Dynamic load balancing strategies for conservative parallel simulations

Abstract

This paper studies the problem of load balancing for conservative parallel simulations for execution on a multicomputer. The synchronization protocol makes use of Chandy-Misra (1979) null-messages. We propose 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 examine two variations for the algorithm which we refer to as centralized and multi-level hierarchical methods, in the context of queueing network simulation of a torus. The torus was chosen because its many cycles aid in the formation of deadlock, making it a stress test for any conservative synchronization protocols. Our experiments indicate that our dynamic load balancing schemes significantly reduce the run time of an optimized version of Chandy-Misra null message approach, and decreases by 30-40% the synchronization overhead when compared to the use of a static partitioning algorithm. Significantly, the results obtained also indicate that the multi-level scheme always outperforms both the centralized load balancing approach and the static partitioning algorithm.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 39 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.