Estimating the cost of throttled execution in time warp

ABSTRACT

Over-optimistic execution has long been identified as a major performance bottleneck in Time Warp based parallel simulation systems. An appropriate throttle or control of optimism can improve performance by reducing the number of rollbacks. However, the design of an appropriate throttle is a difficult task, as correct computations on the critical path may be blocked, thus increasing the overall execution time. In this paper we build a cost model for throttled execution that involves both rollback probability and probability for an event computation being on the critical path. The model can estimate an appropriate size of time window for a throttled execution using statistics collected from the purely optimistic execution. The model is validated by an experimental study with a set of synthetic workloads.

REFERENCES

• 1: D. Ball and S. Hoyt. The adaptive Time-Warp concurrency control algorithm. Proceedings of the S CS Multicon}erence on Distributed Simulation, 22(1):174-177, January 1990.
• 2: Samir Das , Richard Fujimoto , Kiran Panesar , Don Allison , Maria Hybinette, GTW: a time warp system for shared memory multiprocessors, Proceedings of the 26th conference on Winter simulation, p.1332-1339, December 11-14, 1994, Orlando, Florida, United States
• 3: Samir R. Das , Richard M. Fujimoto, A performance study of the cancelback protocol for Time Warp, ACM SIGSIM Simulation Digest, v.23 n.1, p.135-142, July 1993
• 4: Samir R. Das , Richard M. Fujimoto, An adaptive memory management protocol for Time Warp parallel simulation, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.201-210, May 16-20, 1994, Nashville, Tennessee, United States
• 5: P. M. Dickens and P. F. Reynolds, Jr. SRADS with local rollback. Proceedings of the S CS Multiconference on Distributed Simulation, 22(1):161-164, January 1990.
• 6: Alois Ferscha, Probabilistic adaptive direct optimism control in Time Warp, Proceedings of the ninth workshop on Parallel and distributed simulation, p.120-129, June 13-16, 1995, Lake Placid, New York, United States
• 7: A. Ferscha , J. Luthi, Estimating rollback overhead for optimism control in Time Warp, Proceedings of the 28th Annual Simulation Symposium, p.2, April 25-28, 1995
• 8: R. M. Fujimoto. Performance of Time Warp under synthetic workloads. Proceedings of the S CS Multiconference on Distributed Simulation, 22(1):23-28, January 1990.
• 9: Michial A. Gunter, Understanding supercritical speedup, Proceedings of the eighth workshop on Parallel and distributed simulation, p.81-87, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 10: D. O. Hamnes and A. Tripathi. Evaluation of a local adaptive protocol for distributed discrete event simulation. In Proceedings of the 199~ International Conference on Parallel Processing, pages III:127-134, August 1994.
• 11: 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]
• 12: Boris Lubachevsky , Adam Schwartz , Alan Weiss, An analysis of rollback-based simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.2, p.154-193, April 1991 [doi>10.1145/116890.116912]
• 13: Vijay K. Madisetti , David A. Hardaker , Richard M. Fujimoto, The MIMDIX environment for parallel simulation, Journal of Parallel and Distributed Computing, v.18 n.4, p.473-483, Aug. 1993 [doi>10.1006/jpdc.1993.1078]
• 14: L. M. Sokol and B. K. Stucky. MTW: experimental results for a constrained optimistic scheduling paradigm. Proceedings of the SCS Multiconference on Distributed Simulation, 22(1):169-173, January 1990.
• 15: Sudhir Srinivasan , Paul F. Reynolds, Jr., Adaptive algorithms vs. Time Warp: an analytical comparison, Proceedings of the 27th conference on Winter simulation, p.666-673, December 03-06, 1995, Arlington, Virginia, United States [doi>10.1145/224401.224706]
• 16: Sudhir Srinivasan , Paul F. Reynolds, Jr., NPSI adaptive synchronization algorithms for PDES, Proceedings of the 27th conference on Winter simulation, p.658-665, December 03-06, 1995, Arlington, Virginia, United States [doi>10.1145/224401.224705]
• 17: J. Steinman. SPEEDES: A unified approach to parallel simulation. In 6th Workshop on Parallel and Distributed Simulation, pages 75-84, Jan. 1992.
• 18: Jeff S. Steinman, Breathing Time Warp, Proceedings of the seventh workshop on Parallel and distributed simulation, p.109-118, May 16-19, 1993, San Diego, California, United States
• 19: S. J. Turner and M. Q. Xu. Performance evaluation of the bounded Time Warp algorithm. Proceedings of the SCS Multiconference on Parallel and Distributed Simulation, 24(3):117-126, January 1992.
• 20: Z. Xiao F. Gomes , B. Unger , J. Cleary, A fast asynchronous GVT algorithm for shared memory multiprocessor architectures, Proceedings of the ninth workshop on Parallel and distributed simulation, p.203-208, June 13-16, 1995, Lake Placid, New York, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Measurement, Performance, Theory

Keywords:
discrete event simulation, parallel simulation, time warp, performance model