28th Annual Simulation Symposium
Estimating rollback overhead for optimism control in Time Warp
Santa Barbara, California
April 25-April 28
ISBN: 0-8186-7091-6
The main performance pitfall of the Time Warp distributed discrete event simulation (DDES) protocol has been widely recognized to be the overoptimistic progression of event execution into the simulated future. The premature execution of events that eventually have to be "rolled back" due to causality violations induces memory and communication overheads as sources of performance inefficiencies. Optimistic Time Windows and self adaptive mechanisms have been proposed in the literature to control the optimism in Time Warp in order to improve or optimize its execution performance. An adaptive optimism control mechanism based on the observed model parallelism is proposed. Methodologically, logical processes (LPs) monitor the local virtual time (LVT) progression per unit CPU time from the timestamp of arriving messages and establish a cost model for the tradeoff between optimistically progressing and conservatively blocking the simulation engine. Compared to previous approaches, an optimal CPU delay interval is computed from the rollback probability and the overhead induced by the rollback procedure, such that the LP can adapt the synchronization behavior to the amount of optimism that can be justified from the parallelism inherent in the simulation model. Experiments with an implementation on a distributed memory multiprocessor (iPSC/860) show that the protocol is able to automatically adjust the local virtual time progression such that rollback overhead is minimized, and that the original Time Warp protocol can be outperformed.
Index Terms:
time warp simulation; discrete event simulation; virtual machines; protocols; adaptive systems; optimal control; rollback overhead; adaptive optimism control mechanism; performance pitfall; Time Warp distributed discrete event simulation protocol; DDES protocol; overoptimistic progression; event execution; simulated future; premature event execution; causality violations; performance inefficiencies; observed model parallelism; logical processes; local virtual time; LVT progression per unit CPU time; arriving messages; cost model; simulation engine; optimal CPU delay interval; rollback probability; synchronization behavior; distributed memory multiprocessor; iPSC/860
Citation:
A. Ferscha, J. Luthi, "Estimating rollback overhead for optimism control in Time Warp," ss, pp.2, 28th Annual Simulation Symposium, 1995