Run-time Support for Adaptive Load Balancing
Authors:
L. V. Kale, Milind Bhandarkar, and Robert Brunner
Parallel Programming Laboratory, Department of Computer Science, University
of Illinois at Urbana-Champaign
In: Rolim J. (Ed.), Parallel and Distributed Processing. Springer Verlag, 2000, ISBN 3-540-67442-X, Lecture Notes in Computer Science, Vol. 1800, (Proceedings of 4th Workshop on Runtime Systems for Parallel Programming (RTSPP) Cancun - Mexico, March 2000.)
Many parallel scientific applications have dynamic and irregular computational structure. However, most such applications exhibit persistence of computational load and communication structure. This allows us to embed measurement-based automatic load balancing framework in run-time systems of parallel languages that are used to build such applications. In this paper, we describe such a framework built for the Converse~\cite{InterOpLongINTL96} interoperable runtime system. This framework is composed of mechanisms for recording application performance data, a mechanism for object migration, and interfaces for plug-in load balancing strategy objects. Interfaces for strategy objects allow easy implementation of novel load balancing strategies that could use application characteristics on the entire machine, or only a local neighborhood. We present the performance of a few strategies on a synthetic benchmark and also the impact of automatic load balancing on an actual application.