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

Article

DSIM: scaling time warp to 1,033 processors

Authors:

Boleslaw K. SzymanskiAuthors Info & Claims

WSC '05: Proceedings of the 37th conference on Winter simulation

Pages 346 - 355

Published: 04 December 2005 Publication History

Abstract

This paper presents the design, implementation and performance of a Time Warp simulator, called DSIM, which targets clusters comprised of thousands of processors. DSIM employs a novel technique for GVT computation, called the Time Quantum GVT algorithm that requires no message acknowledgement, relies on constant-length messages and is efficient on clusters with large numbers of processors. Its implementation uses a technique called Local Fossil Collection to alleviate the overhead of memory reclamation and to support efficient event management. DSIM is also equipped with a simple programming interface to ease programming and debugging of simulations. Experimental results obtained on the PHOLD benchmark demonstrated that DSIM can process as many as 228 million events per second on 1033 processors.

References

[1]

Baezner, D., G. Lomow and B. Unger. 1994. Parallel simulation environment based on time warp. International Journal in Computer Simulation, 4(2): 183.

[2]

Baldwin, R., M. J. Chung and Y. Chung. 1991. Overlapping window algorithm for computing GVT in Time Warp. 11th International Conference on Distributed Computing Systems (Cat. No.91CH2996--7), 20--24 May 1991, 534--41, Arlington, TX: IEEE Comput. Soc. Press.

[3]

Bauer, H. and C. Sporrer. 1992. Distributed logic simulation and an approach to asynchronous GVT-calculation. Proceedings of the 1992 SCS Western Simulation MultiConference on Parallel and Distributed Simulation, 205--208, Newport Beach, CA: SCS.

[4]

Bellenot, S. 1990. Global Virtual Time Algorithms. Proceedings of the SCS Multiconference on Distributed Simulation, 122--127, San Diego, CA: Soc. for Computer Simulation Int.

[5]

Carothers, C. D., D. Bauer and S. Pearce. 2000. ROSS: a high-performance, low memory, modular Time Warp system, 53, Los Alamitos, CA: IEEE.

Digital Library

[6]

Carothers, C. D., R. M. Fujimoto and L. Yi-Bing. 1995. A case study in simulating PCS networks using time warp, 87, Lake Placid, NY: IEEE Comput. Soc. Press.

Digital Library

[7]

Carothers, C. D., K. S. Perumalla and R. M. Fujimoto. 1999. Efficient optimistic parallel simulations using reverse computation. ACM Transactions on Modeling and Computer Simulation 9(3): 224.

Digital Library

[8]

Choe, M. and C. Tropper. 1998. An Efficient GVT Computation Using Snapshots. CSMA 98, 33--43.

[9]

D'Souza, L. M., X. Fan and P. A. Wilsey. 1994. pGVT: an algorithm for accurate GVT estimation. Proceedings of 8th Workshop on Parallel and Distributed Simulation, 102--109, Edinburgh, UK: SCS.

Digital Library

[10]

Das, S., R. Fujimoto, K. Panesar, D. Allison and M. Hybinette. 1994. GTW: a time warp system for shared memory multiprocessors. Proceedings of Winter Simulation Conference, 1332--1339, M. S. Manivannan and J. D. Tew, Piscataway, NY: Institute of Electrical and Electronics Engineers.

Digital Library

[11]

Das, S. K. and F. Sarkar. 1995. A hypercube algorithm for GVT computation and its application in optimistic parallel simulation. Proceedings of Simulation Symposium, 51--60, Phoenix, AZ: IEEE Comput. Soc. Press.

Digital Library

[12]

Fujimoto, R. M. 1989. Time warp on a shared memory multiprocessor. Transactions of the Society for Computer Simulation 6(3): 211--239.

Digital Library

[13]

Fujimoto, R. M. 1990. Performance of time warp under synthetic workloads. Distributed Simulation. Proceedings of the SCS Multiconference, 23--28, San Diego, CA: SCS.

[14]

Fujimoto, R. M. and M. Hybinette. 1997. Computing global virtual time in shared-memory multiprocessors. ACM Transactions on Modeling and Computer Simulatio,. 7(4): 425--46.

Digital Library

[15]

Jefferson, D., B. Beckman, F. Wieland, L. Blume and M. Diloreto. Time warp operating system. Proceedings of the eleventh ACM Symposium on Operating systems principles, 77--93, ACM Press.

Digital Library

[16]

Jefferson, D. R. 1985. Virtual time. ACM Transactions on Programming Languages and Systems, 7(3): 404--25.

Digital Library

[17]

Kim, H. K. and J. Jean. 1996. Concurrency preserving partitioning (CPP) for parallel logic simulation, 98, Los Alamitos, CA: IEEE.

Digital Library

[18]

Martin, D. E., P. A. Wilsey, R. J. Hoekstra, E. R. Keiter, S. A. Hutchinson, T. V. Russo and L. J. Waters. 2003. Redesigning the WARPED simulation kernel for analysis and application development. Proceedings 36th Annual Simulation Symposium (ANSS-36 2003), 216--23, Orlando, FL: IEEE Comput. Soc.

Digital Library

[19]

Mascarenhas, E., F. Knop and V. Rego. 1995. ParaSol: a multithreaded system for parallel simulation based on mobile threads, 690, Piscataway, NJ: IEEE.

Digital Library

[20]

Mattern, F. 1993. Efficient algorithms for distributed snapshots and global virtual time approximation. Journal of Parallel and Distributed Computing 18(4): 423--34.

Digital Library

[21]

Perumalla, K. and R. Fujimoto. 2001. Virtual time synchronization over unreliable network transport. Proceedings 15th Workshop on Parallel and Distributed Simulation, 129, Lake Arrowehead, CA: IEEE Comput. Soc.

Digital Library

[22]

Preiss, B. R. 1989. The Yaddes Distributed Discrete Event Simulation Speficiation Lnaugage and Execution Environment. Proceedings of the SCS Multiconference on Distributed Simulation, 139--144.

[23]

Samadi, B. 1985. Distributed Simulation, Algorithms and Performance Analysis. Computer Science Department, University of California, Los Angeles.

[24]

Srinivasan, S. and P. F. Reynolds, Jr. 1993. Non-interfering GVT computation via asynchronous global reductions. Proceedings of 1993 Winter Simulation Conference, G. W. Evans, M. Mollaghasemi, E. C. Russell and W. E. Biles, eds. 740--749, Piscataway, NJ: Institute of Electrical and Electronics Engineers.

Digital Library

[25]

Steinman, J. S., C. A. Lee, L. F. Wilson and D. M. Nicol 1995. Global virtual time and distributed synchronization. Proceedings 9th Workshop on Parallel and Distributed Simulation (ACM/IEEE), 14--16 June 1995, 139--48, Lake Placid, NY, USA, IEEE Comput. Soc. Press.

Digital Library

[26]

Tomlinson, A. I. and V. K. Garg. 1993. An algorithm for minimally latent global virtual time. 1993 Workshop on Parallel and Distributed Simulation, 16--19 May 1993, 35--42, San Diego, CA, USA, SCS.

Digital Library

[27]

Vee, V.-Y. and W.-J. Hsu. 2002. Pal: a new fossil collector for time warp. Proceedings 16th Workshop on Parallel and Distributed Simulation, 35--42, Washington, DC, USA, IEEE Comput. Soc.

Digital Library

[28]

Wieland, F., L. Hawley, A. Feinberg, M. Di Loreto, L. Blume, P. Reiher, B. Beckman, P. Hontalas, S. Bellenot and D. Jefferson. 1989. Distributed combat simulation and time warp. The model and its performance, 14, Tampa, FL, USA, Publ by Soc for Computer Simulation Int, San Diego, CA, USA.

[29]

Xiao, Z., F. Gomes, B. Unger and J. Cleary. 1995. A fast asynchronous GVT algorithm for shared memory multiprocessor architectures. Proceedings 9th Workshop on Parallel and Distributed Simulation (ACM/IEEE), 203--208, Lake Placid, NY: IEEE Comput. Soc. Press.

Digital Library

Cited By

Williams BPonomarev DAbu-Ghazaleh NWilsey PCai WMeng TWilsey PJin K(2017)Performance Characterization of Parallel Discrete Event Simulation on Knights Landing ProcessorProceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3064911.3064929(121-132)Online publication date: 16-May-2017
https://dl.acm.org/doi/10.1145/3064911.3064929
Goldstein RBreslav SKhan ABarros FPrähofer HHu XDenil J(2016)A quantum of continuous simulated timeProceedings of the Symposium on Theory of Modeling & Simulation10.5555/2975389.2975390(1-8)Online publication date: 3-Apr-2016
https://dl.acm.org/doi/10.5555/2975389.2975390
Kunz GStoffers MLandsiedel OWehrle KGross J(2016)Parallel Expanded Event Simulation of Tightly Coupled SystemsACM Transactions on Modeling and Computer Simulation10.1145/283290926:2(1-26)Online publication date: 6-Jan-2016
https://dl.acm.org/doi/10.1145/2832909
Show More Cited By

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 ...
Time-parallel multi-delay logic simulation
TMS-DEVS '16: Proceedings of the Symposium on Theory of Modeling & Simulation

