Parallel discrete event simulation

ABSTRACT

This tutorial surveys the state of the art in executing discrete event simulation programs on a parallel computer. Specifically, we will focus attention on asynchronous simulation programs where few events occur at any single point in simulated time, necessitating the concurrent execution of events occurring at different points in time.We first describe the parallel discrete event simulation problem, and examine why it so difficult. We review several simulation strategies that have been proposed, and discuss the underlying ideas on which they are based. We critique existing approaches in order to clarify their respective strengths and weaknesses.

REFERENCES

• 1: R. Ayani. A Parallel Simulation Scheme Based on the Distance Between Objects. Proceedings of the SCS Multiconference on Distributed Simulation, 21(2), March 1989.
• 2: W. L. Bain and D. S. Scott. An Algorithm for Time Synchronization in Distributed Discrete Event Simulation. Proceedings of the SCS Multiconference on Distributed Simulation, 19(3), July 1988.
• 3: B. Beckman et al. Distributed Simulation and Time Warp: Part 1: Design of Colliding Pucks. Proceedings of the SCS Multiconference on Distributed Simulation, 19(3):56--60, July 1988.
• 4: O. Berry. Performance Evaluation of the Time Warp Distributed Simulation Mechanism. Technical Report, University of Southern California, May 1986.
• 5: W. Biles et al. Statistical Considerations in Simulation on a Network of Microcomputers. 1985 Winter Simulation Conference Proceedings, 388--393, December 1985.
• 6: R. E. Bryant. Simulation of Packet Communication Architecture Computer Systems. MIT-LCS-TR-188, Massachusetts Institute of Technology, 1977.
• 7: A. Chandak and J. C. Browne. Vectorization of Discrete Event Simulation. Proceedings of the 1983 International Conference on Parallel Processing, 359--361, August 1983.
• 8: K. M. Chandy and R. Sherman. The Conditional Event Approach to Distributed Simulation. Proceedings of the SCS Multiconference on Distributed Simulation, 21(2), March 1989.
• 9: K. M. Chandy and R. Sherman. Space, Time, and Simulation. Proceedings of the SCS Multiconference on Distributed Simulation, 21(2), March 1989.
• 10: K. M. Chandy and J. Misra. Distributed Simulation: A Case Study in Design and Verification of Distributed Programs. IEEE Transactions on Software Engineering, SE-5(5):440--452, September 1979.
• 11: K. M. Chandy and J. Misra. Parallel Program Design, A Foundation. Addison-Wesley, 1988.
• 12: J. C. Comfort. The Simulation of a Master-Slave Event Set Processor. Simulation, 42(3):117--124, March 1984.
• 13: E. W. Dijkstra and C. S. Scholten. Termination Detection for Diffusing Computations. Information Processing Letters, 11(1):1--4, August 1980.
• 14: M. Ebling et al. An Ant Foraging Model Implemented on the Time Warp Operating System. Proceedings of the SCS Multiconference on Distributed Simulation, 21(2), March 1989.
• 15: R. M. Fujimoto. Performance Measurements of Distributed Simulation Strategies. Technical Report UU-CS-TR-87-026a, Dept. of Computer Science, University of Utah, Salt Lake City, November 1987.
• 16: R. M. Fujimoto. Time Warp on a Shared Memory Multiprocessor. Proceedings of the 1989 International Conference on Parallel Processing, August 1989.
• 17: R. M. Fujimoto. The Virtual Time Machine. International Symposium on Parallel Algorithms and Architectures, June 1989.
• 18: R. M. Fujimoto, J. Tsai, and G. Gopalakrishnan. Design and Performance of Special Purpose Hardware for Time Warp. Proceedings of the 15th Annual Symposium on Computer Architecture, June 1988.
• 19: A. Gafni. Rollback Mechanisms for Optimistic Distributed Simulation Systems. Proceedings of the SCS Multiconference on Distributed Simulation, 19(3):61--67, July 1988.
• 20: J. B. Gilmer. An Assessment of Time Warp Parallel Discrete Event Simulation Algorithm Performance. Proceedings of the SCS Multiconference on Distributed Simulation, 19(3):45--49, July 1988.
• 21: B. Groselj and C. Tropper. A Deadlock Resolution Scheme for Distributed Simulation. Proceedings of the SCS Multiconference on Distributed Simulation, 21(2), March 1989.
• 22: B. Groselj and C. Tropper. Pseudosimulation: An Algorithm for Distributed Simulation with Limited Memory. International Journal of Parallel Programming, October 1987.
• 23: B. Groselj and C. Tropper. The Time of Next Event Algorithm. Proceedings of the SCS Multiconference on Distributed Simulation, 19(3), July 1988.
• 24: P. Heidelberger. Statistical Analysis of Parallel Simulations. 1986 Winter Simulation Conference Proceedings, 290--295, December 1986.
• 25: P. Hontalas et al. Performance of the Colliding Pucks Simulation on the Time Warp Operating System. Proceedings of the SCS Multiconference on Distributed Simulation, 21(2), March 1989.
• 26: D. R. Jefferson. Virtual Time. ACM Transactions on Programming Languages and Systems, 7(3):404--425, July 1985.
• 27: S. Lavenberg and R. Muntz. Performance Analysis of a Rollback Method for Distributed Simulation. In Performance '83, Elsevier Science, North Holland, 1983.
• 28: Y. Lin and E. Lazowska. Exploiting Lookahead in Distributed/Parallel Simulation. Technical Report, Dept. of Computer Science, University of Washington, Seattle, Washington, 1989.
• 29: Y. Lin and E. Lazowska. Optimal Performance of Time Warp Simulation and a Comparison with Chandy Misra Approach. Technical Report, Dept. of Computer Science, University of Washington, Seattle, Washington, 1989.
• 30: B. Lubachevsky. Efficient Distributed Event-Driven Simulations of Multiple-Loop Networks. Communications of the ACM, 32(1):111--123, January 1989.
• 31: B. Lubachevsky. Scalability of the Bounded Lag Distributed Discrete Event Simulation. Proceedings of the SCS Multiconference on Distributed Simulation, 21(2), March 1989.
• 32: V. Madisetti, J. Walrand, and D. Messerschmitt. WOLF: A Rollback Algorithm for Optimistic Distributed Simulation Systems. 1988 Winter Simulation Conference Proceedings, December 1988.
• 33: J. Misra. Distributed-Discrete Event Simulation. ACM Computing Surveys, 18(1):39--65, March 1986.
• 34: D. Mitra and I. Mitrani. Analysis and Optimum Performance of Two Message Passing Parallel Processors Synchronized by Rollback. In Performance '84, Elsevier Science, North Holland, 1984.
• 35: D. M. Nicol. The Cost of Conservative Synchronization in Parallel Discrete Event Simulations. Technical Report, Department of Computer Science, College of William and Mary, June 1989.
• 36: D. M. Nicol. Parallel Discrete-Event Simulation of FCFS Stochastic Queueing Networks. Parallel Programming: Experiences with Applications, Languages and Systems, 23(9):124--137, September 1988. ACM SIGPLAN Notices.
• 37: J. K. Peacock, J. W. Wong, and E. G. Manning. Distributed Simulation Using a Network of Processors. Computer Networks, 3(1):44--56, February 1979.
• 38: M. Presley et al. Benchmarking the Time Warp Operating System with a Computer Network Simulation. Proceedings of the SCS Multiconference on Distributed Simulation, 21(2), March 1989.
• 39: D. A. Reed, A. D. Malony, and B. D. McCredie. Parallel Discrete Event Simulation Using Shared Memory. IEEE Transactions on Software Engineering, 14(4):541--553, April 1988.
• 40: P. L. Reiher, R. M. Fujimoto, S. Bellenot, and D. Jefferson. Cancellation Strategies in Optimistic Execution Systems. submitted for publication.
• 41: P. L. Reiher, F. Wieland, and D. Jefferson. Limitation of Optimism in the Time Warp Operating System. 1989 Winter Simulation Conference Proceedings, December 1989.
• 42: P. F. Reynolds Jr. A Shared Resource Algorithm for Distributed Simulation. Proceedings of the 9th Annual Symposium on Computer Architecture, 10(3):259--266, April 1982.
• 43: L. M. Sokol, D. P. Briscoe, and A. P. Wieland. MTW: A Strategy for Scheduling Discrete Simulation Events for Concurrent Execution. Proceedings of the SCS Multiconference on Distributed Simulation, 19(3), July 1988.
• 44: W. K. Su and C. L. Seitz. Variants of the Chandy-Misra-Bryant Distributed Discrete-Event Simulation Algorithm. Proceedings of the SCS Multiconference on Distributed Simulation, 21(2), March 1989.
• 45: D. B. Wagner and E. D. Lazowska. Parallel Simulation of Queueing Networks: Limitations and Potentials. Proceedings of 1989 ACM SIGMETRICS and PERFORMANCE '89, 17(1), May 1989.
• 46: D. B. Wagner, E. D. Lazowska, and B. N. Bershad. Techniques for Efficient Shared-Memory Parallel Simulation. Proceedings of the SCS Multiconference on Distributed Simulation, 21(2), March 1989.
• 47: F. Wieland et al. Distributed Combat Simulation and Time Warp: The Model and its Performance. Proceedings of the SCS Multiconference on Distributed Simulation, 21(2), March 1989.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory
          Subjects: Types of simulation (continuous and discrete)*

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

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

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Performance