Design and Implementation of DynamicLoad Balancing Algorithms for Rollback Reductionin Optimistic PDES

摘要

In an optimistic parallel simulation, logical processes (Ips) proceed with theircomputation without any constraints. However, if the computing requirements ofdifferent lps are not balanced or if the processors are not homogeneous, some lps maylag behind in simulation time while others surge forward. In other words, if thesimulation clocks of different lps are not progressing at the same rate, cascadingrollbacks may occur nullifying the potential benefit of an optimistic parallel discreteevent simulation (PDES). Hence it is necessary to balance the computational load ondifferent lps in such a way that their local simulation clocks advance almost at the samerate. In this paper, we propose two algorithms for dynamic load balancing which reducethe number of rollbacks in an optimistic PDES system. Our first algorithm is based onthe load transfer mechanism between lps; while the second algorithm, based on theprinciple of evolutionary strategy, migrates logical processes between several pairs ofphysical processors. We have implemented both of these algorithms on a cluster ofheterogeneous workstations and studied their performance. The experimental resultsshow that the algorithm based on the load transfer is effective when the grain size isgreater than 10 milliseconds. The algorithm based on the process migration yields goodperformance only for grain sizes of 20 milliseconds or larger. In both of these cases thespeed up ranges mostly between and 2 using four processors.