High performance parallelized discrete event simulation of stochastic queueing networks

ABSTRACT

Queueing network simulations provide a stress-test for the study of parallel discrete-event simulation because each event involves some synchronization overhead, and very little computation. In this paper we describe techniques for optimizing the performance of large queueing network simulations using a shared-memory multiprocessor. We give empirical data showing that good speedups can sometimes be achieved.

REFERENCES

• 1: Chandy, K.M., and Misra, a. (1979). Distributed simulation: a case study in design and verification of distributed programs. IEEE Trans. on Software Engineering, 5(5):440--452, September 1979.
• 2: Fujimoto, R.M., (1988). Performance measurements of distributed simulation strategies. In Proceedings o} the 1988 SCS Conference on Distributed Simulation, pages 14-20, Sail Diego, CA, 1988.
• 3: Victor Paul Holmes, Parallel algorithms for multiple processor architectures., 1978
• 4: 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]
• 5: Lubachevsky, B. D. (1988). Bounded lag distributed discrete event simulation. In Proceedings of ihe I988 SCS Conference on Distributed Simulation, pages 183-191, San Diego, CA, 1988.
• 6: Nicholas Matelan, The FLEX/32 multicomputer, ACM SIGARCH Computer Architecture News, v.13 n.3, p.209-213, June 1985
• 7: Keith W. Miller , David M. Nicol, Implementation parallelized queueing network simulations using FORTRAN and data abstraction, Proceedings of the 20th conference on Winter simulation, p.333-338, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318210]
• 8: Nicol, D. M. (1984). The performance of ,ynchroniz~n:7 networks. Master's thesis, Department of Computer S,:ience, University of Virginia, January 1984.
• 9: 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
• 10: 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
• 11: Daniel A. Reed , Allen D. Malony , Bradley McCredie, Parallel Discrete Event Simulation Using Shared Memory, IEEE Transactions on Software Engineering, v.14 n.4, p.541-553, April 1988 [doi>10.1109/32.4677]

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

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes; Queueing theory

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

General Terms:
Design, Measurement, Performance, Theory