Qualitative Parametric Comparison of Load Balancing Algorithms in Parallel and Distributed Computing Environment
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:53848", author = "Amit Chhabra and Gurvinder Singh and Sandeep Singh Waraich and Bhavneet Sidhu and Gaurav Kumar", title = "Qualitative Parametric Comparison of Load Balancing Algorithms in Parallel and Distributed Computing Environment", 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.", volume = "2", number = "4", pages = "1094-4", }