An algorithm for parallel discrete event simulation using common memory

ABSTRACT

Most work on parallel discrete event simulation has been based on a distributed model of computation in which processes can only communicate through message passing. Here we study parallel discrete event simulation under a common memory model of computation. An algorithm for parallel discrete event simulation is developed based on the assumption that every process has direct access to the state of any other process. The objective is to avoid the high overhead associated with null messages and request messages in distributed algorithms. This algorithm is then compared to distributed synchronization algorithms.

REFERENCES

• 1: Bain, W.L. and D.S. Scott. 1988. "An Algorithm for Time Synchronization ia Distributed Discrete Eveat Simulation." In Distributed Simulation: 30-33. Society for Computer Simulation.
• 2: Bryant, R.t~. 1979. "Simulation on a Distributed System." In Proceedings of the Firs$ International Conference on Distributed Computing Systems: 544-552. IEEE.
• 3: Chandy, K.M. and J. Misra. 1979. "Distributed Simulation: A Case Study in Design and Verification of Distributed Programs." IEEE Transactions on Software Engineering SE-5, no. 5: 440-452.
• 4: 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]
• 5: Cot~, B.A. and R.G. Sargent. 1988. "Research Report on Parallel Discrete Event Simulation." Simulation Research Group, Syracuse University, Syracuse, NY, 13244.
• 6: Encore 1986. "Multimax Technical Summary." Encore Computer Corporation, 257 Cedar Hill Street, Marlboro, MA 01752.
• 7: 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]
• 8: Lubachevsky, B.D. 1988. "Bounded L~g Distributed Discrete Event Simulation." In Distributed Simulation: 183-191. Society for Computer Simulation.
• 9: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 10: Peacock, J.K.; J.W. Wong; and E.G. Manning. 1979. "Distributed Simulation Using a Network of Processors." Computer Networks 3, no. 1: 44-56.
• 11: 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
• 12: Bernard P. Zeigler, Theory of Modelling and Simulation, Krieger Publishing Co., Inc., Melbourne, FL, 1984

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:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Distributed; Parallel

General Terms:
Algorithms, Design, Performance, Theory