research-article

Strategies for Dynamic Load Balancing on Highly Parallel Computers

Authors:

M. H. Willebeek-LeMair,

A. P. ReevesAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 4, Issue 9

Pages 979 - 993

https://doi.org/10.1109/71.243526

Published: 01 September 1993 Publication History

Abstract

Dynamic load balancing strategies for minimizing the execution time of single applications running in parallel on multicomputer systems are discussed. Dynamic load balancing (DLB) is essential for the efficient use of highly parallel systems when solving non-uniform problems with unpredictable load estimates. With the evolution of more highly parallel systems, centralized DLB approaches which make use of a high degree of knowledge become less feasible due to the load balancing communication overhead. Five DLB strategies are presented which illustrate the tradeoff between 1) knowledge - the accuracy of each balancing decision, and 2) overhead - the amount of added processing and communication incurred by the balancing process. All five strategies have beenimplemented on an Inter iPSC/2 hypercube.

References

[1]

{1} M. Willebeek-LeMair and A. P. Reeves, "Region growing on a hypercube multiprocessor," in Proc. 3rd Conf. Hypercube Concurrent Comput. and Appl., 1988, pp. 1033-1042.

Digital Library

[2]

{2} T. L. Casavant and J. G. Kuhl, "A taxonomy of scheduling in general-purpose distributed computing systems," IEEE Trans. Software Eng., vol. 14, no. 2, pp. 141-154, Feb. 1988.

Digital Library

[3]

{3} Y.-T. Wang and R. J. T. Morris, "Load sharing in distributed systems," IEEE Trans. Comput., vol. C-34, pp. 204-217, Mar. 1985.

[4]

{4} M. J. Berger and S. H. Bokhari, "A partitioning strategy for nonuniform problems on multiprocessors," IEEE Trans. Comput., vol. C-36, pp. 570-580, May 1987.

Digital Library

[5]

{5} G. C. Fox, "A review of automatic load balancing and decomposition methods for the hypercube," California Institute of Technology, C3P- 385, Nov. 1986.

[6]

{6} K. Ramamritham, J. A. Stankovic, and W. Zhao, "Distributed scheduling of tasks with deadlines and resource requirements," IEEE Trans. Comput., pp. 1110-1123, Aug. 1989.

Digital Library

[7]

{7} K. M. Baumgartner, R. M. Kling, and B. W. Wah, "Implementation of GAMMON: An efficient load balancing strategy for a local computer system," in Proc. 1989 Int. Conf. Parallel Processing, vol. 2, Aug. 1989, pp. 77-80.

[8]

{8} F. C. H. Lin and R. M. Keller, "The gradient model load balancing method," IEEE Trans. Software Eng., vol. 13, no. 1, pp. 32-38, Jan. 1987.

Digital Library

[9]

{9} L. V. Kale, "Comparing the performance of two dynamic load distribution methods," in Proc. 1988 Int. Conf. Parallel Processing, Aug. 1988, pp. 8-12.

[10]

{10} J. Hong, X. Tan, and M. Chen, "From local to global: An analysis of nearest neighbor balancing on hypercube," in Proc. Third Conf. Hypercube Concurrent Comput. and Appl., Jan. 1988.

Digital Library

[11]

{11} K. G. Shin and Y.-C. Chang, "Load sharing in distributed real-time systems with state-change broadcasts," IEEE Trans. Comput., pp. 1124-1142, Aug. 1989.

Digital Library

[12]

{12} V. A. Saletore, "A distrubuted and adaptive dynamic load balancing scheme for parallel processing of medium-grain tasks," in Proc. Fifth Distributed Memory Comput. Conf., Apr. 1990, pp. 995-999.

[13]

{13} W. Shu and L. V. Kale, "A dynamic scheduling strategy for the Charekernel system," in Proc. ACM Supercomput. Conf., 1989, pp. 389-398.

Digital Library

[14]

{14} M. Willebeek-LeMair and A. P. Reeves, "A general dynamic load balancing model for parallel computers," Tech. Rep. EE-CEG-89-1, Cornell School of Electrical Engineering, 1989.

[15]

{15} G. Cybenko, "Dynamic load balancing for distributed memory multiprocessors," J. Parallel and Distributed Comput., vol. 7:279-301, October, 1989.

Digital Library

[16]

{16} D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Englewood Cliffs, NJ: Prentice-Hall, 1989.

Digital Library

[17]

{17} K. M. Dragon and J. L. Gustafson, "A low-cost hypercube load balance algorithm," in Proc. Fourth Conf. Hypercubes, Concurrent Comput. and Appl., 1989, pp. 583-590.

[18]

{18} M. Hailperin, "Load balancing for massivelly-parallel soft-real-time systems," in Proc. 2nd Symp. Frontiers of Massively Parallel Computation, 1988, pp. 159-163.

[19]

{19} D. E. Eager, E. D. Lazowska, and J. Zahorjan, "A comparison of receiver-initiated and sender-initiated adaptive load sharing," Perform. Eval., vol. 6, pp. 53-68, 1986, North-Holland.

Digital Library

[20]

{20} R. P. Pargas and E. D. Wooster, "Branch-and-bound algorithms on a hypercube," in Proc. Third Conf. Hypercube Concurrent Comput. and Appl., Jan. 1988.

