Automatic incremental state saving

ABSTRACT

We present an Incremental State Saving technique for which the state saving calls are inserted automatically by directly editing the application executable. This method has the advantage of being easy to use since it is fully automatic, and has good performance since it adds overhead only where state is being modified. Since the editing happens on executable code, the method is independent of the compiler, and allows third party libraries to be used. None of the previous incremental state saving methods have both of these features. We find that it is beneficial to use Automatic Incremental State Saving if less than 15% of the state is modified in each event as compared to copy state saving. This technique allows us to efficiently parallelize existing simulations, and makes Time Warp more accessible to non-Time Warp experts.

REFERENCES

• 1: Christopher D. Carothers , Richard Fujimoto , Yi-Bing Lin , Paul England, Distributed Simulation of Large-Scale PCS Networks, Proceedings of the Second International Workshop on Modeling, Analysis, and Simulation On Computer and Telecommunication Systems, p.2-6, January 31-February 02, 1994
• 2: John Cleary , Fabian Gomes , Brian Unger , Zhonge Xiao , Raimar Thudt, Cost of state saving & rollback, Proceedings of the eighth workshop on Parallel and distributed simulation, p.94-101, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 3: Richard M. Fujimoto, Time warp on a shared memory multiprocessor, Transactions of the Society for Computer Simulation International, v.6 n.3, p.211-239, Jul. 1989
• 4: R. M. Fujimoto. Parallel discrete event simulation: Will the field survive? ORSA Journal on Computing, (3):213-- 230, summer 1993.
• 5: R. M. Fujimoto , J.-J. Tsai , G. Gopalakrishnan, Design and performance of special purpose hardware for time warp, Proceedings of the 15th Annual International Symposium on Computer architecture, p.401-409, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 6: Erol Gelenbe, On the Optimum Checkpoint Interval, Journal of the ACM (JACM), v.26 n.2, p.259-270, April 1979 [doi>10.1145/322123.322131]
• 7: Fabian Gomes. State saving and restoration experiments. http://bungee.cpsc.ucalgary.ca/GOMES/expts.html.
• 8: 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]
• 9: James R. Larus , Eric Schnarr, EEL: machine-independent executable editing, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.291-300, June 18-21, 1995, La Jolla, California, United States
• 10: 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
• 11: Baezner, D., Lomow,G., Unger, B. "Sim++: the Transition to Distributed Simulation," Proc. SCS Multiconference on Distributed Simulation, San Diego, California, January, 1990.
• 12: CORPORATE SPARC International, Inc., The SPARC architecture manual: version 8, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 13: 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]
• 14: Computer Staff, Efficient program tracing, Computer, v.26 n.5, p.52-61, May 1993 [doi>10.1109/2.211900]
• 15: James R. Larus Wisconsin Architectural Research Tool Set. http :llwww.cs. wisc.edul~laruslwarts.html
• 16: 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]
• 17: 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
• 18: Pure Software Inc. HomePage. http://www.mwl.comlpurel
• 19: B. Randell System Structure for software fault tolerance. IEEE Transcations on Software Engineering 1 (2):220-232, June 1975.
• 20: D. L. Russel State restoration in systems of communicating processes. /EEE Transcations of Software Engineering, 6(2):183-194, March 1980.
• 21: Richard Koo , Sam Toueg, Checkpointing and rollback-recovery for distributed systems, IEEE Transactions on Software Engineering, v.13 n.1, p.23-31, Jan. 1987 [doi>10.1109/TSE.1987.232562]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Checkpoint/restart

General Terms:
Measurement, Performance, Theory

Keywords:
Parallel Discrete Event Simulation, State Saving, Incremental State Saving, Checkpointing, Time Warp