Multi-delay logic simulation may perform many logic simulations for each gate in the circuit during the simulation of a single input vector. Conventional event driven simulation will perform each of these gate-simulations as a separate operation, ...
Conservative DEVS: a novel protocol for parallel conservative simulation of DEVS and cell-DEVS models
SpringSim '10: Proceedings of the 2010 Spring Simulation Multiconference

We present a novel conservative algorithm based on the classical Chandy-Misra-Bryant (CMB) synchronization mechanism by extending DEVS abstract simulator to provide means for look-ahead computation and null-message distribution. We integrate this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WSC '05: Proceedings of the 37th conference on Winter simulation

December 2005

2769 pages

ISBN:0780395190

Sponsors

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

Winter Simulation Conference

Publication History

Published: 04 December 2005

Check for updates

Qualifiers

Article

Acceptance Rates

WSC '05 Paper Acceptance Rate 209 of 316 submissions, 66%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
153
Total Downloads

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

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Williams BPonomarev DAbu-Ghazaleh NWilsey PCai WMeng TWilsey PJin K(2017)Performance Characterization of Parallel Discrete Event Simulation on Knights Landing ProcessorProceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3064911.3064929(121-132)Online publication date: 16-May-2017
https://dl.acm.org/doi/10.1145/3064911.3064929
Goldstein RBreslav SKhan ABarros FPrähofer HHu XDenil J(2016)A quantum of continuous simulated timeProceedings of the Symposium on Theory of Modeling & Simulation10.5555/2975389.2975390(1-8)Online publication date: 3-Apr-2016
https://dl.acm.org/doi/10.5555/2975389.2975390
Kunz GStoffers MLandsiedel OWehrle KGross J(2016)Parallel Expanded Event Simulation of Tightly Coupled SystemsACM Transactions on Modeling and Computer Simulation10.1145/283290926:2(1-26)Online publication date: 6-Jan-2016
https://dl.acm.org/doi/10.1145/2832909
Perumalla KPark ATipparaju V(2014)Discrete Event Execution with One-Sided and Two-Sided GVT Algorithms on 216,000 Processor CoresACM Transactions on Modeling and Computer Simulation10.1145/261156124:3(1-25)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1145/2611561
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
Toscano LD'Angelo GMarzolla MFilinski AGrelck C(2012)Parallel discrete event simulation with ErlangProceedings of the 1st ACM SIGPLAN workshop on Functional high-performance computing10.1145/2364474.2364487(83-92)Online publication date: 15-Sep-2012
https://dl.acm.org/doi/10.1145/2364474.2364487
Holder ACarothers C(2011)Investigating the memory characteristics of a massively parallel time warp kernelProceedings of the Winter Simulation Conference10.5555/2431518.2431869(2953-2964)Online publication date: 11-Dec-2011
https://dl.acm.org/doi/10.5555/2431518.2431869
Guo SHu XSun Y(2009)Exploring spatial partition for parallel simulation of DEVS-FIREProceedings of the 2009 Summer Computer Simulation Conference10.5555/2349508.2349568(444-451)Online publication date: 13-Jul-2009
https://dl.acm.org/doi/10.5555/2349508.2349568
Wang BYao YHimmelspach JEwald RUhrmacher ADunkin AIngalls R(2009)Experimental analysis of logical process simulation algorithms in JAMES IIWinter Simulation Conference10.5555/1995456.1995619(1167-1179)Online publication date: 13-Dec-2009
https://dl.acm.org/doi/10.5555/1995456.1995619
Slavik MMahgoub IBadi AJefferson TFowler JIngalls R(2008)Dynamic entity distribution in parallel discrete event simulationProceedings of the 40th Conference on Winter Simulation10.5555/1516744.1516932(1061-1067)Online publication date: 7-Dec-2008
https://dl.acm.org/doi/10.5555/1516744.1516932
Show More Cited By

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