Design and implementation of dynamic load balancing algorithms for rollback reduction in optimistic PDES

摘要

In an optimistic (time-warp) parallel simulation, local clocks with different logical processes must advance at the same rate in order to reduce the number of rollbacks. In this paper, we propose two algorithms for dynamic load balancing which reduce the number of rollbacks in an optimistic parallel discrete event simulation (PDES) system. The first algorithm is based on the load transfer mechanism between logical processes, while the second algorithm, which is based on the principle of an evolutionary strategy, migrates logical processors between several pairs of physical processors. We have implemented both of these algorithms on a cluster of heterogeneous workstations and studied their performance. The experimental results show that the algorithm based on the load transfer is effective when the grain size is larger than 10 ms, and the algorithm based on the process migration yields good performance for grain sizes of 20 ms or larger. In both of these cases, the average speed-up ranges between 1 and 2 using four processors, when the computation grain-size is within the range 7 to 50 ms. The reduction in rollback messages as a percentage of the total number of messages due to the algorithms is, however, around 4 to 8%.