Heuristic methods for dynamic load balancing in a message-passing supercomputer
Jian Xu, Kai Hwang · Conference on High Performance Computing (Supercomputing) · 1990
In this paper, a new adaptive scheme is presented for dynamic load balancing on a message-passing multicomputer. The scheme is based on using easy-to-implement heuristics and variable threshold in migrating processes among the multicomputer nodes. It uses a distributed control over all processor nodes as coordinated by a host processor. Four heuristic methods for process migration are presented, which are distinguished by choosing different policies for process migration and threshold update. A parallel simulator with distributed load balancers is developed on an iPSC/2 hypercube system. The load balancing scheme is evaluated on the effects of system utilization, load imbalance, communication and migration overhead, and multicomputer size. Relative merits of the four methods are revealed under various multicomputer conditions.