Parallel execution for serial simulators

ABSTRACT

This article describes an approach to discrete event simulation modeling that appears to be effective for developing portable and efficient parallel execution of models of large distributed systems and communication networks. In this approach, the modeler develops submodels with an existing sequential simulation modeling tool, using the full expressive power of the tool. A set of modeling language extensions permits automatically sychronized communication between submodels; however, the automation requires that any such communication must take a nonzero amount of simulation time. Within this modeling paradigm, a variety of conservative synchronization protocols can transparently support conservative execution of submodels on potentially different processors. A specific implementation of this approach, U.P.S. (Utilitarian Parallel Simulator), is described, along with performance results on the Intel Paragon and on the IBM SP2.

REFERENCES

• 1: Marc Abrams, The object library for parallel simulation (OLPS), Proceedings of the 20th conference on Winter simulation, p.210-219, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318191]
• 2: BAGRODIA, R. L. 1993. A survival guide for parallel simulation. ORSA J. Comput. 5, 3, 234-235.
• 3: R. L. Bagrodia , Wen-Toh Liao, Maisie: A Language for the Design of Efficient Discrete-Event Simulations, IEEE Transactions on Software Engineering, v.20 n.4, p.225-238, April 1994 [doi>10.1109/32.277572]
• 4: Jeffrey P. Buzen, Computational algorithms for closed queueing networks with exponential servers, Communications of the ACM, v.16 n.9, p.527-531, Sept. 1973 [doi>10.1145/362342.362345]
• 5: Christopher D. Carothers , Richard M. Fujimoto , Yi-Bing Lin, A case study in simulating PCS networks using Time Warp, Proceedings of the ninth workshop on Parallel and distributed simulation, p.87-94, June 13-16, 1995, Lake Placid, New York, United States
• 6: Phillip M. Dickens , Philip Heidelberger , David M. Nicol, A distributed memory LAPSE: parallel simulation of message-passing programs, Proceedings of the eighth workshop on Parallel and distributed simulation, p.32-38, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 7: Richard W. Earnshaw , Alan Hind, A parallel simulator for performance modelling of broadband telecommunication networks, Proceedings of the 24th conference on Winter simulation, p.1365-1373, December 13-16, 1992, Arlington, Virginia, United States [doi>10.1145/167293.167951]
• 8: Richard M. Fujimoto, Parallel discrete event simulation, Communications of the ACM, v.33 n.10, p.30-53, Oct. 1990 [doi>10.1145/84537.84545]
• 9: FUJIMOTO, R. M. 1993. Parallel discrete event simulation: Will the field survive? ORSA J. Comput. 5, 3, 213-230.
• 10: Albert G. Greenberg , Boris D. Lubachevsky , David M. Nicol , Paul E. Wright, Efficient massively parallel simulation of dynamic channel assignment schemes for wireless cellular communications, Proceedings of the eighth workshop on Parallel and distributed simulation, p.187-197, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 11: GROSS, D. AND MILLER, D.R. 1984. The randomization technique as a modeling tool and solution procedure for transient Markov processes. Oper. Res. 32, 2 (March-April), 343-361.
• 12: GTU, INc. 1994. CPSim 1.0 User's Guide and Reference Manual, June, Arlington, VA.
• 13: P. Heidelberger , D. M. Nicol, Conservative Parallel Simulation of Continuous Time Markov Chains Using Uniformization, IEEE Transactions on Parallel and Distributed Systems, v.4 n.8, p.906-921, August 1993 [doi>10.1109/71.238625]
• 14: David M. Nicol, The cost of conservative synchronization in parallel discrete event simulations, Journal of the ACM (JACM), v.40 n.2, p.304-333, April 1993 [doi>10.1145/151261.151266]
• 15: 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
• 16: NICOL, D. AND FUJIMOTO, R. 1994. Parallel simulation today. Annals Oper. Res. 53, 249-286.
• 17: David Nicol , Philip Heidelberger, On extending more parallelism to serial simulators, Proceedings of the tenth workshop on Parallel and distributed simulation, p.202-205, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 18: David Nicol , Philip Heidelberger, On extending parallelism to serial simulators, Proceedings of the ninth workshop on Parallel and distributed simulation, p.60-67, June 13-16, 1995, Lake Placid, New York, United States
• 19: D. M. Nicol , C. C. Michael , P. Inouye, Efficient aggregation of multiple PLs in distributed memory parallel simulations, Proceedings of the 21st conference on Winter simulation, p.680-685, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76825]
• 20: PREISS, B.R. 1989. The Yaddes distributed discrete event simulation specification language and execution environments. In Distributed Simulation 1989, vol. 21, Society for Computer Simulation, San Diego, Calif., 139-144.
• 21: David O. Rich , Randy E. Michelsen, An assessment of the ModSim/TWOS parallel simulation environment, Proceedings of the 23rd conference on Winter simulation, p.509-518, December 08-11, 1991, Phoenix, Arizona, United States
• 22: Herb Schwetman, CSIM: a C-based process-oriented simulation language, Proceedings of the 18th conference on Winter simulation, p.387-396, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318464]
• 23: STEINMAN, J. S. 1991. Speedes: Synchronous parallel environment for emulation and discrete event simulation. In Advances in Parallel and Distributed Simulation, vol. 23, SCS Simulation Series, 95-103.
• 24: SWAIN, J. 1995. Simulation Survey. OR/MS Today (August), 64-79.
• 25: 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

INDEX TERMS

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

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

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

General Terms:
Algorithms, Performance, Verification

Keywords:
parallel simulation, simulation tools