article

Free access

Adaptive checkpointing in Time Warp

Authors:

Robert Rönngren,

Rassul AyaniAuthors Info & Claims

ACM SIGSIM Simulation Digest, Volume 24, Issue 1

Pages 110 - 117

https://doi.org/10.1145/195291.182577

Published: 01 July 1994 Publication History

Abstract

In Time Warp optimistic discrete event simulation, there exists a need to occasionally save the states of the logical processes. The state saving often constitutes a substantial overhead. However it is not necessary to save each state of a logical process since states can be restored from earlier states by re-executing intermediate events. In this paper, we analyse the effects of doing the state saving less frequently and present a method that allows each logical process to adapt its state saving interval to its rollback behaviour. Experimental results indicate that the proposed method improves performance of the Time Warp system.

References

[1]

Ahmed, H. et al, "Impact of Event Scheduling on Performance of Time Warp Parallel Simulations", Proceedings of the 27th Annual Hawaii International Conference on System Sciences, pp 455-462, Vol II, 1994

[2]

Bauer H. et al, "Reducing Rollback Overhead in Time- Warp Based Distributed Simulation with optimized Incremental State Saving", Proceedings of the 26th Annual Simulation Symposium, pp. 12-20, March 1993

[3]

Bellenot S. "State Skipping Performance with the Time Warp Operating System",Proceedings of the 6th Workshop on Parallel and Distributed Simulation, pp. 33- 42, Vol 24, No 3, January 1992.

[4]

Fujimoto,R. et al. "Design and Evaluation of the Rollback Chip: Special Purpose Hardware for Time Warp", IEEE transactions on Computer, Vol 41, No. I, pp 53-64, January 1992

Digital Library

[5]

Fujimoto, R. "Time Warp on a Shared Memeory Multiprocessor", Transactions of the Society for Computer Simulation, Vol. 6, No. 3, pp. 211-239, July 1989.

Digital Library

[6]

Jeffersson, D. "Virtual Time", ACM trans, on Programming Languages and Systems Vol. 7, No. 3, pp. 404 - 425, Jul. 1985.

Digital Library

[7]

Jefferson, D. "Virtual Time II: Storage Management in Distributed Simulation," Proc. of the Ninth Annual ACM Symposium on Principles of Distributed Computing, pp. 75-89, August 1990.

Digital Library

[8]

Jones, D.W. "Concurrent Operations on Priority Queues", Comm. ACM Vol. 32, No. 1, pp. 132-137, Jan. 1989.

Digital Library

[9]

Kreyzig E. "Introduction to Mathematical Statistics", John Wiley & Sons, 1970

[10]

Lin Y. "Understanding the Limits of Optimistic and Conservative Parallel Smulation", PhD thesis, Dept. of Computer Science and Engineering, University of Washington, Tech. Report 90-08-02, August 1990

Digital Library

[11]

Lin Y. et al, "Selecting the Checkpoint Interval in Time Warp Simulation", Proceedings of the 7th workshop on Parallel and Distributed Simulation (PADS93) pp. 3-10, Vol 23, No 1, July 1993

Digital Library

[12]

Palaniswamy A. C. et al, "An Analythical Comparison of Periodic Checkpointing and Incremental State Saving", Proceedings of the 7th workshop on Parallel and Distributed Simulation (PADS93) pp. 127-134, Vol 23, No 1, July 1993

Digital Library

[13]

Palaniswamy A. C. et al, "Adaptive Checkpoint Intervals in an Optimistically Synchronized Parallel Digital System Simulator", Proceedings IFIP TC 10/WG 10.5 IntnI Conf. on Very Large Scale Integration (VLSI93) pp 353-362, September 1993

Digital Library

[14]

Preiss B. et aI, "On the Trade-off Between Time and Space in Optimistic Parallel Discrete-Event Simulation", Proceedings of the 6th Workshop on Parallel and Distributed Simulation, pp. 33-42, Vol 24, No 3, 1992

[15]

Reiher P. et al, "Limitations of Optimism in the Time Warp Operating System", Proceedings of the 1989 Winter Simulation Conference, pp 765-769

Digital Library

[16]

Reynolds P. F., "A spectrum of options for Parallel Simulation", Proceedings of the 1988 Winter Simulation Conference, pp 325-332

Digital Library

[17]

Sleator D. D. and Tarjan R. E., "Self-Adjusting Binary Search Trees", Journal of the ACM Vol. 32, No. 3, pp. 652-686, Jul. 1985.

Digital Library

[18]

"Guide to Parallel Programming on Sequent Computer Systems", Prentice-Hall, ISBN 0-13-370446-7, 1989.

Cited By

Görür Bİmre KOğuztüzün HYilmaz L(2019)Predetermined Rollbacks: An extension to Time Warp for spatially parallel agent-based simulationSimulation Modelling Practice and Theory10.1016/j.simpat.2019.04.00895(60-77)Online publication date: Sep-2019
https://doi.org/10.1016/j.simpat.2019.04.008
Van Tendeloo YVan Mierlo SVangheluwe H(2017)Time- and space-conscious omniscient debugging of parallel DEVSProceedings of the Symposium on Theory of Modeling & Simulation10.5555/3108905.3108908(1-12)Online publication date: 23-Apr-2017
https://dl.acm.org/doi/10.5555/3108905.3108908
Görür Bİmre KOğuztüzün HYilmaz L(2017)Improving the performance of optimistic time management mechanism with sub-state savingProceedings of the 25th High Performance Computing Symposium10.5555/3108096.3108107(1-12)Online publication date: 23-Apr-2017
https://dl.acm.org/doi/10.5555/3108096.3108107
Show More Cited By

