``An Algorithm for Fully Reversible Optimistic Parallel Simulation''
M. Peters and C. D. Carothers
In Proceedings of the 2003 Winter Simulation Conference (WSC '03),
December 2003.
ABSTRACT
Typically, large-scale optimistic parallel simulations will spend 90%
or more of the total execution time forward processing events and very
little time executing rollbacks. In fact, it was recently shown that a
large-scale TCP model consisting of over 1 million nodes will execute
without generating any rollbacks (i.e., perfect optimistic
execution is achieved). The major cost involved in forward execution
is the preparation for a rollback in the form of state-saving. Using
a technique called reverse computation, state-saving
overheads can be greatly reduced. Here, the rollback operation is
realized by executing previously processed events in reverse. However,
events are retained until GVT sweeps past. In this paper, we define a
new algorithm for realizing a continuum of reverse computation-based
parallel simulation systems, which enables us to relax the computing
of GVT and potentially further reduces the amount of memory required
to execute an optimistic simulation.