"Efficient Execution of Time Warp Programs on Heterogeneous, NOW Platforms"
C. D Carothers, and R. M. Fujimoto
IEEE Transactions on Parallel and Distributed Systems
, Volume 11, Number 3, page 299-317, March 2000.
ABSTRACT
Time Warp is an optimistic protocol for synchronizing parallel
discrete-event simulations. To achieve performance in a multi-user
network of workstation (NOW) environment, Time Warp must continue to
operate efficiently in the presence of external workloads caused by
other users, processor heterogeneity and irregular internal workloads
caused by the simulation model. However, these performance problems
can cause a Time Warp program to become grossly unbalanced, resulting
in slower execution. The key observation asserted in this article is
that each of these performance problems, while different in source,
has a similar manifestation. For a Time Warp program to be balanced,
the amount of wall-clock time necessary to advance an LP one unit of
simulation time should be about the same for all LPs. Using this
observation, we devise a single algorithm that mitigates these
performance problems and enables the ``background'' execution of Time
Warp programs on heterogeneous distributed computing platforms in the
presence of external as well as irregular internal workloads.}