Article

Eliminating remote message passing in optimistic simulation

Authors:

David W. Bauer, Jr.,

Christopher D. CarothersAuthors Info & Claims

WSC '06: Proceedings of the 38th conference on Winter simulation

Pages 995 - 1003

Published: 03 December 2006 Publication History

Abstract

This paper introduces an algorithm for parallel simulation capable of executing the critical path without a priori knowledge of the model being executed. This algorithm is founded on the observation that each initial event in a model causes a stream of events to be generated for execution. By focusing on the parallelization of event streams, rather than logical processes, we have created a new simulation engine optimized for large scale models (i.e., models with 1 million LPs or more).

References

[1]

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

[2]

Brown, R. 1988. Calendar queues: a fast O(1) priority queue implementation for the simulation event set problem. Communications of the ACM 31(10):1220--1227.

Digital Library

[3]

Cai, W. T., and S. J. Turner. 1990. An algorithm for distributed discrete event simulation - the carrier null message approach. In Proceedings of the SCS Multiconference on Distributed Simulation, 3--8.

[4]

Carothers, C. D., D. Bauer, and S. Pearce. 2002. Ross: a high-performance, low memory, modular time warp system. Journal of Parallel and Distributed Computing.

[5]

Carothers, C. D., K. S. Perumalla, and R. M. Fujimoto. 1999. The effect of state-saving in optimistic simulation on a cache-coherent non-uniform memory access architecture. In Proceedings of the 1999 Winter Simulation Conference.

Digital Library

[6]

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

[7]

Das, S., R. M. Fujimoto, K. Panesar, D. Allison, and M. Hybinette. 1994. GTW: a time warp simulator for shared memory multiprocessors. In Proceedings of the 1994 Winter Simulation Conference, 1332--1339.

Digital Library

[8]

Fujimoto, R. M. 1990. Parallel discrete event simulation. Communications of the ACM 33:31--52.

Digital Library

[9]

Fujimoto, R. M. 1990. Performance of time warp under synthetic workload. In Proceedings of the SCS Multiconference on Distributed Simulation, 22:1.

[10]

Fujimoto, R. M. 2000. Parallel and distributed simulation systems. In Wiley Series on Parallel and Distributed Computing, 51--95. Wiley-Interscience.

[11]

Jefferson, D. R., and H. Sowizral. 1982. Fast concurrent simulation using the time warp mechanism. Technical Report N-1906-AF, RAND Corporation.

[12]

Lamport, L. 1978. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM 21:558--565.

Digital Library

[13]

Lamport, L. 1979. How to make a multiprocessor compute that correctly executes multiprocess programs. IEEE Transactions on Computers 28(9):690--691.

Digital Library

[14]

L'Ecuyer, P., and T. H. Andres. 1997. A random number generator based on the combination of four LCGs. Mathematics of Computer Simulation 44(1):99--107.

Digital Library

[15]

Lin, Y. B. 1992. Parallelism analyzers for parallel discrete event simulation. Transactions on Modeling and Computer Simulation (TOMACS) 2(3).

Digital Library

[16]

Misra, J. 1986. Distributed discrete event simulation. Proceedings of the ACM Computing Survey 18:39--65.

Digital Library

[17]

Nicol, D., and J. Liu. 2002. Composite synchronization for parallel distributed event simulation. IEEE Transactions on Parallel and Distributed Systems 13(5).

Digital Library

[18]

Nicol, D. M. 1988. Parallel discrete-event simulation of FCFS stochastic queueing networks. SIGPLAN Notice 23:124--137.

Digital Library

[19]

Prasad, S. K., and B. Naquib. 1995. Effectiveness of global event queues in rollback reduction and dynamic load balancing in optimistic discrete event simulation. In Proceedings of the 9th Workshop on Parallel and Distributed Simulation. 187--190. Lake Placid, NY.

Digital Library

[20]

Prasad, S. K., S. Sawant, B. Naqib, and D. Harsch. 1994. Performance of parallel heap compared with parallelized calendar queue and conscurrent heap on a shared memory computer. Technical Report Jan-9-94-1, Department of Mathematics and Computer Science, Georgia State University, Atlanta, GA.

[21]

Preiss, B. R. 1989. The Yaddes distributed discrete event simulation specification language and execution environments. In Proceedings of the SCS Multiconference on Distributed Simulation, Volume 21, 139--144.

