A dynamic load balancing algorithm for conservative parallel simulations

Load balancing is an important component in improving the efficiency of distributed systems because it distributes an even workload over all the processors. This paper considers the problem of load-balancing a conservative parallel simulation for execution on a multicomputer. The synchronization protocol makes use of Chandy-Misra (1979) null-messages. An earlier study conducted by Boukerche and Tropper (1994) showed that static load balancing for conservative parallel simulation is effective when the workload can be sufficiently well characterized beforehand. In this paper, we present a dynamic load balancing algorithm which assumes no compile-time knowledge about the workload parameters. It is based upon a process migration mechanism and the notion of CPU-queue length, which indicates the workload at each processor. We discuss the algorithm and its implementation, and report on the performance results of a simulation of FCFS (first-come, first-served) queueing network models on an Intel Paragon A4