Fast-software-checkpointing in optimistic simulation: embedding state saving into the event routine instructions

ABSTRACT

In this paper we present a software approach, namely Fast-Software-Checkpointing (FSC), to reduce the running time of the state saving protocol in optimistic parallel discrete event simulation. The idea behind FSC is to use the instructions performed during the execution of an event as part of the state saving protocol, hence the total number of instructions due to state saving is reduced. Under FSC the time for saving the state of a logical process prior to the execution of an event e requires an amount of time proportional to the amount of state variables not updated by e's execution, as only these variables must be copied. This outlines that FSC shows some dualism with respect to incremental state saving. We show, however, that there exists a basic difference between the two solutions as in FSC some of the state saving instructions are actually event routine instructions, while in incremental state saving they are only added and mixed to the latter ones. We also present a simple software architecture to support FSC and simulation results to demonstrate the effectiveness of such solution. The obtained data show that FSC, combined with a sparse state saving strategy, may represent the best checkpointing solution in case of both medium/small state granularity simulations and large state granularity simulations even with small (but non-minimal) portions of the state updated by event execution. FSC may result therefore suited for a wide class of simulation problems.

REFERENCES

• 1: H. Bauer and C. Sporrer, "Reducing Rollback Overhead in Time Warp Based Distributed Simulation with Optimized Incremental State Saving", Proc. 26-th Annual Simulation Symposium, pp. 12-20, March 1993.
• 2: S. Bellenot, "State Skipping Performance with the Time Warp Operating System", Proc. 6-th Workshop on Parallel and Distributed Simulation, pp.33-42, January 1992.
• 3: David Bruce, The treatment of state in optimistic systems, Proceedings of the ninth workshop on Parallel and distributed simulation, p.40-49, June 13-16, 1995, Lake Placid, New York, United States
• 4: Josef Fleischmann , Philip A. Wilsey, Comparative analysis of periodic state saving techniques in time warp simulators, Proceedings of the ninth workshop on Parallel and distributed simulation, p.50-58, June 13-16, 1995, Lake Placid, New York, United States
• 5: Steve Franks , Fabian Gomes , Brian Unger , John Cleary, State saving for interactive optimistic simulation, Proceedings of the eleventh workshop on Parallel and distributed simulation, p.72-79, June 10-13, 1997, Lockenhaus, Austria
• 6: Richard M. Fujimoto, Parallel discrete event simulation, Communications of the ACM, v.33 n.10, p.30-53, Oct. 1990 [doi>10.1145/84537.84545]
• 7: R.M. Fujimoto, "'Performance of Time Warp Under Synthetic Workloads", Proc. Multiconf. Distributed Simulation, Vol.22, No. 1, January 1990.
• 8: Richard M. Fujimoto , Jya-Jang Tsai , Ganesh C. Gopalakrishnan, Design and Evaluation of the Rollback Chip: Special Purpose Hardware for Time Warp, IEEE Transactions on Computers, v.41 n.1, p.68-82, January 1992 [doi>10.1109/12.123382]
• 9: D. Jefferson and H. Sowizral, "Fast Concurrent Simulation Using the Time Warp Mechanism; Part I: Local Control", Tech. Rep. N1906AF, RAND Corporation, December 1982.
• 10: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 11: Yi-Bing Lin , Bruno R. Preiss , Wayne M. Loucks , Edward D. Lazowska, Selecting the checkpoint interval in time warp simulation, Proceedings of the seventh workshop on Parallel and distributed simulation, p.3-10, May 16-19, 1993, San Diego, California, United States
• 12: Avinash C. Palaniswamy , Philip A. Wilsey, Adaptive checkpoint intervals in an optimistically synchronised parallel digital system simulator, Proceedings of the IFIP TC10/WG 10.5 International Conference on Very Large Scale Integration, p.353-362, September 07-10, 1993
• 13: Avinash C. Palaniswamy , Philip A. Wilsey, An analytical comparison of periodic checkpointing and incremental state saving, Proceedings of the seventh workshop on Parallel and distributed simulation, p.127-134, May 16-19, 1993, San Diego, California, United States
• 14: Bruno R. Preiss , Wayne M. Loucks , Ian D. Macintyre, Effects of the checkpoint interval on time and space in time warp, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.3, p.223-253, July 1994 [doi>10.1145/189443.189444]
• 15: E Quaglia and V. Cortellessa, "Rollback-Based Parallel Discrete Event Simulation by Using Hybrid State Saving", Proc. 9-th European Simulation Symposium, pp.275-279, October 1997.
• 16: Francesco Quaglia, Event history based sparse state saving in time warp, Proceedings of the twelfth workshop on Parallel and distributed simulation, p.72-79, May 26-29, 1998, Banff, Alberta, Canada
• 17: Robert Rönngren , Rassul Ayani, Adaptive checkpointing in Time Warp, Proceedings of the eighth workshop on Parallel and distributed simulation, p.110-117, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 18: Robert Rönngren , Michael Liljenstam , Rassul Ayani , Johan Montagnat, Transparent incremental state saving in time warp parallel discrete event simulation, Proceedings of the tenth workshop on Parallel and distributed simulation, p.70-77, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 19: Sven Sköld , Robert Rönngren, Event sensitive state saving in time warp parallel discrete event simulations, Proceedings of the 28th conference on Winter simulation, p.653-660, December 08-11, 1996, Coronado, California, United States [doi>10.1145/256562.256779]
• 20: Jeff S. Steinman, Incremental state saving in SPEEDES using C++, Proceedings of the 25th conference on Winter simulation, p.687-696, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256816]
• 21: Brian W. Unger , John G. Cleary , Alan Covington , Darrin West, An external state management system for optimistic parallel simulation, Proceedings of the 25th conference on Winter simulation, p.750-755, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256836]
• 22: Darrin West , Kiran Panesar, Automatic incremental state saving, Proceedings of the tenth workshop on Parallel and distributed simulation, p.78-85, May 22-24, 1996, Philadelphia, Pennsylvania, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Parallel

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Discrete event

General Terms:
Algorithms, Experimentation, Performance