Massively parallel and distributed simulation of a class of discrete event systems: a different perspective

ABSTRACT

In this paper we propose a new approach to parallel and distributed simulation of discrete event systems. Most parallel and distributed discrete event simulation algorithms are concerned with the simulation of one “large” discrete event system. In this case the computational intensity is due to the size and complexity of the simulated system. In contrast, we are interested in simulating a “large” number of “medium sized” systems. These are variants of a “nominal system” with different system parameter values or operation policies. The computational intensity in our case is due to the “large” number of simulated variants. Many simulation projects such as factor screening, performance modeling, and optimization require system performance evaluations at many parameter values; and others, we believe, could significantly benefit from them. There is considerable work in the literature on stochastic coupling of trajectories of parametric families of stochastic processes. Our approach can be viewed as the simulation of the coupled trajectories. We use a single clock mechanism that drives all trajectories simultaneously, hence the approach is called Single Clock Multiple System (SCMS) simulation. The single clock synchronizes all trajectories such that the “same” event occurs at the “same” time at all systems. This synchronization is the basis of our parallel and distributed algorithms. We focus on a particular implementation of the SCMS simulation using the so-called Standard Clock (SC) technique and also on the massively parallel implementation of the SC algorithms on the SIMD Connection Machine. Orders of magnitude of speedup is possible. Furthermore, the possibility of concurrent performance evaluation and comparison at many system parameter values offers new and significant opportunities for performance optimization.

REFERENCES

• 1: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 2: Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 3: CASSANDRAS, C. G., LEE, J. I., AND HO, Y.C. Efficient parametric analysis of performance measures for communications networks. IEEE J. Selected Areas Commun. 8, 9 (1990), 1709-1722.
• 4: CASSANDRAS, C. G., AND STRICKLAND, S. G. On-line sensitivity analysis of Markov chains. IEEE Trans. Autom. Contr. 34, (1989), 76 86.
• 5: FISlIMAN, G.S. Accelerated accuracy in the simulation of Markov chains. Oper. Res. 31, 3 (May-June 1983), 466-487.
• 6: FISHMAN, G.S. Accelerated convergence in the simulation of countably infinite state space Markov chains. Oper. Res. 31, 6 (Nov.-Dec. 1983), 1074-1089.
• 7: Fox, B.L. Generating Markov-chain transitions quickly: I. ORSA J. Comput. 2, 2 (Spring 1990), 126-135.
• 8: Bennett L. Fox , Peter W. Glynn, Discrete-time conversion for simulating finite-horizon Markov processes, SIAM Journal on Applied Mathematics, v.50 n.5, p.1457-1473, Oct. 1990 [doi>10.1137/0150085]
• 9: 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]
• 10: Peter W. Glynn , Philip Heidelberger, Analysis of parallel replicated simulations under a completion time constraint, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.1, p.3-23, Jan. 1991 [doi>10.1145/102810.102811]
• 11: P. W. Glynn , D. L. Iglehart, Simulation methods for queues: an overview, Queueing Systems: Theory and Applications, v.3 n.3, p.221-255, July 1988 [doi>10.1007/BF01161216]
• 12: Albert G. Greenberg , Boris D. Lubachevsky , Isi Mitrani, Algorithms for unboundedly parallel simulations, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.201-221, Aug. 1991 [doi>10.1145/128738.128739]
• 13: GREENBERG, A. G., SCHLUNK, O., AND WHITT, W. Using distributed-event parallel simulation to study departures from many queues in parallel. Manuscript~ 1992.
• 14: Philip Heidelberger, Discrete event simulations and parallel processing: statistical properties, SIAM Journal on Scientific and Statistical Computing, v.9 n.6, p.1114-1132, November 1988 [doi>10.1137/0909077]
• 15: David M. Nicol , Philip Heidelberger, Optimistic parallel simulation of continuous time Markov chains using uniformization, Journal of Parallel and Distributed Computing, v.18 n.4, p.395-410, Aug. 1993 [doi>10.1006/jpdc.1993.1073]
• 16: HEIDELB~RGER, P., AND NICOL, D.M. Simultaneous parallel simulations of continuous time Markov chains at multiple parameter settings. In Proceedings of 1991 W~nter S~mulation Conference, (Phoenix, Ariz., 1991), pp. 602-607.
• 17: Ho, Y. C., CASSANDRAS, C. G., AND MAKHLOUF, M.R. Parallel simulation of real txme systems via the standard clock approach Submitted to Mathematics and Computers in Simulation, 1991.
• 18: Yu-Chi Ho , Shu Li , Pirooz Vakili, On the efficient generation of discrete event sample paths under different system parameter values, Mathematics and Computers in Simulation, v.30 n.4, p.347-370, September 1988 [doi>10.1016/S0378-4754(98)90005-2]
• 19: Ho, Y C., SREENEVAS, R., AND VA~L~, P Ordinal optimization of DEDS. J. D~screte Event Dyn. Syst. 2 (1992), 61-88.
• 20: Averill M. Law , W. David Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1997
• 21: RIGHTER, R., AND WALRAND, J.C. Distributed simulation of discrete event systems. Proceedrags of the IEEE 77, 1 (1989), 99-113.
• 22: J George Shanthikumar, Uniformization and hybrid simulation/analytic models of renewal processes, Operations Research, v.34 n.4, p.573-580, July-Aug. 1986 [doi>10.1287/opre.34.4.573]
• 23: VAmLf, P. Using a standard clock technique for efficient s~mulation. Oper. Res. Lett. 10 (Nov. 1991), 445 452.
• 24: VAKILI, P., AND LAU, E. Massively parallel simulation and optimization of queuelng networks. In Proceedings of Interface 91: Interface between Computing Sczence and Statistics (Seattle, Wash., Apr. 1991), pp. 74-77.
• 25: VAKILI, r., MOLLAMUSTAFAOGLU, L., AND HO, Y.C. Mass~vely parallel simulation of a class of discrete event systems. In Proceedings of Frontiers '92. The 4th SymposLurn on the Frontzers of Massively Parallel Computatzon (McLean, Va, Oct. 1992), pp. 412-419

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Performance

Keywords:
event-driven simulation, parallel discrete-event simulation, speedup