A Cost-Effective State Saving Scheme for Optimistic Parallel Simulation
No Thumbnail Available
Date
1999-10-01T00:00:00Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Unlike the conservative approach, Time Warp (TW) executes simulation events greedily and uses a rollback mechanism to recover from causality errors. The TW protocol has the potential to exploit a higher degree of parallelism in the simulated system but it is realized with an overhead. For the simulator to carry out a rollback, the system state must be checkpointed. While increasing the checkpointing frequency increases the state saving cost, an infrequent scheme also escalates the coast forward effort when a large number of executed events are redone. Such a paradox indicates the need for a cost model to decide if a system state should be saved. This paper uses a probabilistic approach to weigh the performance gain and loss of each checkpointing. Logical processes of the TW simulation and their processing elements are assumed to be homogeneous. By the use of exponential distribution on inter-arrival time and service time, we can derive the rollback probability, thereby calculate the expected coast forward effort if a state is not saved. Based on the derived expectation, a state vector is saved only if the expected coast forward effort is larger than the state saving cost and vice versa. Our experiments show that the cost model reduces the simulation elapsed time by close to 30% as compared to saving the system state after each event execution, and saving the system state at a predefined interval. Keywords: performance optimization, optimistic simulation, state saving, rollback, cost model