Adaptive memory management and optimism control in time warp

ABSTRACT

It is widely believed that the Time Warp protocol for parallel discrete event simulation is prone to two potential problems: an excessive amount of wasted, rolled back computation resulting from “rollback thrashing” behaviors, and inefficient use of memory, leading to poor performance of virtual memory and/or multiprocessor cache systems. An adaptive mechanism is proposed based on the Cancelback memory management protocol for shared-memory multiprocessors that dynamically controls the amount of memory used in the simulation in order to maximize performance. The proposed mechanism is adaptive in the sense that it monitors the execution of the Time Warp program, and using simple models, automatically adjusts the amount of memory used to reduce Time Warp overheads (fossil collection, Cancelback, the amount of rolled back computation, etc.) to a manageable level. We describe an implementation of this mechanism on a shared memory, Kendall Square Research KSR-1, multiprocessor and demonstrate its effectiveness in automatically maximizing performance while minimizing memory utilzation, for several synthetic and benchmark discrete event simulation applications. We also demonstrate the adaptive ability of the mechanism by showing that it “tracks” the time-varying nature of a communication network simulation.

REFERENCES

• 1: Ian F. Akyildiz , Liang Chen , Samir Ranjan Das , Richard M. Fujimoto , Richard F. Serfozo, The effect of memory capacity on Time Warp performance, Journal of Parallel and Distributed Computing, v.18 n.4, p.411-422, Aug. 1993 [doi>10.1006/jpdc.1993.1074]
• 2: ARVIND, K. AND SMART, C. 1992. Hierarchical parallel discrete event simulation in composite ELSA. In Proceedings of 6th Workshop on Parallel and Distributed Simulation (Los Alamitos, CA, Jan.), IEEE Computer Science Press, Los Alamitos, CA, 147-158.
• 3: BALL, D. AND HOYT, S. 1990. The adaptive Time-Warp concurrency control algorithm. Proceedings of the SCS Multiconference on Distributed Simulation 22, 1 (Jan.), SCS, San Diego, CA, 174-177.
• 4: BRINER, J., JR. 1991. Fast parallel simulation of digital systems. Proceedings of the Multiconference on Advances in Parallel and Distributed Simulation 23, 1 (Jan.), SCS, San Diego, CA, 71-77.
• 5: R. Brown, Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem, Communications of the ACM, v.31 n.10, p.1220-1227, Oct. 1988 [doi>10.1145/63039.63045]
• 6: Christopher D. Carothers , Richard Fujimoto , Yi-Bing Lin , Paul England, Distributed Simulation of Large-Scale PCS Networks, Proceedings of the Second International Workshop on Modeling, Analysis, and Simulation On Computer and Telecommunication Systems, p.2-6, January 31-February 02, 1994
• 7: 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
• 8: 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
• 9: Samir R. Das , Richard M. Fujimoto, A performance study of the cancelback protocol for Time Warp, Proceedings of the seventh workshop on Parallel and distributed simulation, p.135-142, May 16-19, 1993, San Diego, California, United States
• 10: Samir R. Das , Richard M. Fujimoto, An Empirical Evaluation of Performance-Memory Trade-Offs in Time Warp, IEEE Transactions on Parallel and Distributed Systems, v.8 n.2, p.210-224, February 1997 [doi>10.1109/71.577269]
• 11: DICKENS, P. M., AND REYNOLDS, P. F. JR. 1990. SRADS with local rollback. Proceedings of the SCS Multiconference on Distributed Simulation 22, 1 (Jan.), SCS San Diego, CA, 161-164.
• 12: 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
• 13: 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
• 14: 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
• 15: 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]
• 16: FUJIMOTO, R.M. 1990b. Performance of Time Warp under synthetic workloads. In Proceedings of the SCS Multiconference on Distributed Simulation 22, 1 (Jan.), SCS, San Diego, CA, 23-28.
• 17: HAMNES, D. O., AND TRIPATHI, A. 1994a. Evaluation of a local adaptive protocol for distributed discrete event simulation. In Proceedings of the 1994 International Conference on Parallel Processing (Aug.), CRC Press, Boca Raton, FL, 127-134.
• 18: Donald O. Hamnes , Anand Tripathi, Investigations in adaptive distributed simulation, Proceedings of the eighth workshop on Parallel and distributed simulation, p.20-23, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 19: 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]
• 20: David Jefferson, Virtual time II: storage management in conservative and optimistic systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.75-89, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93403]
• 21: David R. Jefferson , Amihai Motro, The Time Warp Mechanism for Database Concurrency Control, Proceedings of the Second International Conference on Data Engineering, p.474-481, February 05-07, 1986
• 22: Yi-Bing Lin , Bruno R. Preiss, Optimal memory management for time warp parallel simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.4, p.283-307, Oct. 1991 [doi>10.1145/130611.130612]
• 23: 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
• 24: B. Lubachevsky , A. Shwartz , A. Weiss, Rollback sometimes works...if filtered, Proceedings of the 21st conference on Winter simulation, p.630-639, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76819]
• 25: 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]
• 26: 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]
• 27: MEHL, H. 1991. Speedup of conservative distributed discrete-event simulation methods by speculative computing. Proceedings of the Multiconference on Advances in Parallel and Distributed Simulation 23, 1 (Jan.), SCS, San Diego, CA, 163-166.
• 28: NICOL, D. M., AND FUJIMOTO, R.M. 1994. Parallel simulation today. Ann. Oper. Res. 53, 249-286.
• 29: 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
• 30: Richard M. Fujimoto , Kiran S. Panesar, Buffer management in shared-memory Time Warp systems, Proceedings of the ninth workshop on Parallel and distributed simulation, p.149-156, June 13-16, 1995, Lake Placid, New York, United States
• 31: PRESLEY, M., EBLING, M., WIELAND, F., AND JEFFERSON, D.R. 1989. Benchmarking the Time Warp Operating System with a computer network simulation. Proceedings of the SCS Multiconference on Distributed Simulation 21, 2 (Mar.), SCS, San Diego, CA, 8-13.
• 32: Hassan Rajaei , Rassul Ayani , Lars-Erik Thorelli, The local Time Warp approach to parallel simulation, Proceedings of the seventh workshop on Parallel and distributed simulation, p.119-126, May 16-19, 1993, San Diego, California, United States
• 33: P. L. Reiher , F. Wieland , D. Jefferson, Limitation of optimism in the time warp operating system, Proceedings of the 21st conference on Winter simulation, p.765-770, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76834]
• 34: Robert Rönngren , Rassul Ayani , Richard M. Fujimoto , Samir R. Das, Efficient implementation of event sets in Time Warp, Proceedings of the seventh workshop on Parallel and distributed simulation, p.101-108, May 16-19, 1993, San Diego, California, United States
• 35: SOKOL, L. M., AND STUCKY, B. K. 1990. MTW: Experimental results for a constrained optimistic scheduling paradigm. In Proceedings of the SCS Multiconference on Distributed Simulation 22, 1 (Jan.), SCS, San Diego, CA, 169-173.
• 36: 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]
• 37: STEINMAN, J. S. 1992. SPEEDES: A multiple-synchronization environment for parallel discrete event simulation. Int. J. Comput. Simul. 2, 3, 251-286.
• 38: 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
• 39: TURNER, S. J., AND XU, M. Q. 1992. Performance evaluation of the bounded Time Warp algorithm. Proceedings of the SCS Multiconference on Parallel and Distributed Simulation 24, 3 (Jan.), SCS, San Diego, CA, 117-126.
• 40: WIELAND, F., HAWLEY, L., FEINBERG, A., DILORENTO, M., BLUME, L., REIHER, P., BECKMAN, B., HONTALAS, P., BELLENOT, S., AND JEFFERSON, D.R. 1989. Distributed combat simulation and Time Warp: The model and its performance. Proceedings of the SCS Multiconference on Distributed Simulation 21, 2 (Mar.), SCS, San Diego, CA, 14-20.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

General Terms:
Experimentation, Measurement, Performance