research-article

An Analytical Model for Hybrid Checkpointing in Time Warp Distributed Simulation

Authors:

Hussam M. Soliman,

Adel Said ElmaghrabyAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 9, Issue 10

Pages 947 - 951

https://doi.org/10.1109/71.730524

Published: 01 October 1998 Publication History

Publisher Site

Abstract

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 incremental state saving. The former technique introduces large overheads in reconstructing a desired state by coasting forward from an earlier checkpointed state if the computational granularity is large. The latter technique also has large overheads in applications with large rollback distances. A hybrid checkpointing technique is proposed which uses both periodic and incremental state saving simultaneously in such a way that it reduces checkpointing time overheads. A detailed analytical model is developed for the hybrid technique, and comparisons are made using similar analytical models with periodic and incremental state saving techniques. Results show that when the system parameters are chosen to represent large and complex simulated systems, the hybrid approach has less checkpointing time overhead than the other two techniques.

References

[1]

H. Bauer and C. Sporrer, "Reducing Rollback Overhead in Time-Warp Based Distributed Simulation with Optimized Incremental State Saving," Proc. 26th Ann. Simulation Symp., pp. 12-20, 1993.

Google Scholar

[2]

S. Bellenot, "State Skipping Performance with the Time Warp Operating System," Proc. Sixth Workshop Parallel and Distributed Simulation, pp. 53-61, 1992.

Google Scholar

[3]

D. Bruce, "The Treatment of State in Optimistic Systems," Proc. Ninth Workshop Parallel and Distributed Simulation, pp. 40-48, 1995.

Digital Library

Google Scholar

[4]

J. Fleischmann and P.A. Wilsey, "A Comparative Analysis of Periodic State Saving Techniques in Time Warp Simulators," Proc. Ninth Workshop Parallel and Distributed Simulation, pp. 50-58, 1995.

Digital Library

Google Scholar

[5]

S. Franks F. Gomes B. Unger and J. Cleary, "State Saving for Interactive Optimistic Simulation," Proc. 11th Workshop Parallel and Distributed Simulation, pp. 72-79, 1997.

Digital Library

Google Scholar

[6]

R.M. Fujimoto, "Time Warp on a Shared Memory Multiprocessor," Trans. Soc. Computer Simulation, vol. 6, pp. 211-239, July 1989.

Digital Library

Google Scholar

[7]

Y.B. Lin and E.D. Lazowska, "The Optimal Checkpoint Interval in Time Warp Parallel Simulation," Technical Report 89-09-04, Dept. of Computer Science and Eng., Univ. of Washington, Seattle, Wash., 1989.

Google Scholar

[8]

Y.B. Lin B.R. Preiss W.M. Loucks and E.D. Lazowska, "Selecting the Checkpoint Interval in Time Warp Simulation," Proc. Seventh Workshop Parallel and Distributed Simulation, pp. 3-10, 1993.

Digital Library

Google Scholar

[9]

A.C. Palaniswamy and P.A. Wilsey, "An Analytical Comparison of Periodic Checkpointing and Incremental State Saving," Proc. Seventh Workshop Parallel and Distributed Simulation, pp. 127-134, 1993.

Digital Library

Google Scholar

[10]

B.R. Preiss W.M. Loucks and I.D. Macintyre, "Effects of the Checkpoint Interval on Time and Space in Time Warp," ACM Trans. Modeling and Computer Simulation, vol. 4, pp. 223-253, July 1994.

Digital Library

Google Scholar

[11]

R. Ronngren and R. Ayani, "Adaptive Checkpointing in Time Warp," Proc. Eighth Workshop Parallel and Distributed Simulation, pp. 110-117, 1994.

Digital Library

Google Scholar

[12]

R. Ronngren M. Liljenstam R. Ayani and J. Montagnat, "Transparent Incremental State Saving in Time Warp Parallel Discrete Event Simulation," Proc. 10th Workshop Parallel and Distributed Simulation, pp. 70-77, 1996.

Digital Library

Google Scholar

[13]

R. Ronngren M. Liljenstam and J. Montagnat, "A Comparative Study of State Saving Mechanisms for Time Warp Synchronized Parallel Discrete Event Simulation," Proc. 29th Ann. Simulation Symp., pp. 5-14, 1996.

Digital Library

Google Scholar

[14]

H.M. Soliman and A.S. Elmaghraby, "Hybrid Periodic Checkpointing and Incremental State Saving in Time Warp Simulation," Proc. Ninth Int'l Conf. Parallel and Distributed Computing Systems (PDCS '96), pp. 575-580, Dijon, France, 1996.

Google Scholar

