Versatile Automatic Load Balancing with Migratable Objects
Thesis 2000
Publication Type: PhD Thesis
Repository URL: robert-thesis
Accessing the power of parallel computation demands efficient load distribution across the processors of the parallel machine. Applications where parallel processing has succeeded most impressively are those where the problem can be easily decomposed into any convenient number of equal-sized partitions. Applications which are irregular or dynamic in their application structure prove more difficult to implement with good parallel efficiency. Usually, a particular application-specific load balancing strategy is implemented for a particular application, using load measures such as data size to detect or control imbalance. We show that treating a program as a collection of communicating objects, measuring the execution time consumed by those objects at run time, and achieving good load balance by automatically moving those objects from processor to processor allow the implementation of efficient load balancers that work with a variety of applications.
Increasingly, parallel computers come in a variety of forms. Non-dedicated parallel computers in the form of clusters of networked desktop workstations are an important source of computing power for many computational scientists. These parallel platforms, however, introduce new challenges for achieving efficient performance. Our techniques address several of the problems faced by applications running on such clusters.
We describe techniques for managing migration of objects in the Charm++ parallel system. Then we describe a framework for creating application-independent load balancers. Finally, we examine several load balancers implemented using this framework and demonstrate their performance characteristics on synthetic as well as real-life applications.
Robert K. Brunner, "Versatile Automatic Load Balancing with Migratable Objects", University of Illinois at Urbana-Champaign, January 2000.
Research Areas