State saving for interactive optimistic simulation

ABSTRACT

Time Warp's optimistic scheduling requires the maintenance of simulation state history to support rollback in the event of causality violations. State history, and the ability to rollback the simulation, can provide unique functionality for human-in-the-loop simulation environments. This paper investigates the use of Time Warp to output valid simulation state in a near real-time manner, re-execute portions of the simulation, and interactively probe simulation values to ascertain underlying causes of transient behavior.A shared-memory, multi-threaded interactive simulation architecture is presented and the additional state saving requirements imposed by interactivity are examined. The shortcomings of existing state saving schemes lead us to propose Multiplexed State Saving (MSS). By interleaving checkpointing and incremental state logs MSS provides bounded rollback costs and asynchronous access to prior simulation state. The interaction algorithms and MSS form a scalable, bounded cost component suitable for use in a real-time interactive Time Warp system.

REFERENCES

• 1: J.R. Agre and P. A. Tinker, "Useful Extensions to a Time Warp Simulation System," presented at SCS Multiconference on Advances in Parallel and Distributed Simulation, Anaheim, California, 1991.
• 2: H. Bauer and C. Sporer, "Reducing Rollback Overhead in Time-Warp Based Distributed Simulation with Optimized Incremental State Saving," presented at The 26th Annual Simulation Symposium, pages 12-20, March 1993.
• 3: S. Bellenot, "State Skipping Performance with the Time Warp Operating System," pregented at 1992 SCS Western Simulation MultiConference on Parallel and Distributed Simulation, Newport Beach, California, 1992.
• 4: 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
• 5: 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
• 6: 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
• 7: 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
• 8: R. M, Fujimoto, "Performance of Time Warp Under Synthetic Workloads," presented at Proceedings of the SCS Multiconference on Distributed Simulation, San Diego, California, 1990.
• 9: B, Gates and J. Marti, "An Empirical Study of the Time Warp Request Mechanisms," presented at SCS Multiconference on Distributed Simulation, San Diego, California, 1988,
• 10: 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]
• 11: Kaushik Ghosh , Richard M. Fujimoto , Karsten Schwan, PORTS: a parallel, optimistic, real-time simulator, Proceedings of the eighth workshop on Parallel and distributed simulation, p.24-31, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 12: Fabian Gomes , Brian Unger , John Cleary , Steve Franks, Multiplexed state saving for bounded rollback, Proceedings of the 29th conference on Winter simulation, p.460-467, December 07-10, 1997, Atlanta, Georgia, United States [doi>10.1145/268437.268527]
• 13: 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]
• 14: Fabian Anthony Francis Bosco Gomes , Brian Unger, Optimizing incremental state-saving and restoration, 1996
• 15: 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]
• 16: 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
• 17: B.D. Lubachevsky, "Bounded Lag Distributed Discrete Event Simulation," presented at SCS Multiconference on Distributed Simulation (PADS 88), San Diego, California, 1988.
• 18: J. Marti, "RISE: The Rand Integrated Simulation Environment," presented at SCS Multiconference on Distributed Simulation (PADS 88), San Diego, California, 1988.
• 19: Horst Mehl , Stefan Hammes, Shared variables in distributed simulation, Proceedings of the seventh workshop on Parallel and distributed simulation, p.68-75, May 16-19, 1993, San Diego, California, United States
• 20: 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
• 21: 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
• 22: R. Ronngren , M. Liljenstram , R. Ayani , J. Montagnat, A comparative study of state saving mechanisms for time warp synchronized parallel discrete event simulation, Proceedings of the 29th Annual Simulation Symposium (SS '96), p.5, April 08-11, 1996
• 23: Ben Shneiderman, Designing the user interface (2nd ed.): strategies for effective human-computer interaction, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 24: L.M. Sokol, D. P. Briscoe, and A. P. Wieland, "MTW: A Strategy for Scheduling Discrete Simulaion Events for Concurrent Execution," presented at SCS Multiconference on Distributed Simulation, San Diego, California, 1988.
• 25: L S. Steinman, "SPEEDES: A Multiple-Synchronization Environment for Parallel Discrete-Event Simulation", International Journal in Computer Simulation. Vol.2, Pages 251-286, 1992
• 26: 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]
• 27: Jeffrey S. Steinman , Craig A. Lee , Linda F. Wilson , David M. Nicol, Global Virtual Time and distributed synchronization, Proceedings of the ninth workshop on Parallel and distributed simulation, p.139-148, June 13-16, 1995, Lake Placid, New York, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Interaction styles (e.g., commands, menus, forms, direct manipulation)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.7 Simulation Support Systems
          Subjects: Environments

General Terms:
Algorithms