Page 40 - Data Science Algorithms in a Week

Using Deep Learning to Configure Parallel Distributed Discrete-Event Simulators 25

Time Warp (TW)

The optimistic viewpoint in time management of simulation objects uses a different
strategy for obtaining parallelism by aggressively processing simulation events without
regard for accuracy. Rollback techniques are implemented to undo events that might have
been processed out of order whenever straggler event messages are received from other
simulation objects located in different nodes (Figure 1). In this manner, events are
executed optimistically. While the optimistic approach places no restrictions on how
simulation objects can interact, the biggest drawback is that models must be developed in
a rollbackable manner. Optimistic event processing is able to achieve optimal execution
of the chain of dependent events that limit the performance of a simulation.
The Time Warp (TW) event management provides an efficient rollback mechanism
for each simulation object (Fujimoto, 2000). The simulation time of each simulation
object is defined as the time stamp of its last executed event, or the time of the event it is
presently executing. When a simulation object receives a straggler event in its past, it
rolls the simulation object back to its last correctly processed event. These events that
were rolled back are either reprocessed or rolled forward. A rolled back event can be
safely rolled forward if the straggler event does not modify any of the simulation object’s
state variables that were accessed by the event when it was originally executed
(Steinman, 1991; Steinman, 1992).
TW does not rollback the entire node when a simulation object receives a straggler
message. Instead, only the affected simulation object is rolled back. Of course, during the
rollback, all events scheduled by those events that were rolled back must also be
retracted, potentially causing secondary (or cascading) rollbacks. Each event must
therefore keep track of its generated events until the event itself is committed. Retraction
messages, used to withdraw incorrectly scheduled event messages in Time Warp, are
called antimessages (Fujimoto, 2000).
Figure 1 details the process of rollback and the cascading of antimessages. Rollback
can be started when a simulation object receives a straggler message (one which tag is
before the current simulation time of the simulation object). This straggler message will
make several processed events invalid (the ones from the time tag of the straggler event
to the current simulation time of the simulation object).