Parallel simulation: parallel and distributed simulation systems

ABSTRACT

Originating from basic research conducted in the 1970's and 1980's, the parallel and distributed simulation field has matured over the last few decades. Today, operational systems have been fielded for applications such as military training, analysis of communication networks, and air traffic control systems, to mention a few. This tutorial gives an overview of technologies to distribute the execution of simulation programs over multiple computer systems. Particular emphasis is placed on synchronization (also called time management) algorithms as well as data distribution techniques.

REFERENCES

• 1: François Baccelli , Miguel Canales, Parallel simulation of stochastic Petri nets using recurrence equations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.3 n.1, p.20-41, Jan. 1993 [doi>10.1145/151527.151545]
• 2: Roberto Beraldi , Libero Nigro, Exploiting Temporal Uncertainty in Time Warp Simulations, Proceedings of the Fourth IEEE International Workshop on Distributed Simulation and Real-Time Applications, p.39, August 25-27, 2000
• 3: Neville Thomas, Dynamic Grid-Based Multicast Group Assignment in Data Distribution Management, Proceedings of the Fourth IEEE International Workshop on Distributed Simulation and Real-Time Applications, p.47, August 25-27, 2000
• 4: R. E. Bryant, SIMULATION OF PACKET COMMUNICATION ARCHITECTURE COMPUTER SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 5: Christopher D. Carothers , Kalyan S. Perumalla , Richard M. Fujimoto, Efficient optimistic parallel simulations using reverse computation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.9 n.3, p.224-253, July 1999 [doi>10.1145/347823.347828]
• 6: Chandy, K. M. and J. Misra (1978). "Distributed Simulation: A Case Study in Design and Verification of Distributed Programs." IEEE Transactions on Software EngineeringSE-5(5): 440-452.
• 7: K. M. Chandy , J. Misra, Asynchronous distributed simulation via a sequence of parallel computations, Communications of the ACM, v.24 n.4, p.198-206, April 1981 [doi>10.1145/358598.358613]
• 8: Cohen, D. and A. Kemkes (1997). User-Level Measurement of DDM Scenarios. Proceedings of the Spring Simulation Interoperability Workshop.
• 9: Samir R. Das , Richard M. Fujimoto, Adaptive memory management and optimism control in time warp, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.2, p.239-271, April 1997 [doi>10.1145/249204.249207]
• 10: Tapas K. Das , Gurminder Singh , Alex Mitchell , P. Senthil Kumar , Kevin McGee, NetEffect: a network architecture for large-scale multi-user virtual worlds, Proceedings of the ACM symposium on Virtual reality software and technology, p.157-163, September 1997, Lausanne, Switzerland [doi>10.1145/261135.261164]
• 11: Ewa Deelman , Rajive Bagrodia , Rizos Sakellariou , Vikram Adve, Improving lookahead in parallel discrete event simulations of large-scale applications using compiler analysis, Proceedings of the fifteenth workshop on Parallel and distributed simulation, p.5-13, May 15-18, 2001, Lake Arrowhead, California, United States
• 12: Dickens, P. M. and J. Reynolds, P. F. (1990). SRADS With Local Rollback. Proceedings of the SCS Multiconference on Distributed Simulation.22: 161-164.
• 13: DIS Steering Committee (1994). The DIS Vision, A Map to the Future of Distributed Simulation. Orlando, Florida, Institute for Simulation and Training.
• 14: 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
• 15: 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
• 16: Richard M. Fujimoto, Exploiting temporal uncertainty in parallel and distributed simulations, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.46-53, May 01-04, 1999, Atlanta, Georgia, United States
• 17: Richard M. Fujimoto, Parallel and distributed simulation, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.122-131, December 05-08, 1999, Phoenix, Arizona, United States [doi>10.1145/324138.324176]
• 18: Richard M. Fujimoto, Parallel and Distribution Simulation Systems, John Wiley & Sons, Inc., New York, NY, 1999
• 19: Fujimoto, R. M., et al. (1995). "Parallel Simulation of Statistical Multiplexers." Journal of Discrete Event Dynamic Systems5: 115-140.
• 20: Albert G. Greenberg , Boris D. Lubachevsky , Isi Mitrani, Algorithms for unboundedly parallel simulations, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.201-221, Aug. 1991 [doi>10.1145/128738.128739]
• 21: Philip Heidelberger , Harold S. Stone, Parallel trace-driven cache simulation by time partitioning, Proceedings of the 22nd conference on Winter simulation, p.734-737, December 09-12, 1990, New Orleans, Louisiana, United States
• 22: IEEE Std 1278.1-1995 (1995). IEEE Standard for Distributed Interactive Simulation -- Application Protocols. New York, NY, Institute of Electrical and Electronics Engineers, Inc.
• 23: 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]
• 24: 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]
• 25: Bu-Sung Lee , Wentong Cai , Junlan Zhou, A causality based time management mechanism for federated simulation, Proceedings of the fifteenth workshop on Parallel and distributed simulation, p.83-90, May 15-18, 2001, Lake Arrowhead, California, United States
• 26: Yi-Bing Lin , Edward D. Lazowska, A time-division algorithm for parallel simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.1, p.73-83, Jan. 1991 [doi>10.1145/102810.214307]
• 27: 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]
• 28: 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
• 29: Miller, D. C. and J. A. Thorpe (1995). "SIMNET: The Advent of Simulator Networking." Proceedings of the IEEE83(8): 1114-1123.
• 30: D. M. Nicol , X. Liu, The dark side of risk (what your mother never told you about Time Warp), Proceedings of the eleventh workshop on Parallel and distributed simulation, p.188-195, June 10-13, 1997, Lockenhaus, Austria
• 31: 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
• 32: Bruno R. Preiss , Wayne M. Loucks, Memory management techniques for Time Warp on a distributed memory machine, Proceedings of the ninth workshop on Parallel and distributed simulation, p.30-39, June 13-16, 1995, Lake Placid, New York, United States
• 33: Rak, S. J. and D. J. Van Hook (1996). Evaluation of Grid-Based Relevance Filtering for Multicast Group Assignment. Proceedins of the 14th DIS Workshop on Standards for the Interoperability of Distributed Simulations. Orlando, FL.
• 34: Dhananjai Madhava Rao , Narayanan V. Thondugulam , Radharamanan Radhakrishnan , Philip A. Wilsey, Unsynchronized parallel discrete event simulation, Proceedings of the 30th conference on Winter simulation, p.1563-1570, December 13-16, 1998, Washington, D.C., United States
• 35: Singhal, S. K. and D. R. Cheriton (1995). "Exploiting Position History for Efficient Remote Rendering in Networked Virtual Reality." Presence4(2): 169-193.
• 36: Sokol, L. M. and B. K. Stucky (1990). MTW: Experimental Results for a Constrained Optimistic Scheduling Paradigm. Proceedings of the SCS Multiconference on Distributed Simulation.22: 169-173.
• 37: Gary Tan , Liang Xu , Farshad Moradi , Simon Taylor, An agent-based DDM for high level architecture, Proceedings of the fifteenth workshop on Parallel and distributed simulation, p.75-82, May 15-18, 2001, Lake Arrowhead, California, United States
• 38: Jing Lei Zhang , Carl Tropper, The dependence list in time warp, Proceedings of the fifteenth workshop on Parallel and distributed simulation, p.35-45, May 15-18, 2001, Lake Arrowhead, California, United States

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.7 Simulation Support Systems
          Subjects: Environments
      I.6.8 Types of Simulation
          Subjects: Distributed

General Terms:
Algorithms, Design, Performance