Handling Application-Induced Load Imbalance using Parallel Objects
Authors:
Robert K. Brunner and Laxmikant V. Kale
Parallel Programming Laboratory, Department of Computer Science, University
of Illinois at Urbana-Champaign
Parallel and Distributed Computing for Symbolic and Irregular Applications, pp. 167-181
One of the problems in applying parallel computing for a broad class of applications arises from the dynamic nature of computations being parallelized. Even if the computation is carefully load-balanced at the beginning, the balance deteriorates over time, either do to adaptive refinements, or gradual change in the load of different components. Such imbalances can have a dramatic effect on performance, especially when a large number of processors are used. We present a methodology based on data-driven objects that can automatically handle such application-induced load imbalances and rebalance the load as needed. The methodology relies on automatic instrumentation to record load and communication patterns, and a flexible load-balancing framework that facilitates development of different strategies that may be appropriate for different classes of applications.