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

research-article

Transparently Mixing Undo Logs and Software Reversibility for State Recovery in Optimistic PDES

Authors:

Davide Cingolani,

Alessandro Pellegrini,

Francesco QuagliaAuthors Info & Claims

SIGSIM PADS '15: Proceedings of the 3rd ACM SIGSIM Conference on Principles of Advanced Discrete Simulation

Pages 211 - 222

https://doi.org/10.1145/2769458.2769482

Published: 10 June 2015 Publication History

Abstract

The rollback operation is a fundamental building block to support the correct execution of a speculative Time Warp-based Parallel Discrete Event Simulation. In the literature, several solutions to reduce the execution cost of this operation have been proposed, either based on the creation of a checkpoint of previous simulation state images, or on the execution of negative copies of simulation events which are able to undo the updates on the state. In this paper, we explore the practical design and implementation of a state recoverability technique which allows to restore a previous simulation state either relying on checkpointing or on the reverse execution of the state updates occurred while processing events in forward mode. Differently from other proposals, we address the issue of executing backward updates in a fully-transparent and event granularity-independent way, by relying on static software instrumentation (targeting the x86 architecture and Linux systems) to generate at runtime reverse update code blocks (not to be confused with reverse events, proper of the reverse computing approach). These are able to undo the effects of a forward execution while minimizing the cost of the undo operation. We also present experimental results related to our implementation, which is released as free software and fully integrated into the open source ROOT-Sim (ROme OpTimistic Simulator) package. The experimental data support the viability and effectiveness of our proposal.

References

[1]

GDB: The GNU Project Debugger. http://www.gnu.org/software/gdb/ (last accessed: May 11th, 2015).

[2]

V. Bala, E. Duesterwald, and S. Banerjia. Dynamo: A transparent dynamic optimization system. ACM SIGPLAN Notices, 35(5):1--12, 2000.

Digital Library

[3]

P. D. Barnes, Jr., C. D. Carothers, D. R. Jefferson, and J. M. LaPre. Warp speed: executing Time Warp on 1,966,080 cores. In Proceedings of the 2013 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation (SIGSIM-PADS), pages 327--336. ACM Press. Montréal, Canada -- May 19-22, 2013.

Digital Library

[4]

S. Bellenot. State skipping performance with the Time Warp operating system. In Proceedings of the 6th Workshop on Parallel and Distributed Simulation (PADS), pages 53--64. Society for Computer Simulation International. Newport Beach, California -- January 20-22, 1992.

[5]

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

Digital Library

[6]

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

Digital Library

[7]

V. Cortellessa and F. Quaglia. A checkpointing--recovery scheme for Time Warp parallel simulation. Parallel Computing, 27(9):1226--1252, 2000.

Digital Library

[8]

S. R. Das, R. M. Fujimoto, K. Panesar, D. Allison, and M. Hybinette. GTW: a Time Warp system for shared memory multiprocessors. In Proceedings of the Winter Simulation Conference (WSC), pages 1332--1339. Society for Computer Simulation International. Orlando, FL, USA -- December 11-14, 1994.

Digital Library

[9]

J. Fleischmann and P. A. Wilsey. Comparative analysis of periodic state saving techniques in Time Warp simulators. In Proceedings of the 9th Workshop on Parallel and Distributed Simulation (PADS), pages 50--58. IEEE Computer Society. Lake Placid, NY, USA -- June 13-16, 1995.

Digital Library

[10]

S. Franks, F. Gomes, B. Unger, and J. Cleary. State saving for interactive optimistic simulation. In Proceedings of the 11th Workshop on Parallel and Distributed Simulation (PADS), pages 72--79. IEEE Computer Society. Lockenhaus, Austria -- June 10-13, 1997.

Digital Library

[11]

R. M. Fujimoto. Parallel discrete event simulation. Communications of the ACM, 33(10):30--53, 1990.

Digital Library

[12]

D. R. Jefferson. Virtual Time. ACM Transactions on Programming Languages and System, 7(3):404--425, 1985.

Digital Library

[13]

S. Kandukuri and S. Boyd. Optimal power control in interference-limited fading wireless channels with outage-probability specifications. IEEE Transactions on Wireless Communications, 1(1):46--55, 2002.