Digital Library

[21]

{21} V. N. Rao and V. Kumar, "Parallel depth first search. Part I. Implementation," Int. J. Parallel Programming, vol. 16, no. 6, 1987.

Digital Library

[22]

{22} V. N. Rao and V. Kumar, "Parallel depth first search. Part II. Analysis," Int. J. Parallel Programming, vol. 16, no. 6, 1987.

Digital Library

Cited By

de Mooij JBhattacharya PDell’Anna DDastani MLogan BSwarup S(2023)A framework for modeling human behavior in large-scale agent-based epidemic simulationsSimulation10.1177/0037549723118489899:12(1183-1211)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1177/00375497231184898
De Rango AGiordano AMendicino GRongo RSpataro W(2023)Tailoring load balancing of cellular automata parallel execution to the case of a two-dimensional partitioned domainThe Journal of Supercomputing10.1007/s11227-023-05043-379:8(9273-9287)Online publication date: 10-Jan-2023
https://dl.acm.org/doi/10.1007/s11227-023-05043-3
Chen RWang ZSu HXie SWang Z(2022)Parallel XPath query based on cost optimizationThe Journal of Supercomputing10.1007/s11227-021-04074-y78:4(5420-5449)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s11227-021-04074-y
Show More Cited By

Strategies for Dynamic Load Balancing on Highly Parallel Computers
1. Theory of computation
  1. Models of computation
    1. Concurrency

Recommendations

Load Balancing Requirements in Parallel Implementations of Image Feature Extraction Tasks

Load balancing requirements in parallel image analysis are considered and results on theperformance of parallel implementations of two image feature extraction tasks on theConnection Machine and the iPSC/2 hypercube are reported and discussed. A ...
A distributed diffusion method for dynamic load balancing on parallel computers
PDP '95: Proceedings of the 3rd Euromicro Workshop on Parallel and Distributed Processing

Parallel applications can be divided into tasks that can be executed simultaneously in different processors. Depending on prior knowledge about computational requirements of the problem, the assignment of tasks to processors can be guided in two ways: ...
A case for on-machine load balancing

This paper diverges from the traditional load balancing, and introduces a new principle called the on-machine load balance rule. The on-machine load balance rule leads to resource allocations that are better in tolerating uncertainties in the processing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 4, Issue 9

September 1993

112 pages

ISSN:1045-9219

Issue’s Table of Contents

Copyright © Copyright © 1993 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 September 1993

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

116
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

de Mooij JBhattacharya PDell’Anna DDastani MLogan BSwarup S(2023)A framework for modeling human behavior in large-scale agent-based epidemic simulationsSimulation10.1177/0037549723118489899:12(1183-1211)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1177/00375497231184898
De Rango AGiordano AMendicino GRongo RSpataro W(2023)Tailoring load balancing of cellular automata parallel execution to the case of a two-dimensional partitioned domainThe Journal of Supercomputing10.1007/s11227-023-05043-379:8(9273-9287)Online publication date: 10-Jan-2023
https://dl.acm.org/doi/10.1007/s11227-023-05043-3
Chen RWang ZSu HXie SWang Z(2022)Parallel XPath query based on cost optimizationThe Journal of Supercomputing10.1007/s11227-021-04074-y78:4(5420-5449)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s11227-021-04074-y
He QZhang FBian GZhang WLi ZDuan D(2022)Real-time network virtualization based on SDN and Docker containerCluster Computing10.1007/s10586-022-03731-y26:3(2069-2083)Online publication date: 16-Sep-2022
https://dl.acm.org/doi/10.1007/s10586-022-03731-y
Jia NWang RLi MGuan YZhou F(2021)Towards the Concurrent Optimization of the ServerComplexity10.1155/2021/55871702021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/5587170
Wei LMellor-Crummey JGupta RShen X(2020)Using sample-based time series data for automated diagnosis of scalability losses in parallel programsProceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3332466.3374538(144-159)Online publication date: 19-Feb-2020
https://dl.acm.org/doi/10.1145/3332466.3374538
Lavanya K. Reddy LReddy B(2019)Distributed Based Serial Regression Multiple Imputation for High Dimensional Multivariate Data in Multicore Environment of CloudInternational Journal of Ambient Computing and Intelligence10.4018/IJACI.201904010510:2(63-79)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.4018/IJACI.2019040105
Yu RKilari VXue GYang D(2019)Load Balancing for Interdependent IoT MicroservicesIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737450(298-306)Online publication date: 29-Apr-2019
https://dl.acm.org/doi/10.1109/INFOCOM.2019.8737450
Cabrera AAcosta AAlmeida FBlanco V(2019)A heuristic technique to improve energy efficiency with dynamic load balancingThe Journal of Supercomputing10.1007/s11227-018-2718-675:3(1610-1624)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s11227-018-2718-6
Ashok Kumar CVimala RAravind Britto KSathya Devi S(2019)FDLA: Fractional Dragonfly based Load balancing Algorithm in cluster cloud modelCluster Computing10.1007/s10586-018-1977-622:1(1401-1414)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s10586-018-1977-6
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents