Limitation of optimism in the time warp operating system

ABSTRACT

Optimistic systems execute events out of order and must undo their errors to produce correct results. Undoing incorrect work can be expensive. By restraining their optimism, such systems might execute fewer events out of order and thereby run faster. This paper examines two methods tested in the Time Warp Operating System. The first method explicitly prevents events from executing in the far simulation future. The second method tries to identify objects that are doing work that has to be undone; such objects are allowed to execute less often. Experimental results show that only modest gains were realized, and that even these gains were unpredictable. While other methods remain untested, the value of limiting optimism seems small.

REFERENCES

• 1: Hontalas, P., Beckman, B., Di Loreto, M., Blume, L., Reiher, P., Sturdevant, K., Warren, L. V., Wedel, J., Wieland, F., Jefferson, D. (1989). Performance of the Colliding Pucks Simulation on the Time Warp Operating System (Part 1: Asynchronous Behavior and Sectoring), Proceedings of the Society for Computer Simulation's 1989 Eastern Multiconference.
• 2: Jefferson, D., Beckman, B., Wieland, F., Blume, L., Di Loreto, M., Hontalas, P., Laroche, P., Sturdevant, K., Tupman, J., Warren, V., Wedel, J., Younger, H., Bellenot, S. (1987). Distributed Simulation and the Time Warp Operating System, ACM Operating System Review, Vol. 20, No. 4.
• 3: Mitra (1985). Personal communications.
• 4: Mitra and Mitrani, (1984). Analysis and Optimum Performance of Two Message-Passing Parallel Processors Synchronized By Rollback, Tenth International Symposium on Computer Performance Modeling, Measurement, and Evaluation.
• 5: Presley, M., Ebling, M., Wieland, F., Jefferson, D. (1989). Benchmarking the Time Warp Operating System With a Computer Network Simulation, Proceedings of the Society for Computer Simulation's 1989 Eastern Multiconference.
• 6: Sokol, L. Stucky, B., Hwang V. (1989). MTW: A Control Mechanism for Parallel Discrete Simulation, Mitre Technical Report MP-89W00008.
• 7: Wieland, F., Hawley, L., Feinberg, A., Di Loreto, M., Blume, L., Ruffles, J., Reiher, P., Beckman, B., Hontalas, P., Bellenot, S., Jefferson, D. (1989). Distributed Combat Simulation and Time Warp: The Model and its Performance, Proceedings of the Society for Computer Simulation's 1989 Eastern Multiconference.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Modeling and prediction

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory
          Subjects: Types of simulation (continuous and discrete)*

General Terms:
Algorithms, Design, Experimentation