Article

Free access

Performance prediction tools for parallel discrete-event simulation

Authors:

Shell Ying HuangAuthors Info & Claims

PADS '99: Proceedings of the thirteenth workshop on Parallel and distributed simulation

Pages 148 - 155

Published: 01 May 1999 Publication History

PDF eReader Publisher Site

Abstract

We have developed a set of performance prediction tools which help to estimate the achievable speedups from parallelizing a sequential simulation. The tools focus on two important factors in the actual speedup of a parallel simulation program : (a) the simulation protocol used, and (b) the inherent parallelism in the simulation model. The first two tools are a performance/parallelism analyzer for a conservative, asynchronous simulation protocol, and a similar analyzer for a conservative, synchronous ("super-step") protocol. Each analyzer allows us to study how the speedup of a model changes with increasing number of processors, when a specific protocol is used. The third tool -- a critical path analyzer -- gives an ideal upper bound to the model's speedup. This paper gives an overview of the prediction tools, and reports the predictions from applying the tools to a discrete-event wafer fabrication simulation model. The predictions are close to speedups from actual parallel implementations. These tools help us to set realistic expectations of the speedup from a parallel simulation program, and to focus our work on issues which are more likely to yield performance improvement.

References

[1]

O. Berry and D. Jefferson. Critical path analysis of distributed simulation. In Proceedings of 1985 SCS Multiconference on Distributed Simulation, pages 57-60, January 1985.

[2]

W. Cai, E. Letertre, and S. J. Turner. Dag consistent parallel simulation: a predictable and robust conservative algorithm. In Proceedings of 11th Workshop on Parallel and Distributed Simulation (PADS'97), pages 178-181, Lockenhaus Austria, June 1997.

Digital Library

[3]

K. Chandy and J. Misra. Distributed simulation: a case study in design and verification of distributed programs. IEEE Trans. On Software Engineering, SE-5(5):440--452, Sept. 1979.

Digital Library

[4]

E. G. Coffman, M. R. Garey, and D. S. Johnson. An application of bin-packing to multiprocessor scheduling. SIAM Journal of Computing, 7:1-17, 1978.

[5]

A. Ferscha and J. Johnson. Performance oriented development of spmd programs based on task structure specifications. In Proceedings of the CONPAR 94 - VAPP VI conference, pages 53-65, Linz, Austria, Sept 6--8 1994. Lecture Notes in Computer Science, Springer Verlag.

Digital Library

[6]

Karypis, George. University of Minnesota, Minneaspolis, MN. Metis: Family of multilevel partitioning algorithms. http:llwww-users.cs.umn.edulkarypis/metis, 1998.

[7]

C.-C. Lira, Y.-H. Low, and Cai Wentong. A parallelism analyzer algorithm for a conservative super-step simulation protocol. In Hawaii International Conference on System Sciences (HICSS-32), Maul, Hawaii, USA, January 5-8 1999.

[8]

C.-C. Lim, Yoke-Heart Low, and Stephen J. Turner. Relaxing safetime computation of a conservative simulation algorithm. In International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'98), pages 1538-t545, Las Vegas, Nevada, USA, July 1998.

[9]

M. Livny. A study of parallelism in distributed simulation. In Proceedings of 1985 SCS Multiconference on Distributed Simulation, pages 94--98, January 1985.

[10]

Y.-H. Low, C.-C. Lim, B.-P. Gan, S. Jain, W. Cai, W. J. Hsu, S. Y. Huang, and S. J. Turner. Conservative parallel simulation of manufacturing system. In 8th International Parallel Computing Workshop (PCW'98), pages 293-300. Singapore, September 7-8 1998.

Digital Library

[11]

D. Nicol. Problem characteristics and parallel discrete event simulation, volume Parallel Computing: Paradigms and Applications, chapter 19, pages 499-513. Int. Thomson Computer Press, 1996.

[12]

B.L. Noble and R. D. Chamberlain. Performance model for speculative simulation using predictive optimism. In Hawaii International Conference on System Sciences (HICSS-32), Maul, Hawaii, USA, January 5-8 1999.

Digital Library

[13]

Pellegrini, Franqois. LaBRI, Universit~ Bordeaux-l. Scotch" Static mapping and graph partitioning package, http:// www.labri.u-bordeaux.frl Equipel ALiENor/membrel pelegrin/scotch/, 1998.

[14]

Sanjay Jain. Virtual factory framework: A key enabler for agile manufacturing. In Proceedings of 1995 INRIA/ IEEE Symposium on Emerging Technologies and Factor. Automation, volume 1, pages 247-258, Pads, Oct. 1995. IEEE Computer Society Press, Los Alamitos, CA.

[15]

Sematech. Modeling data standards, version 1.0. Technical report, Sematech, Inc., Austin, TX78741, 1997.

[16]

The National Center for Supercomputing Applications (NCSA) and University of Illinois at Urbana-Champaign. Scalable parallel random number generators library for parallel monte carlo computations, http://www.ncsa.uiuc.edu/ Appsl CMP/RNGI RNG-home.html.

[17]

Y.-C. Wong, S.-Y. Hwang, and J. Y.-B. Lin. A parallelism analyzer for conservative parallel simulation. IEEE Transactions on Parallel and Distributed Systems, 6(6):628-638, June 1995.

Digital Library

[18]

C. M. Woodside and Monforton G. G. Fast allocation of processes in distributed and parallel systems. IEEE Transactions on Parallel and Distributed Systems, 4(2), 1993.

Digital Library

Cited By

Seok MChan CCai WSarjoughian HPark DLiu JGiabbanelli PCarothers C(2020)Runtime Abstraction-Level Conversion of Discrete-Event Wafer-fabrication Models for Simulation AccelerationProceedings of the 2020 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3384441.3395982(83-92)Online publication date: 15-Jun-2020
https://dl.acm.org/doi/10.1145/3384441.3395982
Gianni DBocciarelli PD'Ambrogio ARose OUhrmacher A(2012)Model-driven performance prediction of HLA-based distributed simulation systemsProceedings of the Winter Simulation Conference10.5555/2429759.2430150(1-12)Online publication date: 9-Dec-2012
https://dl.acm.org/doi/10.5555/2429759.2430150
Gianni DIazeolla GD'Ambrogio A(2010)A Methodology to Predict the Performance of Distributed SimulationsProceedings of the 2010 IEEE Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2010.5471669(31-39)Online publication date: 17-May-2010
https://dl.acm.org/doi/10.1109/PADS.2010.5471669
Show More Cited By

Index Terms

Performance prediction tools for parallel discrete-event simulation
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Model verification and validation
    2. Simulation types and techniques
      1. Discrete-event simulation
      2. Massively parallel and high-performance simulations
2. Software and its engineering
  1. Software notations and tools
    1. Software libraries and repositories

Recommendations

Towards Automated Performance Prediction in Bulk-Synchronous Parallel Discrete-Event Simulation
SCCC '99: Proceedings of the 19th International Conference of the Chilean Computer Science Society

This paper discusses the running time cost of performing discrete-event simulation on the bulk-synchronous parallel (BSP) model of computing. The BSP model provides a general purpose framework for parallel computing which is independent of the ...
Discrete-event simulation on a massively parallel computer
Parallel DaSSF Discrete-Event Simulation without Shared Memory

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PADS '99: Proceedings of the thirteenth workshop on Parallel and distributed simulation

May 1999

194 pages

ISBN:0769501559

Chairmen:
Richard M. Fujimoto
Georgia Institute of Technology, Atlanta
,
Stephen J. Turner
Univ. of Exeter, Exeter, UK

Copyright © Copyright (c) 1998 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Sponsors

SCS: Society for Computer Simulation
SIGSIM: ACM Special Interest Group on Simulation and Modeling
IEEE-CS\TCSIM: TC on Simulation

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 May 1999

Check for updates

Qualifiers

Article

Conference

PADS99

Sponsor:

SCS
SIGSIM
IEEE-CS\TCSIM

PADS99: ACM Workshop on Parallel and Distributed Simulation

May 1 - 4, 1999

Georgia, Atlanta, USA

Acceptance Rates

PADS '99 Paper Acceptance Rate 19 of 38 submissions, 50%;

Overall Acceptance Rate 398 of 779 submissions, 51%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
288
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)4

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Seok MChan CCai WSarjoughian HPark DLiu JGiabbanelli PCarothers C(2020)Runtime Abstraction-Level Conversion of Discrete-Event Wafer-fabrication Models for Simulation AccelerationProceedings of the 2020 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3384441.3395982(83-92)Online publication date: 15-Jun-2020
https://dl.acm.org/doi/10.1145/3384441.3395982
Gianni DBocciarelli PD'Ambrogio ARose OUhrmacher A(2012)Model-driven performance prediction of HLA-based distributed simulation systemsProceedings of the Winter Simulation Conference10.5555/2429759.2430150(1-12)Online publication date: 9-Dec-2012
https://dl.acm.org/doi/10.5555/2429759.2430150
Gianni DIazeolla GD'Ambrogio A(2010)A Methodology to Predict the Performance of Distributed SimulationsProceedings of the 2010 IEEE Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2010.5471669(31-39)Online publication date: 17-May-2010
https://dl.acm.org/doi/10.1109/PADS.2010.5471669
Wang YCai WLow MZhou STian FLuo LOng DHamilton BWainer GShaffer CMcGraw RChinni M(2009)A framework of evaluating partitioning mechanisms for agent-based simulation systemsProceedings of the 2009 Spring Simulation Multiconference10.5555/1639809.1639844(1-8)Online publication date: 22-Mar-2009
https://dl.acm.org/doi/10.5555/1639809.1639844
Teo PTurner SJuhasz Z(2005)Optimistic Protocol Analysis in a Performance Analyzer and Prediction ToolProceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2005.17(49-58)Online publication date: 1-Jun-2005
https://dl.acm.org/doi/10.1109/PADS.2005.17
Park AFujimoto RPerumalla KLuthi JLehmann APage EMcLean A(2004)Conservative synchronization of large-scale network simulationsProceedings of the eighteenth workshop on Parallel and distributed simulation10.1145/1013329.1013355(153-161)Online publication date: 16-May-2004
https://dl.acm.org/doi/10.1145/1013329.1013355
Xu JChung M(2004)Predicting the Performance of Synchronous Discrete Event SimulationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2004.8515:12(1130-1137)Online publication date: 1-Dec-2004
https://dl.acm.org/doi/10.1109/TPDS.2004.85
Chung IHollingsworth JHuskamp J(2004)Using Information from Prior Runs to Improve Automated Tuning SystemsProceedings of the 2004 ACM/IEEE conference on Supercomputing10.1109/SC.2004.65Online publication date: 6-Nov-2004
https://dl.acm.org/doi/10.1109/SC.2004.65
Gan BLow YJain STurner SCai WHsu WHuang SDonatiello LTurner SBruce D(2000)Load balancing for conservative simulation on shared memory multiprocessor systemsProceedings of the fourteenth workshop on Parallel and distributed simulation10.5555/336146.336177(139-146)Online publication date: 1-May-2000
https://dl.acm.org/doi/10.5555/336146.336177

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

Media

Figures

Other

Tables

View Table of Contents