A study of time warp rollback mechanisms

ABSTRACT

The Time Warp “optimistic” approach is one of the most important parallel simulation protocols. Time Warp synchronizes processes via rollback. The original rollback mechanism called lazy cancellation has aroused great interest. This paper studies these rollback mechanisms. The general tradeoffs between aggressive and lazy cancellation are discussed, and by a conservitive-optimal simulation is defined for comparitive purposes. Within the framework of aggressive cancellation, we offer some observations and analyze the rollback behavior of tandom systems. The lazy cancellation mechanism iss examined using a metric called the sensitivity of output message. Both aggressive and lazy cancellation are shown to work well for a process with a small simulated load intensity. Finally, an analytical model is given to analyze message preemtion, an important factor that affects the performance of rollback mechanisms. Results indicate that message preemtion has a significant effect on performance when (1) the processor is highly utilized, (2) the execution times of messages have high varience, and (3) rollbacks occur frequently.

REFERENCES

• 1: Marc Abrams, The object library for parallel simulation (OLPS), Proceedings of the 20th conference on Winter simulation, p.210-219, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318191]
• 2: AGRE, J. R., JORNSON, A., TINKER, P. A., AND VOPOVA, S. Time Warp object oriented distributed simulation system (TWOODS). In Proceedings of the Rockwell Software Engineering Symposium III (Oct.). 1989, pp. 9.2.1-9.2.13.
• 3: Orna Berry, Performance evaluation of the time warp distributed simulation mechanism, University of Southern California, Los Angeles, CA, 1986
• 4: BERRY, O., AND JEFFERSON, D Critical path analysis of distributed simulation. In Proceedings of the 1985 SCS Multiconference on Distributed Simulation (Jan.). 1985, pp. 57-60.
• 5: CRANNY, K. M., AND MISRA, J. Distributed simulation: A case study in design and verification of distributed programs. IEEE Trans. Softw. Eng. SE-5, 5 (Sept. 1979), 440-452.
• 6: EBLING, M., DI LORETO, M., PRESLEY, M., WIELAND, F., AND JEFFERSON, D. An ant foraging model implemented on the Time Warp operating system. In Proceedings of the 1989 SCS Multiconference on Dtstributed Simulation (Mar.). 1989, pp. 21-26.
• 7: FELDERMAN, R. E., AND KLEINROCK, L. An upper bound on the improvement of asynchronous versus synchronous distributed processing. In Proceedings of the 1990 SCS Multiconference on Distributed Simulatmn (Jan.). 1990, pp. 131-136.
• 8: FUJIMOTO, R. M. Time Warp on a shared memory multiprocessor In Proceedings of the 1989 International Conference on Parallel Processing, vol. 3 (Aug). 1989, pp. 242-249.
• 9: FUJmOTO, R.M. Performance of Time Warp under synthetic workloads. In Proceedings of the 1990 SCS Multiconference on Dtstributed Simulation (Jan.). 1990, pp. 23-28.
• 10: 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
• 11: GArNL A. Rollback mechanisms for optimistic distributed simulation. In Proceedings of the 1988 SCS Multiconference on Distributed Simulation (Feb.). 1988, pp. 61-67.
• 12: GATES, B., AND MARTI, J. An empirical study of Time Warp request mechanisms. In Proceedings of the 1988 SCS Multiconference on Distributed Stmulation (Feb.). 1988, pp. 73-80.
• 13: HONTALAS, P., BECKMAN, B., DILORETO, M., BLUME, L., REmER, P., STURDEVANT, K., WARREN, L., WEDEL, J., WIELAND, F., AND JEFFERSON, D. Performance of the colliding pucks simulation on the Time Warp operating systems (Part 1: Asynchronous behavior and sectoring). In Proceedings of the 1989 SCS Multiconference on D~stributed Szmulation (Mar.). 1989, pp. 3-7.
• 14: 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]
• 15: JEFFERSON, D. Private communication. 1989.
• 16: D. Jefferson , B. Beckman , F. Wieland , L. Blume , M. Diloreto, Time warp operating system, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.77-93, November 08-11, 1987, Austin, Texas, United States
• 17: KLmNROCK, L. Queueing Systems: Volume I--Theory. Wiley, New York, 1976.
• 18: M. S Lakshmi, A Study and Analysis of Performance of Distributed Simulation, University of Texas at Austin, Austin, TX, 1987
• 19: LIN, Y.-B., AND LAZOWSKA, E.D. The optimal checkpoint interval in Time Warp parallel simulation. Tech. Rep. 89-09-04, Dept. of Computer Science and Engineering, Univ. of Washington, 1989.
• 20: LIN, Y.-B., ANO L~ZOWSKA, E. D. Determining the global virtual time in a distributed simulation. In Proceedings of the International Conference on Parallel Processing. 1990.
• 21: Y. B. Lin , E. D. Lazowska, Exploiting Lookahead in Parallel Simulation, IEEE Transactions on Parallel and Distributed Systems, v.1 n.4, p.457-469, October 1990 [doi>10.1109/71.80174]
• 22: LIN, Y.-B., AND LAZOWSKA, E.D. Optimality considerations for Time Warp parallel simulation. In Proceedings of the 1990 SCS Multiconference on Distrtbuted S~mulation (Jan.). 1990, pp. 29-34.
• 23: LtN, Y -B., AND LAZOWSKA, E.D. Processor scheduling for Time Warp parallel simulation Tech Rep 90-03-03, Dept. of Computer Science and Engineering, Univ. of Washington, 1990.
• 24: LIN, Y.-B., AND LAZOWSKA, E. D. Reducing the state saving overhead for Time Warp parallel simulation. Tech Rep. 90-02-03, Dept. of Computer Science and Engineering, Univ of Washington, 1990.
• 25: LIPTON, R. J., AND MIZELL, n.W. Time Warp vs. Chandy-Misra: A worst-case comparison. In Proceedings of the 1990 SCS Multiconference on Distributed S~mulatzon (Jan.). 1990, pp. 137-143.
• 26: LOMOW, G., CLEARY, J., UNOER, B., AND WEST, D. A performance study of Time Warp. In Proceedings of the 1988 SCS Multiconference on Dzstnb~ted Simulation (Feb) 1988, pp. 50-55.
• 27: NIcoL, D. Performance bounds on self-initiating parallel discrete event simulations. Tech. Rep 90-21, ICASE, 1990.
• 28: PRESLEY, M., EBLING, M., WIELAND, F., AND JEFFERSON, D. Benchmarking the Time Warp operating system with a computer network simulation. In Proceedings of the 1989 SCS Multiconference on Distributed S~mulation (Mar.). 1989, pp. 8-13.
• 29: REED, D. A., AND MALONY, A. Parallel discrete event simulation: The Chandy Misra approach. In Proceedings of the 1988 SCS Mult~conference on Distributed S~mulation (Feb.). 1988, pp. 8 13.
• 30: REmER, P., ^ND JEFFERSON, D. Limitation of optimism in the Time Warp operating system. In Proceedings of the 1989 Winter Simulation Conference, (Jan.). 1990, pp 112-121
• 31: REIHER, P., AND JEFFERSON, D. Virtual time based dynamic load management in the Time Warp operating system. In Proceedings of the 1990 SCS Mult~conference on Distributed Szmulat~on (Jan) 1990, pp 103-111.
• 32: REIHER, P, FUJIMOTO, R., BELLENOT, S., AND JEFFERSON, D. Cancellation strategies in optimistic execution systems. In Proceedings of the 1990 SCS Mult~conference on Dzstnbuted Simulation (Jan.). 1990, pp. 112-121
• 33: SOKOL, L. M., STUEKY, B. K., AND HWANO, V. MTW: A control mechanism for parallel discrete simulation. In Proceedings of the International Conference on Porallel Processing, vol 3. 1989, pp 250-254.
• 34: D. B. Wagner , E. D. Lazowska, Parallel simulation of queueing networks: limitations and potentials, Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.146-155, May 23-26, 1989, Oakland, California, United States
• 35: WIEL^ND, F., HAWLEY, L., FEINBEaG, A., DI LORETO, M., BLUME, L., REInEd, P., BECxMAN, B., HONTALAS, P, BELLENOT, S, AND JEFFERSON, D. Distributed combat simulation and Time Warp: The model and its performance. In Proceedings of the 1989 SCS MuIt~conference on Distributed Simulation (Mar.) 1989, pp. 14 20.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization
      D.4.4 Communications Management
          Subjects: Message sending
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Performance

Keywords:
Time Warp approach, aggressive cancellation, discrete-event simulation, lazy cancellation, parallel simulation