A COORDINATED LOCATION POLICY FOR LOAD SHARING IN HYPERCUBE-CONNECTEDMULTICOMPUTERS

Uneven task arrivals in a hypercube-connected multicomputer may tempor arily overload some nodes while leaving others underloaded. This probl em can be solved or alleviated by load sharing (LS); that is, some of the tasks arriving at overloaded nodes, caned overflow tasks, are tran sferred to underloaded nodes. One important issue in LS is to locate u nderloaded nodes to which the overflow tasks can be transferred. This is termed the location policy, Any efficient location policy should di stribute the overflow tasks to the entire system instead of 'dumping' them on a few underloaded nodes, To reduce the overhead for collecting state information and transferring tasks, each node is required to ma intain the state information of only those nodes in its proximity, cal led a buddy set, Several location policies-random probing, random sele ction, preferred lists, and bidding algorithm-are analyzed and compare d for hypercube-connected multicomputer systems, Under the random-sele ction and preferred-list policies, an overloaded node can select, with out probing other nodes, an underloaded node within its buddy set, whi le under the random probing policy and the bidding algorithm the overl oaded node needs to probe other nodes before transferring the overflow task, Task collision(s) is said to occur if two or more overflow task s are transferred (almost) simultaneously to the same underloaded node , The performances of these location policies are analyzed and compare d in terms of the average number of task collisions, Our analysis show s that use of preferred lists allows the overflow tasks to be shared m ore evenly throughout the entire hypercube than the other two location policies.