On metrics for the dynamic load balancing of optimistic simulations

Focuses on evaluating metrics for use with the dynamic load balancing of optimistic simulations. We present a load balancing algorithm which is token-based and is used in conjunction with clustered time warp (CTW). CTW is a hybrid synchronization protocol, which makes use of a sequential algorithm within clusters of logical processes (LPs) and time warp between the clusters. We define three separate metrics and measure their effectiveness in different simulation environments. One metric measures processor utilization, a second measures the difference in virtual times between the clusters, while a third is a combination of these two metrics. We compare the execution time, memory consumption and throughput obtained in three simulation environments by each of these metrics and to the results obtained without load balancing. Our categories of simulation are VLSI simulations, characterized by a large number of LPs and a low computational granularity; distributed network simulations, in which the workload varies spatially over the execution of the simulation; and a pipeline simulation, characterized by a single direction of message flow. The experiments revealed a significant improvement in the simulation times in the first two categories of simulations when we employed the processor utilization and the combination metrics. For example, improvements of up to 70% were obtained for VLSI simulations. None of the metrics proved to be effective for the pipeline simulation.