A spectrum of options for parallel simulation

ABSTRACT

Conventional wisdom has it there are two basic approaches to parallel simulation: conservative (Chandy-Misra) and optimistic (time warp). All known protocols are thought to fall into one of these two classes. This dichotomy is false. There exists a spectrum of options that includes these approaches. We describe a design space that admits these as alternatives, we show how most of the well known parallel simulation approaches can be derived using our design alternatives, and we explore the implications of the existence of the design space we describe. In particular, we note there are many as yet unexplored approaches to parallel simulation.

REFERENCES

• Bain88: Bain, W. and D. Scott, "An Algorithm for Time Synchronization in Distributed Discrete Event Simulation," Proc., SCS Multi-conference, San Diego, CA, Feb., 1988.
• ChMi79: Chandy, K.M. and J. Misra, "Distributed Simulation: A Case Study in Design and Verification of Distributed Programs," IEEE Trans on Software Engineering., SE- 5,5, May, 1979, 440-452.
• ChMi81: 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]
• ChMi87: K. M Chandy , Jay Misra, Conditional Knowledge as a Basis for Distributed Simulation, California Institute of Technology, Pasadena, CA, 1987
• Chan88: Chandy, K.M., Private Communication.
• FJLO88: Geoffrey C. Fox , Mark A. Johnson , Gregory A. Lyzenga , Steve W. Otto , John K. Salmon , David W. Walker, Solving problems on concurrent processors. Vol. 1: General techniques and regular problems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• Fuji88: Fujimoto, R.M., "Performance Studies of Distributed Simulation Strategies," Proc., SCS Multi-conference, San Diego, CA, Feb., 1988.
• HaDo88: Hartrum, T.C. and B.J. Donlan, "Distributed Battlemanagement Simulation on a Hypercube," Proc,, SCS Multi-conference,, San Diego, CA, Feb., 1988.
• JeSo82: Jefferson, D. and H Sowizral, "Fast Concurrent Simulation Using the Time Warp Mechanism," A Rand Note, N- 1906-AF.
• Jeff85: 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]
• Kuma86: Devendra Kumar, Simulating feedforward systems using a network of processors, Proceedings of the 19th annual symposium on Simulation, p.127-144, March 12-14, 1986, Tampa, Florida, United States
• LCUW88: Lomow, G., et al., "A Performance Study of Time Warp," Proc., SCS Multi-conference,, San Diego, CA, Feb., 1988.
• Luba87: Lubachevsky, B., "Bounded Lag Distributed Discrete Event Simulation", Proc., SCS Multi-conference,, San Diego, CA, Feb., 1988.
• Misr86: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• Nico88: David M. Nicol, Parallel discrete-event simulation of FCFS stochastic queueing networks, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.124-137, July 19-21, 1988, New Haven, Connecticut, United States
• NiRe84: David M. Nicol , Paul F. Reynolds, Jr., Problem oriented protocol design, Proceedings of the 16th conference on Winter simulation, p.470-474, December 28-30, 1984, Dallas, TX
• PeWo78: Peacock, J.K., Wong, J,W. and E. Manning, "Distributed Simulation Using a Network of Processors," Computer Networks, 3, North Holland Pub., 1979, 44- 56.
• PeMa80: Peacock, J.K., Manning, E. and J.W. Wong, "Synchronization of Distributed Simulation Using Broadcast Algorithms," Computer Networks, North Holland Pub., 1980, 3-10.
• ReMa87: Daniel A. Reed , Allen D. Malony , Bradley D. McCredie, Parallel discrete event simulation: a shared memory approach, Proceedings of the 1987 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.36-38, May 11-14, 1987, Banff, Alberta, Canada
• ReMa88: Reed, M.A., and A.D. Maloney, "Parallel Discrete Event Simulat~Lon: The Chandy-Misra Approach", Proc., SCS Multi-conference,, San Diego, CA. Feb., 1988.
• Reyn82: Paul F. Reynolds, Jr., A shared resource algorithm for distributed simulation, Proceedings of the 9th annual symposium on Computer Architecture, p.259-266, April 26-29, 1982, Austin, Texas, United States
• Soko88: Sokol, L., et al. "MTW: A Strategy for Scheduling Discrete Events for concurrer, t Execution",Proc of SCS Multi-Conference," February, 1988, San Diego, 34-42.
• Theo84: Theofanos, "Distribute:d Simulation of Queueing Networks," Master's The.,;LS, The Univ of Virginia, }'an., 1984.
• Word88: Worden, J. "National Testbed Program," Proc of SCS Multi-Conference: Aerospace Simulation Ili," February, 1988, San Diego, CA.

INDEX TERMS

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

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

General Terms:
Design, Performance, Theory