Title: Dynamic load balancing efficiently in a large-scale cluster

Authors: Bao-Yin Zhang, Ze-Yao Mo, Guang-Wen Yang, Wei-Min Zheng

Addresses: Institute of Applied Physics and Computational Mathematics, Beijing, 100088, PR China. ' Institute of Applied Physics and Computational Mathematics, Beijing, 100088, PR China. ' Department of Computer Science and Technology, Tsinghua University, Beijing, 100084, PR China. ' Department of Computer Science and Technology, Tsinghua University, Beijing, 100084, PR China

Abstract: Random Stealing (RS) is a well-known dynamic load-balancing algorithm, used both in shared-memory and distributed-memory systems. However, for a large-scale cluster, the simple RS policy is no longer efficient because an idle node must randomly steal many times to obtain a task from another node. In this paper, we propose a novel dynamic load-balancing algorithm, Transitive Random Stealing (TRS), which can make any idle node obtain a task from another node with much fewer stealing times in a large-scale cluster. Analysing and testing show that TRS is a highly efficient dynamic load-balancing algorithm in a large-scale cluster.

Keywords: dynamic load balancing; large-scale clusters; TRS; transitive random stealing; load distribution; probabilistic model.

DOI: 10.1504/IJHPCN.2009.027460

International Journal of High Performance Computing and Networking, 2009 Vol.6 No.2, pp.100 - 105

Published online: 26 Jul 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article