A Comparative Analysis Of Various Time Warp Algorithms
Implemented In The WARPED Simulation Kernel


Radharamanan Radhakrishnan, Timothy J. McBrayer,
Krishnan Subramani, Malolan Chetlur,
Vijay Balakrishnan, and Philip A. Wilsey
Computer Architecture Design Laboratory
Dept. of ECECS, PO Box 210030, Cincinnati, OH 45221-0030
Phone: (513) 556-4779
Email: phil.wilsey@uc.edu



Abstract

The Time Warp mechanism conceptually has the potential to speedup discrete event simulations on parallel platforms. However, practical implementations of the optimistic mechanism have been hindered by several drawbacks such as large memory usage, excessive rollbacks (instability), and wasted lookahead computation. Several optimizations and variations to the original Time Warp algorithm have been presented in the literature to optimistically synchronize Parallel Discrete Event Simulation. This paper uses a common simulation environment to present comparative performance results of several Time Warp optimizations in two different application domains, namely: queuing model simulation and digital system simulation. The particular optimizations considered are: Lowest Timestamp First (LTSF) Scheduling, Periodic (fixed period) Checkpointing, Dynamic Checkpointing, Lazy Cancellation, and Dynamic Cancellation.