Index Terms

Adaptive checkpointing in Time Warp
1. Computing methodologies
  1. Modeling and simulation
    1. Simulation types and techniques
2. Software and its engineering
  1. Software organization and properties
    1. Extra-functional properties
      1. Software fault tolerance
        Checkpoint / restart

Recommendations

Adaptive checkpointing in Time Warp
PADS '94: Proceedings of the eighth workshop on Parallel and distributed simulation

In Time Warp optimistic discrete event simulation, there exists a need to occasionally save the states of the logical processes. The state saving often constitutes a substantial overhead. However it is not necessary to save each state of a logical ...
An Analytical Model for Hybrid Checkpointing in Time Warp Distributed Simulation

The Time Warp distributed simulation algorithm uses checkpointing to save process states after certain event executions for later recovery at the time of a rollback. Two main techniques have been used for checkpointing: periodic state saving and ...
Event scheduling schemes for time warp on distributed systems
WSC '96: Proceedings of the 28th conference on Winter simulation

In this paper we present event sensitive state saving as a novel idea for sparse state saving in Time Warp synchronized parallel discrete event simulations. This state saving model is aimed at efficient simulation of models where the execution time or ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGSIM Simulation Digest

ACM SIGSIM Simulation Digest Volume 24, Issue 1

July 1994

192 pages

ISSN:0163-6103

DOI:10.1145/195291

Editors:
D. K. Arvind
Univ. of Edinburgh, Edinburgh, Scotland, UK
,
Rajive Bagrodia
Univ. of California, Los Angeles
,
Jason Yi-Bing Lin
Bellcore, Morristown, NJ

Issue’s Table of Contents

PADS '94: Proceedings of the eighth workshop on Parallel and distributed simulation
August 1994
196 pages
ISBN:1565550277
DOI:10.1145/182478
Editors:
D. K. Arvind
Univ. of Edinburgh, Scotland, UK
,
Rajive Bagrodia
Univ. of California, Los Angeles
,
Jason Yi-Bing Lin
Bellcore

Copyright © 1994 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1994

Published in SIGSIM Volume 24, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

107
Total Citations
View Citations
397
Total Downloads

Downloads (Last 12 months)61
Downloads (Last 6 weeks)18

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Görür Bİmre KOğuztüzün HYilmaz L(2019)Predetermined Rollbacks: An extension to Time Warp for spatially parallel agent-based simulationSimulation Modelling Practice and Theory10.1016/j.simpat.2019.04.00895(60-77)Online publication date: Sep-2019
https://doi.org/10.1016/j.simpat.2019.04.008
Van Tendeloo YVan Mierlo SVangheluwe H(2017)Time- and space-conscious omniscient debugging of parallel DEVSProceedings of the Symposium on Theory of Modeling & Simulation10.5555/3108905.3108908(1-12)Online publication date: 23-Apr-2017
https://dl.acm.org/doi/10.5555/3108905.3108908
Görür Bİmre KOğuztüzün HYilmaz L(2017)Improving the performance of optimistic time management mechanism with sub-state savingProceedings of the 25th High Performance Computing Symposium10.5555/3108096.3108107(1-12)Online publication date: 23-Apr-2017
https://dl.acm.org/doi/10.5555/3108096.3108107
Pellegrini A(2016)Optimizing memory management for optimistic simulation with reinforcement learning2016 International Conference on High Performance Computing & Simulation (HPCS)10.1109/HPCSim.2016.7568312(26-33)Online publication date: Jul-2016
https://doi.org/10.1109/HPCSim.2016.7568312
Pellegrini AQuaglia F(2014)Programmability and Performance of Parallel ECS-Based Simulation of Multi-agent Exploration ModelsRevised Selected Papers, Part I, of the Euro-Par 2014 International Workshops on Parallel Processing - Volume 880510.1007/978-3-319-14325-5_34(395-406)Online publication date: 25-Aug-2014
https://dl.acm.org/doi/10.1007/978-3-319-14325-5_34
Santoro AQuaglia F(2007)Multiprogrammed non-blocking checkpoints in support of optimistic simulation on myrinet clustersJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2007.01.00353:9(659-676)Online publication date: 1-Sep-2007
https://dl.acm.org/doi/10.1016/j.sysarc.2007.01.003
Gomes FUnger BCleary J(1996)Language based state saving extensions for optimistic parallel simulationProceedings of the 28th conference on Winter simulation10.1145/256562.256812(794-800)Online publication date: 8-Nov-1996
https://dl.acm.org/doi/10.1145/256562.256812
Fujimoto R(2024)Development of the parallel and distributed simulation fieldSIMULATION10.1177/00375497241261407100:12(1197-1223)Online publication date: 2-Dec-2024
https://doi.org/10.1177/00375497241261407
Marotta RMontesano FPellegrini AQuaglia F(2023)Incremental Checkpointing of Large State Simulation Models with Write-Intensive Events via Memory Update Correlation on Buddy Pages2023 IEEE/ACM 27th International Symposium on Distributed Simulation and Real Time Applications (DS-RT)10.1109/DS-RT58998.2023.00014(40-47)Online publication date: 4-Oct-2023
https://doi.org/10.1109/DS-RT58998.2023.00014
Tennison JUesbeck PGiudice NStefik ASmith DGorlewicz J(2020)Establishing Vibration-Based Tactile Line Profiles for Use in Multimodal GraphicsACM Transactions on Applied Perception10.1145/338345717:2(1-14)Online publication date: 18-May-2020
https://dl.acm.org/doi/10.1145/3383457
Show More Cited By

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 Issue’s Table of Contents