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 due to 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 novel SBN-based load-balancing algorithms, and implement them on an SP2. A thorough experimental study with Poisson-distributed synthetic loads demonstrates that these algorithms are very effective in balancing system load while minimizing processor idle time. They also compare favorably with several other existing load-balancing techniques.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Cybenko, G.: Dynamic load balancing for distributed-memory multiprocessors. J. Parallel Distrib. Comput. 7 (1989) 279–301
Das, S., Harvey, D., Biswas, R.: Adaptive load-balancing algorithms using symmetric broadcast networks, NASA Ames Research Center Technical Report NAS97-014 (1997)
Das, S., Prasad, S.: Implementing task ready queues in a multiprocessing environment. International Conference on Parallel Computing (1990) 132–140
Das, S., Yang, C., Leung, N.: Implementation of load balancing in multiprocessor systems using a symmetric broadcast network. International Conference of Parallel and Distributed Systems (1992) 589–596
Eager, D., Lazowska, E., Zahorjan, J.: Adaptive load sharing in homogeneous distributed systems. IEEE Trans. on Soft. Engrg. 12 (1986) 662–675
Eager, D., Lazowska, E., Zahorjan, J.: A comparison of receiver-initiated and sender-initiated adaptive load sharing. Perf. Eval. 6 (1986) 53–68
Lin, F., Keller, R.: The gradient model load balancing method. IEEE Trans. on Soft. Engrg. 13 (1987) 32–38
Sarkar, V., Hennessy, J.: Compile-time partitioning and scheduling of parallel programs. Scheduling and Load Balancing in Parallel and Distributed Systems (1995) 61–70
Shivaratri, N., Krueger, P., Singhal, M.: Load distributing for locally distributed systems. Computer 25 (1992) 33–44
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Das, S.K., Harvey, D.J., Biswas, R. (1997). Design of novel load-balancing algorithms with implementations on an IBM SP2. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds) Euro-Par'97 Parallel Processing. Euro-Par 1997. Lecture Notes in Computer Science, vol 1300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0002836
Download citation
DOI: https://doi.org/10.1007/BFb0002836
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63440-9
Online ISBN: 978-3-540-69549-3
eBook Packages: Springer Book Archive