A Throttled Time Warp Scheme for Parallel Discrete-event Simulation

Abstract: "Excessive rollback recoveries due to overoptimistic event execution in Time Warp simulators often degrade their runtime performance. A common approach to handle this problem is to avoid the potential rollback occurrences by limiting the optimism. Some form of synchronization, however, is often used to ensure that simulation proceeds within the constraint. If the number of events available for processing is not sufficient to amortize the synchronization overhead, the control scheme may cause an undesirable performance slow down. Other approaches roll back the simulation to an earlier time even without the occurrence of causality error. This paper uses a two-sided throttling scheme to dynamically adjust the event execution speed of Time Warp simulators. We introduce the terminology called rollback thrashing to describe the rollback phenomena. The proposed throttle is based on a new concept called global progress window, which allows the individual simulation process to position on a global time scale, thereby to accelerate or decelerate their event execution. No global synchronization is required in the throttling scheme, and correct events processed need not be artificially rolled back. To quantify the effect of rollbacks and for purpose of comparing different time warp implementations, we propose two new measures called RPE (number of Rollback events Per committed Event), and [epsilon] (relative Effectiveness in reducing rollback overhead). Our implementation results show that the proposed throttle effectively regulates the proceeding of each simulation process, resulting in a significant reduction in rollback thrashing and elapsed time."