Dynamic load balancing efficiently in a large-scale cluster. (27th July 2009)

• Record Type: Journal Article
• Authors: Zhang, Bao-Yin; Mo, Ze-Yao; Yang, Guang-Wen; Zheng, Wei-Min
• Is Part Of: International journal of high performance computing and networking. Volume 6:Number 2(2009)
• Page Start: 100
• Page End: 105
• Publication Date: 2009-07-27
• Subjects: dynamic load balancing -- large-scale clusters -- TRS -- transitive random stealing -- load distribution -- probabilistic model; High performance computing -- Periodicals; Computer networks -- Periodicals; High performance computing; Periodicals; 004.05
• Languages: English
• ISSNs: 1740-0562

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.