Dynamic load balancing on the earth-SP system
Haïying. Cai · eScholarship@McGill (McGill) · 1997
The rapid progress of computer systems based on fine-grain multithreaded program execution models introduce both unique opportunities and challenges in the design and application of dynamic load balancing algorithms. This thesis presents a study of dynamic load balancing under the EARTH muitithreaded model. In this study, we have implemented a number of load balancing algorithms on the EARTH-SP testbed--a realization of EARTH model on the IBM-SP2 system. Our study has been carried out on both benchmark programs and a set of stress tests. The major results of this thesis include: (A) Demonstration that a load balancing algorithm is likely to be robust if it has the following features: (1) initiating load balancing requests by both the satiated and the hungry nodes; (2) making use of certain history information to guide balancing decisions. (B) Several specific observations and conclusions: (1) The performances of the load balancers vary under different computation models. This difference between load balancers becomes substantial under certain class of computation such as SPMD model. (2) When the parallelism grain size is small, the performance difference between load balancing algorithms becomes significant. This indicates the importance of searching good load balancers for efficient exploitation of fine-grain parallelism. (3) Some architecture parameters such as polling interval have a considerable impact on the effect of dynamic load balancing. (4) A load balancer with shorter communication path is likely to be scalable. (C) Suggestions for a number of aspects which should be considered in the exploitation of the design space for load balancing algorithms and their evaluations.