Strategies for Dynamic Load Balancing on Highly Parallel Computers

Abstract

Dynamic load balancing strategies for minimizing the execution time of single applications running in parallel on multicomputer systems are discussed. Dynamic load balancing (DLB) is essential for the efficient use of highly parallel systems when solving non-uniform problems with unpredictable load estimates. With the evolution of more highly parallel systems, centralized DLB approaches which make use of a high degree of knowledge become less feasible due to the load balancing communication overhead. Five DLB strategies are presented which illustrate the tradeoff between 1) knowledge—the accuracy of each balancing decision, and 2) overhead—the amount of added processing and communication incurred by the balancing process. The Sender (Receiver) Initiated Diffusion (SID/RID) strategies are asynchronous schemes which only use near-neighbor information. The Hierarchical Balancing Method (HBM) organizes the system into a hierarchy of subsystems within which balancing is performed independently. The Gradient Model (GM) employs a gradient map of the proximities of underloaded processors in the system to guide the migration of tasks between overloaded and underloaded processors. Finally, the Dimension Exchange Method (DEM) requires a synchronization phase prior to load balancing and then balances iteratively. All five strategies have been implemented on an Intel iPSC/2 hypercube. Our results indicate that the RID approach performs well, and can most easily be scaled to support highly parallel systems. © 1993 IEEE