Int. J. of High Performance Computing and Networking   »   2009 Vol.6, No.2

 

 

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

 

Author: 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

 

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

 

Available online: 26 Jul 2009

 

 

Editors Full text accessAccess for SubscribersPurchase this articleComment on this article