Adaptive Load-Balancing Algorithms Using Symmetric Broadcast Networks
Source: Journal of Parallel and Distributed Computing, Volume 62, Number 6, June 2002 , pp. 1042-1068(27)
Publisher: Academic Press
Abstract:In a distributed computing environment, it is important to ensure that the processor workloads are adequately balanced. Among numerous load-balancing algorithms, a unique approach given by Das and Prasad defines a symmetric broadcast network (SBN) that provides a robust communication pattern among the processors in a topology-independent manner. In this paper, we propose and analyze three efficient SBN-based dynamic load-balancing algorithms, and implement them on an SGI Origin2000. A thorough experimental study with Poisson-distributed synthetic loads demonstrates that our algorithms are effective in balancing system load. By optimizing completion time and idle time, the proposed algorithms are shown to compare favorably with several existing approaches. © 2002 Elsevier Science (USA).
Document Type: Research Article
Affiliations: 1: Department of Computer Science and Engineering, The University of Texas at Arlington, Arlington, Texas, 76019 2: Department of Computer Science, Southern Oregon University, Ashland, Oregon, 97520 3: NASA Ames Research Center, Moffett Field, California, 94035
Publication date: 2002-06-01