[22]

Reynolds, P. F., Jr. 1988. A spectrum of options for parallel simulation. In Proceedings of the 1988 Winter Simulation Conference, 325--332.

Digital Library

[23]

Riley, G. F. 2003. Large-scale network simulations with GTNetS. In Proceedings of the 2003 Winter Simulation Conference, 676--684.

Digital Library

[24]

Srinivasan, S., and P. F. Reynolds. 1998. Elastic time. ACM Transactions on Modeling and Computer Simulation (TOMACS).

Digital Library

[25]

Szymanski, B., Y. Liu, and R. Gupta. 2003. Parallel network simulation under distributed Genesis. In Proceedings of the 17th Workshop on Parallel and Distributed Simulation, 61.

Digital Library

[26]

Uspensky, J. V. 1937. Introduction to mathematical probability (page 18). McGraw-Hill.

[27]

Wikipedia. 2006. HyperTransport. <http://en.wikipedia.org/wiki/Hypertransport>.

[28]

Zhou, S., W. Cai, S. J. Turner, and F. Lee. 2002. Critical causality in distributed virtual environments. In Proceedings of the 16th Workshop on Parallel and Distributed Simulation (PADS '02), 53--59.

Digital Library

[29]

Zimmerman, D. M., and M. Chandy. 2005. A parallel algorithm for correlating event streams. In Proceedings of the International Parallel and Distributed Processing Symposium.

Digital Library

Cited By

Barnes PCarothers CJefferson DLaPre JLoper MWainer G(2013)Warp speedProceedings of the 1st ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/2486092.2486134(327-336)Online publication date: 19-May-2013
https://dl.acm.org/doi/10.1145/2486092.2486134
Bauer DPage E(2007)An Approach for Incorporating Rollback through Perfectly Reversible Computation in a Stream SimulatorProceedings of the 21st International Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2007.13(171-178)Online publication date: 12-Jun-2007
https://dl.acm.org/doi/10.1109/PADS.2007.13

Eliminating remote message passing in optimistic simulation
1. General and reference
  1. Cross-computing tools and techniques

Recommendations

Optimistic simulation of parallel message-passing applications
PADS '01: Proceedings of the fifteenth workshop on Parallel and distributed simulation

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

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

WSC '06: Proceedings of the 38th conference on Winter simulation

December 2006

2429 pages

ISBN:1424405017

Editors:
L. Felipe Perrone
Bucknell University
,
Barry G. Lawson
University of Richmond
,
Jason Liu
Colorado School of Mines
,
Frederick P. Wieland
Sensis Corporation
,
General Chair:
David Nicol
University of Illinois, Urbana-Champaign
,
Program Chair:
Richard Fujimoto
College of Computing, Georgia Tech

Sponsors

IIE: Institute of Industrial Engineers
ASA: American Statistical Association
IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
IEEE-CS\DATC: The IEEE Computer Society
SIGSIM: ACM Special Interest Group on Simulation and Modeling
NIST: National Institute of Standards and Technology
(SCS): The Society for Modeling and Simulation International
INFORMS-CS: Institute for Operations Research and the Management Sciences-College on Simulation

Publisher

Winter Simulation Conference

Publication History

Published: 03 December 2006

Check for updates

Qualifiers

Article

Conference

WSC06

Sponsor:

IIE
ASA
IEICE ESS
IEEE-CS\DATC
SIGSIM
NIST
(SCS)
INFORMS-CS

WSC06: Winter Simulation Conference 2006

December 3 - 6, 2006

California, Monterey

Acceptance Rates

WSC '06 Paper Acceptance Rate 177 of 252 submissions, 70%;

Overall Acceptance Rate 3,413 of 5,075 submissions, 67%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
123
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Barnes PCarothers CJefferson DLaPre JLoper MWainer G(2013)Warp speedProceedings of the 1st ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/2486092.2486134(327-336)Online publication date: 19-May-2013
https://dl.acm.org/doi/10.1145/2486092.2486134
Bauer DPage E(2007)An Approach for Incorporating Rollback through Perfectly Reversible Computation in a Stream SimulatorProceedings of the 21st International Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2007.13(171-178)Online publication date: 12-Jun-2007
https://dl.acm.org/doi/10.1109/PADS.2007.13

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.

Figures

Tables

Media

View Table of Conten