Parallel simulation: distributed simulation systems

ABSTRACT

An overview of technologies concerned with distributing the execution of simulation programs across multiple processors is presented. Here, particular emphasis is placed on discrete event simulations. The High Level Architecture (HLA) developed by the Department of Defense in the United States is first described to provide a concrete example of a contemporary approach to distributed simulation. The remainder of this paper is focused on time management, a central issue concerning the synchronization of computations on different processors. Time management algorithms broadly fall into two categories, termed conservative and optimistic synchronization. A survey of both conservative and optimistic algorithms is presented focusing on fundamental principles and mechanisms. Finally, time management in the HLA is discussed as a means to illustrate how this standard supports both approaches to synchronization.

REFERENCES

• 1: Ayani, R. (1989). A Parallel Simulation Scheme Based on the Distance Between Objects. Proceedings of the SCS Multiconference on Distributed Simulation, Society for Computer Simulation. 21: 113--118.
• 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: David J. Bodoh , Dr. Frederick Wieland, Performance Experiments with the High Level Architecture and the Total Airport and Airspace Model (TAAM), Proceedings of the seventeenth workshop on Parallel and distributed simulation, p.31, June 10-13, 2003
• 4: Luciano Bononi , Gabriele D'Angelo , Lorenzo Donatiello, HLA-based Adaptive Distributed Simulation of Wireless Mobile Systems, Proceedings of the seventeenth workshop on Parallel and distributed simulation, p.40, June 10-13, 2003
• 5: R. E. Bryant, SIMULATION OF PACKET COMMUNICATION ARCHITECTURE COMPUTER SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 6: Cai, W. and S. J. Turner (1990). An Algorithm for Distributed Discrete-Event Simulation - the "Carrier Null Message" Approach. Proceedings of the SCS Multiconference on Distributed Simulation, SCS Simulation Series. 22: 3--8.
• 7: 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]
• 8: Chandy, K. M. and J. Misra (1978). "Distributed Simulation: A Case Study in Design and Verification of Distributed Programs." IEEE Transactions on Software Engineering SE-5(5): 440--452.
• 9: 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]
• 10: Gilbert Chen , Boleslaw K. Szymanski, Lookback: a new way of exploiting parallelism in discrete event simulation, Proceedings of the sixteenth workshop on Parallel and distributed simulation, May 12-15, 2002, Washington, D.C.
• 11: Gilbert Chen , Boleslaw K. Szymanski, Four Types of Lookback, Proceedings of the seventeenth workshop on Parallel and distributed simulation, p.3, June 10-13, 2003
• 12: 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]
• 13: 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
• 14: Dickens, P. M. and J. Reynolds, P. F. (1990). SRADS With Local Rollback. Proceedings of the SCS Multiconference on Distributed Simulation. 22: 161--164.
• 15: 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
• 16: 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
• 17: 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
• 18: Richard M. Fujimoto, Parallel and Distribution Simulation Systems, John Wiley & Sons, Inc., New York, NY, 1999
• 19: Richard M. Fujimoto, Parallel simulation: parallel and distributed simulation systems, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
• 20: IEEE Std 1278.1-1995 (1995). IEEE Standard for Distributed Interactive Simulation - Application Protocols. New York, NY, Institute of Electrical and Electronics Engineers, Inc.
• 21: IEEE Std 1516--2000 (2000). IEEE Standard for Modeling and Simulation (M&S) High Level Architecture (HLA) - Framework and Rules. New York, NY, Institute of Electrical and Electronics Engineers, Inc.
• 22: IEEE Std 1516.2-2000 (2000). IEEE Standard for Modeling and Simulation (M&S) High Level Architecture (HLA) - Object Model Template (OMT) Specification. New York, NY, Institute of Electrical and Electronics Engineers, Inc.
• 23: IEEE Std 1516.3-2000 (2000). IEEE Standard for Modeling and Simulation (M&S) High Level Architecture (HLA) - Interface Specification. New York, NY, Institute of Electrical and Electronics Engineers, Inc.
• 24: 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]
• 25: 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]
• 26: Vikas Jha , Rajive Bagrodia, Simultaneous events and lookahead in simulation protocols, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.10 n.3, p.241-267, July 2000 [doi>10.1145/361026.361032]
• 27: Frederick Kuhl , Richard Weatherly , Judith Dahmann, Creating computer simulation systems: an introduction to the high level architecture, Prentice Hall PTR, Upper Saddle River, NJ, 1999
• 28: 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
• 29: 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]
• 30: 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
• 31: B. D. Lubachevsky, Efficient distributed event-driven simulations of multiple-loop networks, Communications of the ACM, v.32 n.1, p.111-123, Jan. 1989 [doi>10.1145/63238.63247]
• 32: Friedemann Mattern, Efficient algorithms for distributed snapshots and global virtual time approximation, Journal of Parallel and Distributed Computing, v.18 n.4, p.423-434, Aug. 1993 [doi>10.1006/jpdc.1993.1075]
• 33: Mehl, H. (1992). A Deterministic Tie-Breaking Scheme for Sequential and Distributed Simulation. Proceedings of the Workshop on Parallel and Distributed Simulation, Society for Computer Simulation. 24: 199--200.
• 34: Richard A. Meyer , Rajive L. Bargrodia, Path lookahead: a data flow view of PDES models, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.12-19, May 01-04, 1999, Atlanta, Georgia, United States
• 35: Miller, D. C. and J. A. Thorpe (1995). "SIMNET: The Advent of Simulator Networking." Proceedings of the IEEE 83(8): 1114--1123.
• 36: David Nicol , Philip Heidelberger, Parallel execution for serial simulators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.6 n.3, p.210-242, July 1996 [doi>10.1145/235025.235031]
• 37: 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
• 38: 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
• 39: Kalyan S. Perumalla , Alfred Park , Richard M. Fujimoto , George F. Riley, Scalable RTI-Based Parallel Simulation of Networks, Proceedings of the seventeenth workshop on Parallel and distributed simulation, p.97, June 10-13, 2003
• 40: 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
• 41: 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
• 42: Behrokh Samadi, Distributed simulation, algorithms and performance analysis (load balancing, distributed processing), 1985
• 43: 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.
• 44: Steinman, J. S. (1992). "SPEEDES: A Multiple-Synchronization Environment for Parallel Discrete Event Simulation." International Journal on Computer Simulation: 251--286.
• 45: Boleslaw K. Szymanski , Yu Liu , Rashim Gupta, Parallel Network Simulation under Distributed Genesis, Proceedings of the seventeenth workshop on Parallel and distributed simulation, p.61, June 10-13, 2003
• 46: Stephen J. Turner , Wentong Cai , Boon Ping Gan, Adapting a Supply-Chain Simulation for HLA, Proceedings of the Fourth IEEE International Workshop on Distributed Simulation and Real-Time Applications, p.71, August 25-27, 2000
• 47: Annette L. Wilson , Richard M. Weatherly, The aggregate level simulation protocol: an evolving system, Proceedings of the 26th conference on Winter simulation, p.781-787, December 11-14, 1994, Orlando, Florida, United States
• 48: Z. Xiao , B. Unger , R. Simmonds , J. Cleary, Scheduling critical channels in conservative parallel discrete event simulation, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.20-28, May 01-04, 1999, Atlanta, Georgia, United States
• 49: 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