Article

Free access

Selecting the checkpoint interval in time warp simulation

Authors:

Yi-Bing Lin,

Bruno R. Preiss,

Wayne M. Loucks,

Edward D. LazowskaAuthors Info & Claims

PADS '93: Proceedings of the seventh workshop on Parallel and distributed simulation

Pages 3 - 10

https://doi.org/10.1145/158459.158460

Published: 01 July 1993 Publication History

PDF eReader

Abstract

In Time Warp parallel simulation, the state of each process must be saved (checkpointed) regularly in case a rollback is necessary. Although most existing Time Warp implementations checkpoint after every state transition, this is not necessary, and the checkpoint interval is in reality a tuning parameter of the simulation.

Lin and Lazowska[6] proposed a model to derive the optimal checkpoint interval by assuming that the rollback behavior of Time Warp is not affected by the frequency of checkpointing. An experimental study conducted by Preiss et al.[10] indicates that the behavior of rollback is affected by the frequency of checkpointing in general, and that the Lin-Lazowska model may not reflect the real situations in general.

This paper extends the Lin-Lazowska model to include the effect of the checkpoint interval on the rollback behavior. The relationship among the checkpoint interval, the rollback behavior, and the overhead associated with state saving and restoration is described. A checkpoint interval selection algorithm which quickly determines the optimal checkpoint interval during the execution of Time Warp simulation is proposed. Empirical results indicate that the algorithm converges quickly and always selects the optimal checkpoint interval.

References

[1]

Bellenot, S. State Skipping Performance with the Time Warp Operating Systems. Proc_ 5th Workshop on Parallel and Distributed Simulation, pages 53-64, January 1992.]]

Digital Library

Google Scholar

[2]

Fujimoto, R.M. Optimistic Approaches to Parallel Discrete Event Simulation. Transactions of the Society for Computer Simulation, 7(2):153- 191, June 1990.]]

Digital Library

Google Scholar

[3]

Fujimoto, R.M., Tsai, J.J., and Gopalakrishnan, G. Design and Evaluation of the Rollback Chip: Special Purpose Hardware for Time Warp. IEEE Transactions on Computer, 41(1):68-82, January 1992.]]

Digital Library

Google Scholar

[4]

Jefferson, D. Virtual Time. A CM Transactions on Programming Languages and Systems, 7(3):404-425, July 1985.]]

Digital Library

Google Scholar

[5]

Lin, Y.-B., and Lazowska, E.D. Optimality Considerations for Time Warp Parallel Simulation. Proc. 1990 SCS Mulliconference on Distributed Simulation, pages 29-34, January 1990.]]

Google Scholar

[6]

Lin, Y.-B., and Lazowska, E.D. Reducing the State Saving Overhead For Time Warp Parallel Simulation. Technical Report 90-02-03, Department of Computer Science and Engineering, University of Washington, 1990.]]

Google Scholar

[7]

Nicol, D.M. Parallel Discrete-Event Simulation of FCFS Stochastic Queueing Networks. Proc. A CM SIGPLAN Symposium on Parallel Programming: Experience with Applications, Languages, and Systems, pages 124-137, 1988.]]

Digital Library

Google Scholar

[8]

Preiss, B.R. The Yaddes Distributed Discrete Event Simulation Specification Language and Execution Environment. Proc. 1989 SCS Multiconference on Distributed Simulation, pages 139-144, 1989.]]

Google Scholar

[9]

Preiss, B.R. Performance of Discrete Event Simulation on a Multiprocessor Using Optimistic and Conservative Synchronization. Proc. International Conference on Parallel Processing, III:218- 222, 1990.]]

Google Scholar

[10]

Preiss, B.R., MacIntyre, I.D., and Loucks, W.M. On the Trade-off between Time and Space in Optimistic Parallel Discrete-Event Simulation. Proc. 5th Workshop on Parallel and Distributed Simulation, 1992.]]

Google Scholar

[11]

Young, J.W. A First Order Approximation to the Optimum Checkpoint Interval. Communications of the A CM, 17(17):530-531, September 1974.]]

Digital Library

Google Scholar

Cited By

View all

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
Jefferson DBarnes P(2023)Virtual Time III, Part 1: Unified Virtual Time Synchronization for Parallel Discrete Event SimulationACM Transactions on Modeling and Computer Simulation10.1145/350524832:4(1-29)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3505248
Suh W(2020)Graphical Analysis of Rollback Process in Ad Hoc Distributed Traffic SimulationApplied Sciences10.3390/app1101012111:1(121)Online publication date: 24-Dec-2020
https://doi.org/10.3390/app11010121
Show More Cited By

Index Terms

Selecting the checkpoint interval in time warp simulation
1. Computing methodologies
  1. Modeling and simulation
    1. Simulation support systems
      1. Simulation languages
    2. Simulation types and techniques
      1. Discrete-event simulation
      2. Massively parallel and high-performance simulations

Recommendations

A first order approximation to the optimum checkpoint interval

To avoid having to restart a job from the beginning in case of random failure, it is standard practice to save periodically sufficient information to enable the job to be restarted at the previous point at which information was saved. Such points are ...
Selecting the checkpoint interval in time warp simulation

In Time Warp parallel simulation, the state of each process must be saved (checkpointed) regularly in case a rollback is necessary. Although most existing Time Warp implementations checkpoint after every state transition, this is not necessary, and the ...
Effects of the checkpoint interval on time and space in time warp

Optimistically synchronized parallel discrete-event simulation is based on the use of communicating sequential processes. Optimistic synchronization means that the processes proceed under the assumption that a synchronized execution schedule is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PADS '93: Proceedings of the seventh workshop on Parallel and distributed simulation

July 1993

168 pages

ISBN:1565550552

DOI:10.1145/158459

Editors:
Rajive Bagrodia
Univ. of California, Los Angeles
,
David Jefferson
Univ. of California, Los Angeles

ACM SIGSIM Simulation Digest Volume 23, Issue 1
July 1993
164 pages
ISSN:0163-6103
DOI:10.1145/174134
Editors:
Rajive Bagrodia
Univ. of California, Los Angeles
,
David Jefferson
Univ. of California, Los Angeles
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PADS93

Sponsor:

SCS
SIGSIM
IEEE-CS\TCSIM

PADS93: Workshop on Parellel and Distributed Simulation

May 16 - 19, 1993

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 398 of 779 submissions, 51%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

117
Total Citations
View Citations
1,733
Total Downloads

Downloads (Last 12 months)115
Downloads (Last 6 weeks)25

Reflects downloads up to 08 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Jefferson DBarnes P(2023)Virtual Time III, Part 1: Unified Virtual Time Synchronization for Parallel Discrete Event SimulationACM Transactions on Modeling and Computer Simulation10.1145/350524832:4(1-29)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3505248
Suh W(2020)Graphical Analysis of Rollback Process in Ad Hoc Distributed Traffic SimulationApplied Sciences10.3390/app1101012111:1(121)Online publication date: 24-Dec-2020
https://doi.org/10.3390/app11010121
Peluso SDidona DQuaglia F(2017)Supports for transparent object-migration in PDES systemsJournal of Simulation10.1057/jos.2012.136:4(279-293)Online publication date: 19-Dec-2017
https://doi.org/10.1057/jos.2012.13
Gorur BImre KOguztuzun HYilmaz LWeinbub JBaboulin MThacker WPolok L(2016)Repast HPC with optimistic time managementProceedings of the 24th High Performance Computing Symposium10.22360/SpringSim.2016.HPC.046(1-9)Online publication date: 3-Apr-2016
https://dl.acm.org/doi/10.22360/SpringSim.2016.HPC.046
LaPre JGonsiorowski ECarothers CJenkins JCarns PRoss R(2015)Time warp state restoration via delta encodingProceedings of the 2015 Winter Simulation Conference10.5555/2888619.2888969(3025-3036)Online publication date: 6-Dec-2015
https://dl.acm.org/doi/10.5555/2888619.2888969
Fujimoto R(2015)Parallel and distributed simulationProceedings of the 2015 Winter Simulation Conference10.5555/2888619.2888624(45-59)Online publication date: 6-Dec-2015
https://dl.acm.org/doi/10.5555/2888619.2888624
Li ZCai WTurner SLi XDuong TGoh R(2015)Adaptive Resource Provisioning Mechanism in VEEs for Improving Performance of HLA-Based SimulationsACM Transactions on Modeling and Computer Simulation10.1145/271730926:1(1-25)Online publication date: 29-Jun-2015
https://dl.acm.org/doi/10.1145/2717309
LaPre JGonsiorowski ECarothers CJenkins JCarns PRoss R(2015)Time Warp state restoration via delta encoding2015 Winter Simulation Conference (WSC)10.1109/WSC.2015.7408406(3025-3036)Online publication date: Dec-2015
https://doi.org/10.1109/WSC.2015.7408406
Fujimoto R(2015)Parallel and distributed simulation2015 Winter Simulation Conference (WSC)10.1109/WSC.2015.7408152(45-59)Online publication date: Dec-2015
https://doi.org/10.1109/WSC.2015.7408152
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A first order approximation to the optimum checkpoint interval

Selecting the checkpoint interval in time warp simulation

Effects of the checkpoint interval on time and space in time warp