More Web Proxy on the site http://driver.im/

article

Free access

Dynamic load balancing strategies for conservative parallel simulations

Authors:

Azzedine Boukerche,

Sajal K. DasAuthors Info & Claims

ACM SIGSIM Simulation Digest, Volume 27, Issue 1

Pages 20 - 28

https://doi.org/10.1145/268823.268897

Published: 01 June 1997 Publication History

Abstract

This paper studies the problem of load balancing for conservative parallel simulations for execution on a multicomputer. The synchronization protocol makes use of Chandy-Misra null-messages. We propose a dynamic load balancing algorithm which assumes no compile time knowledge about the workload parameters. It is based upon a process migration mechanism, and the notion of CPU-queue length, which indicates the workload at each processor.We examine two variations for the algorithm which we refer to as centralized and multi-level hierarchical methods, in the context of queueing network simulation of a torus. The torus was chosen because it of its many cycles aid in the formation of deadlock making it a stress test for any conservative synchronization protocols. Our experiments indicate that our dynamic load balancing schemes significantly reduce the run time of an optimized version of Chandy-Misra null message approach, and decreases by 30-40\% the synchronization overhead when compared to the use of a static partitioning algorithm. Significantly, the results obtained also indicate that the multi-level scheme always outperforms both the centralized load balancing approach and the static partitioning algorithm.

References

[1]

Boukerche A., and Tropper C., "Performance Analysis of Distributed Simulation with Clustered Processes", Proc. o/the SCS Multiconf. on Advances in Parallel and Distributed Simulation, Anaheim, Calif. Jan. 1991, pp. 112-120.

[2]

Boukerche, A., and Tropper C., "A Static Partitioning and Mapping Algorithm for Conservative Parallel Simulations", Proc. of 8th Workshop on Parallel and Distributed Simulation, 1994, pp. 164-172.

Digital Library

[3]

Boukerche A., and Tropper C., "Parallel Simulation on the Hypercube Multiprocessor", Distributed Computing, Vol. 8, 1995, pp. 181-190.

Digital Library

[4]

Boukerche A., Das, S. K.,"Load Balancing Strategies for Parallel Simulations on a Multiprocessor Machine" in State-of-the Art in Performance Modeling and Simulation, Eds. G. Zobrist, K. Bagchi and J. Walrand, Gordon and Breach Pub., 1996.

[5]

Boukerche A., "Load Balancing Parallel Simulation on Distributed memory Machines", In preparation.

[6]

Bryant, R. M., and Finkel, R. A, "A Stable Distributed Scheduling Algorithm", Proc. of the 2nd International Conference on Distributed Gomputing Systems, April 1981, pp.314-323.

[7]

Chandy, K.M, and Misra, J., "Distributed Simulation: A Case Study in Design and Verification of Distributed Programs", IEEE Trans. on Software Engineering, SE-5, Sept. 1979, pp. 440-452.

Digital Library

[8]

Das, S.K., and Sarkar, F.,"Reducing Rollbacks Through Load Sharing in Parallel Discrete Event Simulation", Proc. of the Int. Conf. On Parallel and Distributed Computing and Systems, Oct. 1994, pp. 402-410.

[9]

Douglis, F., and Ousterhout, J.,"Transparent Process Migration: Design Alternatives and Sprite Implementation", Software and Experience, 1991, pp. 757-785.

Digital Library

[10]

Eager, D. L., Lazowska, E.D., and Zahorjan, J.,"Adaptive Load Sharing in Homogeneous Distributed Systems", IEEE Trans. on Software Eng., SE-12(5), 1986, pp. 662-675.

Digital Library

[11]

Fox, G. F., Williams, R. D., and Messina, P. C.,'~ParaUel Computing Works!", Morgan Kaufmann Pub., 1994.

[12]

Fujimoto, R. M., "Performance Measurements of Distributed Simu/ation Strategies", Proc. 1988 SCS Multiconference on Distributed Simulation, Vol. 19, No. 3, Feb. 1988, pp. 14-20.

[13]

