Heuristic Methods for Dynamic Load Balancing in a Message-Passing Multicomputer

In this paper, a new adaptive scheme is presented for dynamic load balancing in a message-passing multicomputer. The scheme is based on using easy-to-implement heuristics and adaptive threshold in balancing the system load among dispersed nodes. It uses a distributed control over all computer nodes as coordinated by an information collector. Four heuristic methods are presented here, which are distinguished by the ranges for location and threshold update policies and by the disciplines used for determining the load transfer destination. A parallel simulator with distributed load balancers is developed on an iPSC/2 hypercube multi-computer. The load balancing scheme is evaluated on the basis of the effects of system utilization, load imbalance, communication and migration overhead, and multicomputer size. Relative merits of the four methods are revealed under various physical configurations of the multicomputer. The application potentials are discussed for parallel execution of AI-oriented programs and distributed semantic network data bases.