''Work-Efficient Load Balancing''

Gokarna Sharma

Suresh Rai

Costas Busch

Jerry L. Trahan

Ramachandran Vaidyanathan

Proc. 10th International Workshop on Scheduling and Resource Management for Parallel and Distributed Systems (SRMPDS), pp. 27-36, 2014


Load balancing is the key to many parallel and distributed applications. We consider the following load balancing problem: given any undirected connected graph and an initial weight distribution on the nodes, determine a schedule to move weights across edges so as to have (almost) equal weights on the nodes. Weights are moved across edges in rounds; and, in a round, weights are moved between the adjacent nodes exactly once. We study this problem in both static and dynamic networks. Previously studied diffusion and dimension exchange algorithms are slow in practice in the sense that they require many rounds of weight exchanges. In this paper, we present a class of algorithms that are work-efficient, i.e., they reduce the number of rounds (i.e., iterations) of weight exchanges needed to balance the load. In our algorithms, a node exchanges load with its neighbors sequentially (one neighbor at a time) and the load at that node is updated before subsequent exchanges with other neighbors. Simulation results on six network topologies show that our algorithms balance the load quite work-efficiently compared to previous algorithms.