Digital Library

[14]

J. M. LaPre, E. J. Gonsiorowski, and C. D. Carothers. Lorain: A step closer to the PDES 'holy grail'. In Proceedings of the 2nd ACM SIGSIM Conference on Principles of Advanced Discrete Simulation (SIGSIM-PADS), pages 3--14. ACM Press. Denver, CO, USA -- May 18-21, 2014.

Digital Library

[15]

Y.-B. Lin and E. D. Lazowska. Reducing the state saving overhead for Time Warp parallel simulation. Tech. Rep. 90-02-03, Department of Computer Science and Engineering,University of Washington, Seattle, Feb. 1990.

[16]

A. C. Palaniswamy and P. A. Wilsey. An analytical comparison of periodic checkpointing and incremental state saving. In Proceedings of the 7th Workshop on Parallel and Distributed Simulation (PADS), pages 127--134. ACM Press. San Diego, CA, USA -- May 16-19, 1993.

Digital Library

[17]

A. Pellegrini. Hijacker: Efficient static software instrumentation with applications in high performance computing. In Proceedings of the 2013 International Conference on High Performance Computing & Simulation (HPCS), pages 650--655. IEEE Computer Society. Helsinki, Finland -- July 1-5, 2013.

[18]

A. Pellegrini and F. Quaglia. The ROme OpTimistic Simulator: A tutorial. In Proceedings of the 1st Workshop on Parallel and Distributed Agent-Based Simulations (PADABS). LNCS, Springer-Verlag Berlin Heidelberg. Aachen, Germany -- August 26-30, 2013.

[19]

A. Pellegrini, R. Vitali, and F. Quaglia. Di-DyMeLoR: Logging only dirty chunks for efficient management of dynamic memory based optimistic simulation objects. In Proceedings of the 23rd Workshop on Principles of Advanced and Distributed Simulation (PADS), pages 45--53. IEEE Computer Society. Lake Placid, NY, USA -- June 22-25, 2009.

Digital Library

[20]

A. Pellegrini, R. Vitali, and F. Quaglia. The ROme OpTimistic Simulator: Core internals and programming model. In Proceedings of the 4th International ICST Conference on Simulation Tools and Techniques (SIMUTools), pages 96--98. ICST. Barcelona, Spain -- March 22-24, 2011.

Digital Library

[21]

A. Pellegrini, R. Vitali, and F. Quaglia. Autonomic state management for optimistic simulation platforms. IEEE Transactions on Parallel and Distributed Systems (preprint available), May 2014.

[22]

B. R. Preiss, W. M. Loucks, and D. MacIntyre. Effects of the checkpoint interval on time and space in Time Warp. ACM Transactions on Modeling and Computer Simulation, 4(3):223--253, 1994.

Digital Library

[23]

F. Qin, C. Wang, Z. Li, H.-s. Kim, Y. Zhou, and Y. Wu. LIFT: A low-overhead practical information flow tracking system for detecting security attacks. In Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 135--148. IEEE Computer Society. Orlando, FL, USA -- December 9-13, 2006.

Digital Library

[24]

F. Quaglia. A cost model for selecting checkpoint positions in Time Warp parallel simulation. IEEE Transactions on Parallel and Distributed Systems, 12(4):346--362, 2001.

Digital Library

[25]

F. Quaglia and A. Santoro. Non-blocking checkpointing for optimistic parallel simulation: Description and an implementation. IEEE Transactions on Parallel and Distributed Systems, 14(6):593--610, 2003.

Digital Library

[26]

R. Rönngren and R. Ayani. Adaptive checkpointing in Time Warp. In Proceedings of the 8th Workshop on Parallel and Distributed Simulation (PADS), pages 110--117. Society for Computer Simulation. Edinburgh, Scotland -- July 6-8, 1994.

Digital Library

[27]

R. Rönngren, M. Liljenstam, R. Ayani, and J. Montagnat. Transparent incremental state saving in Time Warp parallel discrete event simulation. In Proceedings of the 10th Workshop on Parallel and Distributed Simulation (PADS), pages 70--77. IEEE Computer Society. Philadelphia, PA, USA -- May 22-24, 1996.

Digital Library

[28]

S. Skold and R. Rönngren. Event sensitive state saving in Time Warp parallel discrete event simulation. In Proceedings of the Winter Simulation Conference (WSC), pages 653--660. Society for Computer Simulation. Coronado, CA, USA -- December 8-11, 1996.

Digital Library

[29]

H. Soliman and A. Elmaghraby. An analytical model for hybrid checkpointing in Time Warp distributed simulation. IEEE Transactions on Parallel and Distributed Systems, 9(10):947--951, 1998.

Digital Library

[30]

J. S. Steinman. SPEEDES--a multiple- synchronization environment for parallel discrete-event simulation. International Journal in Computer Simulation, 2:251--286, 1992.

[31]

J. S. Steinman. Incremental state saving in SPEEDES using C plus plus. In Proceedings of the Winter Simulation Conference (WSC), pages 687--696. Society for Computer Simulation. Los Angeles, CA, USA -- December 12-15, 1993.

Digital Library

[32]

R. Toccaceli and F. Quaglia. DyMeLoR: Dynamic Memory Logger and Restorer library for optimistic simulation objects with generic memory layout. In Proceedings of the 22nd Workshop on Principles of Advanced and Distributed Simulation (PADS), pages 163--172. IEEE Computer Society. Rome, Italy -- June 3-6, 2008.

Digital Library

[33]

R. Vitali, A. Pellegrini, and F. Quaglia. Towards symmetric multi-threaded optimistic simulation kernels. In Proceedings of the 26th Workshop on Principles of Advanced and Distributed Simulation (PADS), pages 211--220. IEEE Computer Society. Zhangjiajie, China -- July 15-19, 2012.

Digital Library

[34]

R. Wahbe, S. Lucco, and S. L. Graham. Practical data breakpoints: Design and implementation. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 1--12. ACM Press. Albuquerque, NM, USA -- June 21-25, 1993 .

Digital Library

[35]

D. West and K. Panesar. Automatic incremental state saving. In Proceedings of the 10th Workshop on Parallel and Distributed Simulation (PADS), pages 78--85. IEEE Computer Society. Philadelphia, PA, USA -- May 22-24, 1996.

Digital Library

[36]

Q. Zhao, R. Rabbah, S. Amarasinghe, L. Rudolph, and W.-F. Wong. How to do a million watchpoints: Efficient debugging using dynamic instrumentation. In L. Hendren, editor, Compiler Construction, LNCS, Springer-Verlag Berlin Heidelberg. Budapest, Hungary -- March 29--April 6, 2008.

Digital Library

Cited By

Schordan MOppelstrup TThomsen MGlück R(2020)Reversible Languages and Incremental State Saving in Optimistic Parallel Discrete Event SimulationReversible Computation: Extending Horizons of Computing10.1007/978-3-030-47361-7_9(187-207)Online publication date: 12-May-2020
https://doi.org/10.1007/978-3-030-47361-7_9
Bhardwaj RTummala GRamalingam GRamjee RSinha P(2018)AutoCalibACM Transactions on Sensor Networks10.1145/319966714:3-4(1-27)Online publication date: 27-Nov-2018
https://dl.acm.org/doi/10.1145/3199667
Fierro GCuller D(2018)Design and Analysis of a Query Processor for BrickACM Transactions on Sensor Networks10.1145/319966614:3-4(1-25)Online publication date: 27-Nov-2018
https://dl.acm.org/doi/10.1145/3199666
Show More Cited By

Index Terms

Transparently Mixing Undo Logs and Software Reversibility for State Recovery in Optimistic PDES
1. Computing methodologies
  1. Modeling and simulation
    1. 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. Compilers
      1. Source code generation

Recommendations

Transparently Mixing Undo Logs and Software Reversibility for State Recovery in Optimistic PDES
Special Issue on PADS 2015

The Time Warp synchronization protocol for Parallel Discrete Event Simulation (PDES) is universally considered a viable solution to exploit the intrinsic simulation model parallelism and to provide model execution speedup. Yet it leads the PDES system ...
Dealing with Reversibility of Shared Libraries in PDES
SIGSIM-PADS '17: Proceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation

State recoverability is a crucial aspect of speculative Time Warp-based Parallel Discrete Event Simulation. In the literature, we can identify three major classes of techniques to support the correct restoration of a previous simulation state upon the ...
Time-Sharing Time Warp via Lightweight Operating System Support
SIGSIM PADS '15: Proceedings of the 3rd ACM SIGSIM Conference on Principles of Advanced Discrete Simulation

The order according to which the different tasks are carried out within a Time Warp platform has a direct impact on performance, given that event processing is speculative, thus being subject to the possibility of being rolled-back. It is typically ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSIM PADS '15: Proceedings of the 3rd ACM SIGSIM Conference on Principles of Advanced Discrete Simulation

June 2015

300 pages

ISBN:9781450335836

DOI:10.1145/2769458

General Chair:
Simon J.E. Taylor
Brunel University London, UK
,
Program Chairs:
Navonil Mustafee
University of Exeter, UK
,
Young-Jun Son
University of Arizona, USA

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGSIM-PADS '15

Sponsor:

SIGSIM

SIGSIM-PADS '15: SIGSIM Principles of Advanced Discrete Simulation

June 10 - 12, 2015

London, United Kingdom

Acceptance Rates

SIGSIM PADS '15 Paper Acceptance Rate 35 of 60 submissions, 58%;

Overall Acceptance Rate 398 of 779 submissions, 51%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
79
Total Downloads

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

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Schordan MOppelstrup TThomsen MGlück R(2020)Reversible Languages and Incremental State Saving in Optimistic Parallel Discrete Event SimulationReversible Computation: Extending Horizons of Computing10.1007/978-3-030-47361-7_9(187-207)Online publication date: 12-May-2020
https://doi.org/10.1007/978-3-030-47361-7_9
Bhardwaj RTummala GRamalingam GRamjee RSinha P(2018)AutoCalibACM Transactions on Sensor Networks10.1145/319966714:3-4(1-27)Online publication date: 27-Nov-2018
https://dl.acm.org/doi/10.1145/3199667
Fierro GCuller D(2018)Design and Analysis of a Query Processor for BrickACM Transactions on Sensor Networks10.1145/319966614:3-4(1-25)Online publication date: 27-Nov-2018
https://dl.acm.org/doi/10.1145/3199666
Finley BSoikkeli T(2018)Mobile Device Type SubstitutionProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/31917402:1(1-20)Online publication date: 26-Mar-2018
https://dl.acm.org/doi/10.1145/3191740
Fan XGong WLiu J(2018)TagFree Activity Identification with RFIDsProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/31917392:1(1-23)Online publication date: 26-Mar-2018
https://dl.acm.org/doi/10.1145/3191739
Chun KBhattacharya SThomaz E(2018)Detecting Eating Episodes by Tracking Jawbone Movements with a Non-Contact Wearable SensorProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/31917362:1(1-21)Online publication date: 26-Mar-2018
https://dl.acm.org/doi/10.1145/3191736
Stoffers MSchemmel DDustmann OWehrle K(2018)On Automated Memoization in the Field of Simulation Parameter StudiesACM Transactions on Modeling and Computer Simulation10.1145/318631628:4(1-25)Online publication date: 24-Sep-2018
https://dl.acm.org/doi/10.1145/3186316
Schordan MOppelstrup TJefferson DBarnes P(2018)Generation of Reversible C++ Code for Optimistic Parallel Discrete Event SimulationNew Generation Computing10.1007/s00354-018-0038-236:3(257-280)Online publication date: 27-Jul-2018
https://doi.org/10.1007/s00354-018-0038-2
Lanese I(2018)From Reversible Semantics to Reversible DebuggingReversible Computation10.1007/978-3-319-99498-7_2(34-46)Online publication date: 22-Aug-2018
https://doi.org/10.1007/978-3-319-99498-7_2
Bruno ROliveira LFerreira P(2017)NG2C: pretenuring garbage collection with dynamic generations for HotSpot big data applicationsACM SIGPLAN Notices10.1145/3156685.309227252:9(2-13)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3156685.3092272
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