Article

Optimistic simulation of parallel message-passing applications

Authors:

Rajive BagrodiaAuthors Info & Claims

PADS '01: Proceedings of the fifteenth workshop on Parallel and distributed simulation

Pages 173 - 181

Published: 15 May 2001 Publication History

Publisher Site Get Access

Abstract

Optimistic techniques can improve the performance of discrete-event simulations, but one area where optimistic simulators have been unable to show performance improvement is in the simulation of parallel programs. Unfortunately parallel program simulation using direct execution is difficult: the use of direct execution implies that the memory and computation requirements of the simulator are at least as large as that of the target application, which restricts the target systems and application problem sizes that can be studied. Memory usage is especially important for optimistic simulators due to the need for periodic state-saving and rollback. In our research we addressed this problem and have implemented a simulation library running a Time-Warp-based optimistic engine that uses direct execution to simulate and predict the performance of parallel MPI programs while attaining good simulation speedup. For programs with data sets too large to be directly executed with our optimistic simulator, we reduced the memory and computational needs of these programs by utilizing a static task graph and code-slicing methodology; an approach which also exhibited good performance speedup.

References

[1]

V. Adve, R. Bagrodia, E. Deelman, T. Phan, and R. Sakellariou. "Compiler-Supported Simulation of Highly Scalable Parallel Applications," Proceedings of Supercomputing '99, Portland, Oregon, November 1999.

Digital Library

[2]

R. Bagrodia, R. Meyer, M. Takai, Y. Chen, X. Zeng, J. Martin, B. Park, and H. Song. "PARSEC: A Parallel Simulation Environment for Complex Systems," IEEE Computer, vol. 31 ( 1 ), October 1998.

Digital Library

[3]

R. Bagrodia, E. Deelman, S. Docy, and T. Phan. "Performance Prediction of Large Parallel Applications Using Parallel Simulations," in Proceedings of ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Atlanta, Georgia, May 4-6, 1999.

Digital Library

[4]

D. Bailey, T. Harris, W. Shaphir, R. van der Winjngaart, A. Woo, and M. Yarrow. "The NAS Parallel Benchmarks 2.0," Report NAS-95-090, NASA Ames Research Center, 1995.

[5]

S. Chandrasekaran and M. Hill. "Optimistic Simulation of Parallel Architectures Using Program Executahles," Workshop on Parallel and Distributed Simulation, May 1996.

Digital Library

[6]

R. Covington, S. Dwarkadas, J. Jump, J. Sinclair, and S. Madala. "'The Efficient Simulation of Parallel Computer Systems," International Journal in Computer Simulation, vol. 1, 1991.

[7]

H. Davis, S. Goldschmidt, and J. Hennessy. "Multiprocessot Simulation and Tracing Using Tango," In Proceedings of the 1991 International Conference on Parallel Processing, August 1991.

[8]

P. Dickens, P. Heidelberger, and D. Nicol. "Parallelized Network Simulators for Message-Passing Parallel Programs," In Proceedings of the Third huernational Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS), Durham, NC, USA, 18-20 Jan. 1995.

Digital Library

[9]

E Dickens, R Heidelberger, and D. Nicol. "Parallelized Direct Execution Simulation of Message-Passing Parallel Programs," 1EEl" Transactions on Parallel and Distributed Svstents, vol.7, (no. 10), Oct. 1996.

Digital Library

[10]

M. Dikaiakos, A. Rogers, and K. Steiglitz. "FAST: a Functional Algorithm Simulation Testbed," In Proceedings of MASCOTS 94.

Digital Library

[11]

M. Dikaiakos, A. Rogers, and K. Steiglitz. "Function Algorithm Simulation of the Fast Multipole Method: Architectural Implications," Parallel Processing Letters, 6( 1 ), March 1996.

[12]

D. Jefferson. "Virtual Time," ACM Transactions on Programming Languages and Systems, vol. 7, 1985.

Digital Library

[13]

S. Horwitz, T. Reps, and D. Binkley. "lnterprocedural Slicing Using Dependence Graphs," ACM Transactions on Programming Languages and Systems, 12( 1 ), January 1990.

Digital Library

[14]

J. Laudon and D. Lenoski. "The SGI Origin: A ccNUMA Highly Scalable Server," The 24th Annual International Symposium on Computer Architecture, May 1997.

Digital Library

[15]

U. Legedza. "Reducing Synchronization Overhead in Parallel Programs," MIT Technical Report MIT/LCS/'TR-655.

Digital Library

[16]

J. Martin and R. Bagrodia. "COMPOSE: An Object- Oriented Environment for Parallel Discrete-Event Simulations," In Proceedings of the 1995 Winter Simulation Conference, December 1995.

Digital Library

[17]

"Message-Passing Interface - MPI," www. mcs. a n l . gov/mpi /

[18]

"The NAS Parallel Benchmarks," www.nas .nasa.gov/Software/NPB/

[19]

The POEMS Homepage. www. cs .utexas. edu/usera/poems/

[20]

S. Prakash and R. Bagrodia. "Parallel Simulation of Data Parallel Programs," In Proceedings of the 8th Workshop on Languages and Compilers for Parallel Computing, Columbus, Ohio, 1995.

Digital Library

[21]

S. Prakash and R. Bagrodia. "'Using Parallel Simulation to Evaluate MPI Programs," in Proceedings of the 1998 Winter Simulation Conference.

Digital Library

[22]

S. Reinhardt, M. Hill, J. Larus, A. Lebeck, J. Lewis, and D. Wood. "The Wisconsin Wind Tunnel: Virtual Prototyping of Parallel Computers," In Proceedings of the 1993 ACM S1G- METRIC Conference, May 1993.

Digital Library

[23]

M. Rosenblum, E. Bugnion, S. Devine, and S. Herrod. "'Using the SimOS Machine Simulator to Study Complex Computer Systems," ACM Transactions ol7 Modeling and Computer Simulation, 7( 1 ), January 1997.

Digital Library

[24]

J. Steinman. "Incremental State Saving in SPEEDES Using C++," In Proceedings of the 1993 Winter Simulation Conference, December 1993.

Digital Library

[25]

Sweep3D."The ASCISweep3D Benchmark," www.llnl.gov/asci_benchmarks/asci/ limited/sweep3d.html

Cited By

Perumalla KPerrone LStea GLiu JUhrmacher AVillén-Altamirano M(2010)μπProceedings of the 3rd International ICST Conference on Simulation Tools and Techniques10.4108/ICST.SIMUTOOLS2010.8692(1-6)Online publication date: 15-Mar-2010
https://dl.acm.org/doi/10.4108/ICST.SIMUTOOLS2010.8692
Naborskyy AFujimoto R(2007)Using Reversible Computation Techniques in a Parallel Optimistic Simulation of a Multi-Processor Computing SystemProceedings of the 21st International Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2007.31(179-188)Online publication date: 12-Jun-2007
https://dl.acm.org/doi/10.1109/PADS.2007.31

Index Terms

Optimistic simulation of parallel message-passing applications

Recommendations

Conservative vs. optimistic parallel simulation of DEVS and Cell-DEVS: a comparative study
SCSC '10: Proceedings of the 2010 Summer Computer Simulation Conference

The conservative Parallel DEVS protocol offers a novel approach that allows conservative simulation of DEVS-based PDES systems. The protocol is based on the classical Chandy-Misra-Bryant synchronization mechanism, and it extends the DEVS abstract ...
Parallelized Direct Execution Simulation of Message-Passing Parallel Programs

As massively parallel computers proliferate, there is growing interest in finding ways by which performance of massively parallel codes can be efficiently predicted. This problem arises in diverse contexts such as parallelizing compilers, parallel ...
PARALLELIZED DIRECT EXECUTION SIMULATION OF MESSAGE-PASSING PARALLEL PROGRAMS

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PADS '01: Proceedings of the fifteenth workshop on Parallel and distributed simulation

May 2001

209 pages

ISBN:076951104X

Chairmen:
Rajive L. Bagrodia
Univ. of California at Los Angeles
,
Ewa Deelman
Information Sciences Institute
,
Philip A. Wilsey
Univ. of Cincinnati

Copyright © Copyright (c) 2001 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: 15 May 2001

Check for updates

Qualifiers

Article

Conference

PADS01

Sponsor:

SCS
SIGSIM
IEEE-CS\TCSIM

PADS01: ACM/IEEE/SCS 15th Workshop on Parallel and Distributed Simulation

May 15 - 18, 2001

California, Lake Arrowhead, USA

Acceptance Rates

PADS '01 Paper Acceptance Rate 21 of 31 submissions, 68%;

Overall Acceptance Rate 398 of 779 submissions, 51%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
265
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Perumalla KPerrone LStea GLiu JUhrmacher AVillén-Altamirano M(2010)μπProceedings of the 3rd International ICST Conference on Simulation Tools and Techniques10.4108/ICST.SIMUTOOLS2010.8692(1-6)Online publication date: 15-Mar-2010
https://dl.acm.org/doi/10.4108/ICST.SIMUTOOLS2010.8692
Naborskyy AFujimoto R(2007)Using Reversible Computation Techniques in a Parallel Optimistic Simulation of a Multi-Processor Computing SystemProceedings of the 21st International Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2007.31(179-188)Online publication date: 12-Jun-2007
https://dl.acm.org/doi/10.1109/PADS.2007.31

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents