Qualitative Parametric Comparison of Load Balancing Algorithms in Parallel and Distributed Computing Environment

Authors: Amit Chhabra, Gurvinder Singh, Sandeep Singh Waraich, Bhavneet Sidhu, Gaurav Kumar

Abstract:

Decrease in hardware costs and advances in computer networking technologies have led to increased interest in the use of large-scale parallel and distributed computing systems. One of the biggest issues in such systems is the development of effective techniques/algorithms for the distribution of the processes/load of a parallel program on multiple hosts to achieve goal(s) such as minimizing execution time, minimizing communication delays, maximizing resource utilization and maximizing throughput. Substantive research using queuing analysis and assuming job arrivals following a Poisson pattern, have shown that in a multi-host system the probability of one of the hosts being idle while other host has multiple jobs queued up can be very high. Such imbalances in system load suggest that performance can be improved by either transferring jobs from the currently heavily loaded hosts to the lightly loaded ones or distributing load evenly/fairly among the hosts .The algorithms known as load balancing algorithms, helps to achieve the above said goal(s). These algorithms come into two basic categories - static and dynamic. Whereas static load balancing algorithms (SLB) take decisions regarding assignment of tasks to processors based on the average estimated values of process execution times and communication delays at compile time, Dynamic load balancing algorithms (DLB) are adaptive to changing situations and take decisions at run time. The objective of this paper work is to identify qualitative parameters for the comparison of above said algorithms. In future this work can be extended to develop an experimental environment to study these Load balancing algorithms based on comparative parameters quantitatively.

Keywords: SLB, DLB, Host, Algorithm and Load.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1059751

References:

[1] Y.C. Chow and W. Kohler, "Models for Dynamic Load Balancing in a Heterogeneous Mu1tiiple Processor System," IEEE Transactions on Computers, Vol. C-28, pp. 334-361, May 1979.
[2] D L Eager, E D Lazowska , J Zahorjan, "A comparison of receiverinitiated and sender-initiated adaptive load sharing", Performance Evaluation, v.6 n.1, p.53-68, March 1986.
[3] Derek L. Eager, Edward D. Lazowska , John Zahorjan, "Adaptive load sharing in homogeneous distributed systems", IEEE Transactions on Software Engineering, v.12 n.5, p.662-675, May 1986.
[4] C.H.Hsu and J.W.Liu "Dynamic Load Balancing Algorithms in Homogeneous Distributed System," Proceedings of The 6th International Conference on Distributed Computing Systems, May, 1986, pp. 216-223.
[5] Miron Livny, Myron Melman, "Load balancing in homogeneous broadcast distributed systems", Proceedings of the Computer Network Performance Symposium, p.47-55, April 13-14, 1982, College Park, Maryland, United States.
[6] H.S. Stone. "Multiprocessor scheduling with the aid of network flow algorithms". IEEE Trans of Software Engineering, SE-3(1):95--93, January 1977.
[7] H.S. Stone, "Critical Load Factors in Two-Processor Distributed Systems," IEEE Trans. Software Eng., vol. 4, no. 3, May 1978.
[8] Y.Wang and R. Morris, "Load balancing in distributed systems," IEEE Trans. Computing. C-34, no. 3, pp. 204-217, Mar. 1985.