Selecting the Checkpoint Interval in Time Warp Parallel Simulation

logo Website of Bruno R. Preiss
next up contents external
Next : A Unifying Framework for Up: Conference Papers Previous: On the Performance of

  Yi-Bing Lin, Bruno  Richard Preiss, Wayne  Mervin Loucks, and Edward  D. Lazowska. In Proc. 1993 Workshop on Parallel and Distributed Simulation , pages 3-10, San Diego, CA, May 1993. Institute of Electrical and Electronics Engineers, Inc.[16].
In Time Warp parallel simulation, a process executes every message as soon as it arrives. If a message with a smaller timestamp subsequently arrives, the process rolls back its state to the time of the earlier message and re-executes from that point.

Clearly, 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 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. 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.

Copyright 1993 by Simulation Councils, Inc.

external Full text. external Presentation slides. external BibTeX entry.


Website of Bruno R. Preiss
next up contents external
Next: A Unifying Framework for Up: Conference Papers Previous: On the Performance of

bruno Copyright 2002 by Bruno R. Preiss, P.Eng. All rights reserved.
Tue Jan 1 13:41:25 EST 2002



Data Structures and Algorithms With Object-Oriented Design Patterns in Java
Data Structures and Algorithms with Object-Oriented Design Patterns in Java (Worldwide Series in Computer Science)
ISBN: 0471346136
EAN: 2147483647
Year: 1999
Pages: 100

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net