| Faster Schedules for Diffusive Load Balancing via Over-Relaxation (1995) | |||||||||||||||
Abstract | |||||||||||||||
| Consider the following load balancing problem. We are given a graph with arbitrary topology and an arbitrary load distribution on the nodes. In each time step, a node can send any amount of load to each neighbor in parallel. This problem is a simple formalization of dynamic load balancing problems arising in various applications on parallel and distributed machines. Earlier work on this problem [Cyb89, SS94, HT93] provides relaxation-type diffusive algorithms which use local and/or global information about the structure of the graph. In this paper we present Algorithm SLB which uses an over-relaxation technique to perform load balancing. For any particular graph, Algorithm SLB needs only a limited amount of global information to begin with but subsequently uses only local information to schedule the load movement. Extensive simulations on different graphs and load distributions confirm that Algorithm SLB is substantially faster than earlier relaxation-based algorithms, especially on... | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||