Language based state saving extensions for optimistic parallel simulation

ABSTRACT

One of the greatest challenges in making optimistic synchronization techniques such as Time Warp practical tools is making state saving efficient and easy to use. State saving is necessary so that when optimistic execution is found to be out of order, rollback can be used to recover an earlier execution state. Previous work has shown that the most robust and efficient technique for saving state is to incrementally save copies of small parts of the state at the point that they are modified. Unfortunately, this requires sig nificant programmer intervention to insert additional code. In this paper, C++ language extensions for trans parent incremental state saving are presented. Operator overloading and type parameterization are used to incrementally save basic data types. Building on this, two new type-specifiers, "recover" and "nourecover" are described. They allow a single declaration to specify, for example, that all the member variables of a class are to be state saved, and for all the resulting state saving calls to be automatically generated. Issues, including how these specifiers interact with class inheritance and function declarations are examined and solved.

REFERENCES

• 1: Bauer, H., and C. Sporer. 1993. Reducing rollback overhead in Time Warp based distributed simulation with optimized incremental state saving. In Proceedings of the P6th Annual Simulation Symposium, ed. J. Miller, 12-20. Arlington, Virginia.
• 2: 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
• 3: John Cleary , Fabian Gomes , Brian Unger , Zhonge Xiao , Raimar Thudt, Cost of state saving & rollback, ACM SIGSIM Simulation Digest, v.24 n.1, p.94-101, July 1994
• 4: Margaret A. Ellis , Bjarne Stroustrup, The annotated C++ reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 5: 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
• 6: 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
• 7: 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]
• 8: Fabian Gomes , John Cleary , Alan Covington , Steve Franks , Brian Unger , Zhong-e Ziao, SimKit: a high performance logical process simulation class library in C++, Proceedings of the 27th conference on Winter simulation, p.706-713, December 03-06, 1995, Arlington, Virginia, United States [doi>10.1145/224401.224714]
• 9: Gomes, F., and B. Unger. 1994. Benchmarking Shared Memory Time Warp with Signalling System No. 7 Performance Model- 3. Project Report CPSC 601.24, Department of Computer Science, University of Calgary, Canada.
• 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, ACM SIGSIM Simulation Digest, v.23 n.1, p.3-10, July 1993
• 12: 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]
• 13: Robert Rönngren , Rassul Ayani, Adaptive checkpointing in Time Warp, ACM SIGSIM Simulation Digest, v.24 n.1, p.110-117, July 1994
• 14: 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]
• 15: Stroustrup, B. 1988. Parameterized types for C++. In Proceedings of the 1988 USENIX C++ Conference, 1-18.
• 16: Brian W. Unger , Fabian Gomes , Xiao Zhonge , Pawel Gburzynski , Theodore Ono-Tesfaye , Srinivasan Ramaswamy , Carey Williamson , Alan Covington, A high fidelity ATM traffic and network simulator, Proceedings of the 27th conference on Winter simulation, p.996-1003, December 03-06, 1995, Arlington, Virginia, United States [doi>10.1145/224401.224763]
• 17: Xiao, Z. and B. Unger. 1995. Performance of ATM- TN Wnet model. TeleSirn Project Report ATMI.1- PR, Department of Computer Science, University of Calgary, Canada: WurcNet Inc.