A Study of Time Warp Rollback Mechanisms

Yi-Bing Lin, Edward D. Lazowska

Research output: Contribution to journalArticlepeer-review

45 Scopus citations

Abstract

The Time Warp “optimistic” approach is one of the most important parallel simulation protocols. Time Warp synchronizes processes via rollback. The original rollback mechanism called lazy cancellation has aroused great interest. This paper studies these rollback mechanisms. The general tradeoffs between aggressive and lazy cancellation are discussed, and by a conservitive-optimal simulation is defined for comparitive purposes. Within the framework of aggressive cancellation, we offer some observations and analyze the rollback behavior of tandom systems. The lazy cancellation mechanism iss examined using a metric called the sensitivity of output message. Both aggressive and lazy cancellation are shown to work well for a process with a small simulated load intensity. Finally, an analytical model is given to analyze message preemtion, an important factor that affects the performance of rollback mechanisms. Results indicate that message preemtion has a significant effect on performance when 1991 the processor is highly utilized, (2) the execution times of messages have high varience, and (3) rollbacks occur frequently.

Original languageEnglish
Pages (from-to)51-72
Number of pages22
JournalACM Transactions on Modeling and Computer Simulation (TOMACS)
Volume1
Issue number1
DOIs
StatePublished - 1 Mar 1991

Keywords

  • aggressive cancellation
  • discrete-event simulation
  • lazy cancellation
  • parallel simulation
  • Time Warp approach

Fingerprint

Dive into the research topics of 'A Study of Time Warp Rollback Mechanisms'. Together they form a unique fingerprint.

Cite this