Cited By

View all

Montesano FMencagli GDazzi PLowenthal DBadia R(2024)Full-Stack Revision of Memory and Data Management in PDES on Multi-Core MachinesProceedings of the 33rd International Symposium on High-Performance Parallel and Distributed Computing10.1145/3625549.3658831(417-420)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3625549.3658831
Marotta RMontesano FQuaglia F(2023)Effective Access to the Committed Global State in Speculative Parallel Discrete Event Simulation on Multi-core MachinesProceedings of the 2023 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3573900.3591117(107-117)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1145/3573900.3591117
Principe MPiccione APellegrini AQuaglia FLiu JGiabbanelli PCarothers C(2020)Approximated RollbacksProceedings of the 2020 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3384441.3395984(23-33)Online publication date: 15-Jun-2020
https://dl.acm.org/doi/10.1145/3384441.3395984
Show More Cited By

Index Terms

An Analytical Model for Hybrid Checkpointing in Time Warp Distributed Simulation

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 ...
Adaptive checkpointing in Time Warp

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 ...
Automatic incremental state saving
PADS '96: Proceedings of the tenth workshop on Parallel and distributed simulation

We present an Incremental State Saving technique for which the state saving calls are inserted automatically by directly editing the application executable. This method has the advantage of being easy to use since it is fully automatic, and has good ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 9, Issue 10

October 1998

128 pages

ISSN:1045-9219

Editor:
John A. Stankovic
Univ. of Virginia

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 October 1998

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Montesano FMencagli GDazzi PLowenthal DBadia R(2024)Full-Stack Revision of Memory and Data Management in PDES on Multi-Core MachinesProceedings of the 33rd International Symposium on High-Performance Parallel and Distributed Computing10.1145/3625549.3658831(417-420)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3625549.3658831
Marotta RMontesano FQuaglia F(2023)Effective Access to the Committed Global State in Speculative Parallel Discrete Event Simulation on Multi-core MachinesProceedings of the 2023 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3573900.3591117(107-117)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1145/3573900.3591117
Principe MPiccione APellegrini AQuaglia FLiu JGiabbanelli PCarothers C(2020)Approximated RollbacksProceedings of the 2020 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3384441.3395984(23-33)Online publication date: 15-Jun-2020
https://dl.acm.org/doi/10.1145/3384441.3395984
Carnà SFerracci SDe Santis EPellegrini AQuaglia FSon YHaas P(2019)Hardware-assisted incremental checkpointing in speculative parallel discrete event simulationProceedings of the Winter Simulation Conference10.5555/3400397.3400623(2759-2770)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3400397.3400623
Cingolani DPellegrini AQuaglia F(2017)Transparently Mixing Undo Logs and Software Reversibility for State Recovery in Optimistic PDESACM Transactions on Modeling and Computer Simulation10.1145/307758327:2(1-26)Online publication date: 27-May-2017
https://dl.acm.org/doi/10.1145/3077583
Cingolani DPellegrini AQuaglia FTaylor SMustafee NSon Y(2015)Transparently Mixing Undo Logs and Software Reversibility for State Recovery in Optimistic PDESProceedings of the 3rd ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/2769458.2769482(211-222)Online publication date: 10-Jun-2015
https://dl.acm.org/doi/10.1145/2769458.2769482
Pellegrini AVitali RQuaglia FLiu JQuaglia FEidenbenz SGilmore S(2011)An evolutionary algorithm to optimize log/restore operations within optimistic simulation platformsProceedings of the 4th International ICST Conference on Simulation Tools and Techniques10.5555/2151054.2151093(206-215)Online publication date: 21-Mar-2011
https://dl.acm.org/doi/10.5555/2151054.2151093
Pellegrini AVitali RQuaglia F(2009)Di-DyMeLoRProceedings of the 2009 ACM/IEEE/SCS 23rd Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2009.24(45-53)Online publication date: 22-Jun-2009
https://dl.acm.org/doi/10.1109/PADS.2009.24
Vitali RPellegrini AQuaglia F(2009)Benchmarking Memory Management Capabilities within ROOT-SimProceedings of the 2009 13th IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications10.1109/DS-RT.2009.15(33-40)Online publication date: 25-Oct-2009
https://dl.acm.org/doi/10.1109/DS-RT.2009.15
Wang GTurgut DBölöni LMarinescu D(2009)Time-parallel simulation of wireless ad hoc networksWireless Networks10.1007/s11276-007-0058-115:4(463-480)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1007/s11276-007-0058-1
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Adaptive checkpointing in Time Warp

Adaptive checkpointing in Time Warp

Automatic incremental state saving

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations