Optimality considerations of 'Time Warp' parallel simulation

Yi-Bing Lin*, Edward D. Lazowska

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

19 Scopus citations

Abstract

This paper derives a relationship between a conservative optimal simulation and the 'Time Warp' or 'optimistic' parallel simulation, and compares the performance of the Time Warp simulation with Chandy-Misra conservative simulation. We show that Time Warp simulation with aggressive cancellation is not conservative optimal in general, even under the assumption that the operational overhead virt is 0. We derive a sufficient condition for Time Warp to be conservative optimal and show some simulation problems that meet this condition (referred to as Time Warp simulations that satisfy the sufficient conservative optimal condition, or TWSO.) We show that by applying the lazy cancellation technique to TWSO, Time Warp always outperforms a conservative optimal simulation. Given equivalently favorable assumptions for both the Time Warp approach and the Chandy-Misra approach, we show that the Time Warp approach outperforms the Chandy-Misra approach in every feedforward network simulation. For feedback networks without lookahead, we show that in most cases Time Warp outperforms Chandy-Misra.

Original languageEnglish
Pages (from-to)29-34
Number of pages6
JournalSimulation Series
Volume22
Issue number1
StatePublished - 1 Jan 1990
EventProceedings of the SCS Multiconference on Distributed Simulation - San Diego, CA, USA
Duration: 17 Jan 199019 Jan 1990

Fingerprint Dive into the research topics of 'Optimality considerations of 'Time Warp' parallel simulation'. Together they form a unique fingerprint.

Cite this