Fujimoto, R. M., "Parallel Discrete Event Simulation", Communications of the A CM, Vol. 33, No. 10, Oct. 1990, pp. 30-53.

Digital Library

[14]

Glazer, D., and Tropper, C.,"On Process Migration and Load Balancing in Time Warp", IEEE Trans. on Parallel and Distributed Systems, Vol. 4, No. 3, March 1993, pp. 318-327.

Digital Library

[15]

Jefferson, D. R., "Virtual Time", A CM Trans. Prog. Lang. Syst. 77, (3), july 1985, pp. 405- 425.

Digital Library

[16]

Leighton, F. T.,"Introduction to Parallel Algorithms and Architectures: Arrays-Trees- Hypercubes", Morgan and Kaufmann Publ. Inc, 1992.

Digital Library

[17]

Misra, J., "Distributed Discrete-event Simulation", ACM Computing Surveys, Vol. 18, No. 1, March 1986, pp. 39-65.

Digital Library

[18]

Lin, Y. B., and Lazowska, E. D., "Conservative Parallel Simulation for Systems with no Lookahead Prediction",TR 89-07-07, Dept. of Compt. Sc. and Eng., Univ. of Washington, 1989.

[19]

Nicol, D.M., and Reynolds, P.F.,"The automated Partitioning of Simulations for Parallel Execution", Tech. Report. TR-85-15, Univ. Virginia, August 1985.

[20]

Reed, D. A. and Fujimoto, R., " Multicomputer Networks: Message-Based Parallel Processing" MIT Press, 1987.

Digital Library

[21]

Reiher, P., and Jefferson, D.,"Virtual Time Based Dynamic Load Management in the Time Warp Operating System", Proc. of the SCS Multiconference on Distributed Simulation, 1990, pp. 103-111.

[22]

Stankovic, J., and Sidhu I., "An Adaptive Bidding Algorithm for Processes, Clusters and Distributed Groups", Proc. 4th Int. Conf. Dis. tributed Compt. Systems, 1984.

[23]

Wagner, D. B., Lazowska, E.D, and Bershad, B., "Techniques for Efficient Shared Memory Parallel Simulation", Proc. 1089 SGS Multiconf. on Distributed Simulation, 1989, pp. 29-37.

Cited By

Wenjie TYiping YTianlin LXiao SFeng Z(2020)An Adaptive Persistence and Work-stealing Combined Algorithm for Load Balancing on Parallel Discrete Event SimulationACM Transactions on Modeling and Computer Simulation10.1145/336421830:2(1-26)Online publication date: 20-Mar-2020
https://dl.acm.org/doi/10.1145/3364218
Ibrahim MIqbal MAleem MIslam MVo N(2019)MAHA: Migration-based Adaptive Heuristic Algorithm for Large-scale Network SimulationsCluster Computing10.1007/s10586-019-02991-5Online publication date: 25-Sep-2019
https://doi.org/10.1007/s10586-019-02991-5
(2018)Reshuffling PDES platforms for multi/many-core machines: A perspective with focus on load sharingModeling and Simulation-Based Systems Engineering Handbook10.1201/b17902-15(234-263)Online publication date: 9-Oct-2018
https://doi.org/10.1201/b17902-15
Show More Cited By

Index Terms

Dynamic load balancing strategies for conservative parallel simulations

Recommendations

Dynamic load balancing strategies for conservative parallel simulations
PADS '97: Proceedings of the eleventh workshop on Parallel and distributed simulation

This paper studies the problem of load balancing for conservative parallel simulations for execution on a multicomputer. The synchronization protocol makes use of Chandy-Misra null-messages. We propose a dynamic load balancing algorithm which assumes no ...
A Dynamic Load Balancing Algorithm for Conservative Parallel Simulations
MASCOTS '97: Proceedings of the 5th International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems

Load balancing is an important component in improving the efficiency of distributed systems because it distributes an even workload over all the processors. This paper considers the problem of load-balancing a conservative parallel simulation for ...
Strategies for Dynamic Load Balancing on Highly Parallel Computers

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGSIM Simulation Digest

ACM SIGSIM Simulation Digest Volume 27, Issue 1

July 1997

184 pages

ISSN:0163-6103

DOI:10.1145/268823

Chairmen:
Alois Ferscha
Univ. of Wien, Vienna, Austria
,
Brian W. Unger
Univ. of Calgary, Alta, Canada

Issue’s Table of Contents

PADS '97: Proceedings of the eleventh workshop on Parallel and distributed simulation
June 1997
200 pages
ISBN:0818679654
Chairmen:
Alois Ferscha
Univ. Wien, Vienna, Austria
,
Rassul Ayani,
Carl Tropper

Copyright © 1997 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1997

Published in SIGSIM Volume 27, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
827
Total Downloads

Downloads (Last 12 months)114
Downloads (Last 6 weeks)16

Reflects downloads up to 04 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wenjie TYiping YTianlin LXiao SFeng Z(2020)An Adaptive Persistence and Work-stealing Combined Algorithm for Load Balancing on Parallel Discrete Event SimulationACM Transactions on Modeling and Computer Simulation10.1145/336421830:2(1-26)Online publication date: 20-Mar-2020
https://dl.acm.org/doi/10.1145/3364218
Ibrahim MIqbal MAleem MIslam MVo N(2019)MAHA: Migration-based Adaptive Heuristic Algorithm for Large-scale Network SimulationsCluster Computing10.1007/s10586-019-02991-5Online publication date: 25-Sep-2019
https://doi.org/10.1007/s10586-019-02991-5
(2018)Reshuffling PDES platforms for multi/many-core machines: A perspective with focus on load sharingModeling and Simulation-Based Systems Engineering Handbook10.1201/b17902-15(234-263)Online publication date: 9-Oct-2018
https://doi.org/10.1201/b17902-15
Principe MTocci TPellegrini AQuaglia FQuaglia FPellegrini ATheodoropoulos G(2018)Porting Event &Cross-State Synchronization to the CloudProceedings of the 2018 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3200921.3200929(177-188)Online publication date: 14-May-2018
https://dl.acm.org/doi/10.1145/3200921.3200929
Wenjie TYiping YFeng ZTianlin LXiao S(2017)A work-stealing based dynamic load balancing algorithm for conservative parallel discrete event simulationProceedings of the 2017 Winter Simulation Conference10.5555/3242181.3242242(1-12)Online publication date: 3-Dec-2017
https://dl.acm.org/doi/10.5555/3242181.3242242
Wenjie TYiping YFeng ZTianlin LXiao S(2017)A work-stealing based dynamic load balancing algorithm for conservative parallel discrete event simulation2017 Winter Simulation Conference (WSC)10.1109/WSC.2017.8247833(798-809)Online publication date: Dec-2017
https://doi.org/10.1109/WSC.2017.8247833
Inostrosa‐Psijas AGil‐Costa VMarin M Wainer G(2017)Semi‐asynchronous approximate parallel DEVS simulation of web search enginesConcurrency and Computation: Practice and Experience10.1002/cpe.414930:7Online publication date: 5-May-2017
https://doi.org/10.1002/cpe.4149
Gil-Costa VTapia EMarin Mde Rango FRisco Martín J(2016)Asynchronous approximate simulation algorithm for stream processing platforms (WIP)Proceedings of the Summer Computer Simulation Conference10.5555/3015574.3015626(1-6)Online publication date: 24-Jul-2016
https://dl.acm.org/doi/10.5555/3015574.3015626
Marin MGil-Costa VBonacic CSolar RLoper MWainer G(2013)Approximate parallel simulation of web search enginesProceedings of the 1st ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/2486092.2486116(189-200)Online publication date: 19-May-2013
https://dl.acm.org/doi/10.1145/2486092.2486116
Jafer SLiu QWainer G(2013)Synchronization methods in parallel and distributed discrete-event simulationSimulation Modelling Practice and Theory10.1016/j.simpat.2012.08.00330(54-73)Online publication date: Jan-2013
https://doi.org/10.1016/j.simpat.2012.08.003
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Issue’s Table of Contents