Statistical analysis of parallel simulations

ABSTRACT

This paper addresses statistical issues that arise when discrete event simulations are run on parallel processing computers. First, the statistical properties of estimates obtained by parallel distributed simulation and parallel independent replications are compared. This comparison shows that, when estimating steady state quantities, the run length, the strength of the initial transient and the asymptotic variance must be taken into account in addition to the parallel processing speed-up and the number of processors in order to determine which method is statistically more efficient. Second, the statistical properties of estimators of transient quantities obtained by the method of parallel independent replications are considered. The analysis shows that strongly consistent estimates are not obtained in finite expected time as the number of processors increases unless the computational time to complete a single replication is bounded.

REFERENCES

• 1: Berry, O. and Jefferson, D. (1985). Critical Path Analysis of Distributed Simulation. Distributed Simulation 1985, The 1985 Society for Computer Simulation Multiconference, San Diego, California.
• 2: Billingsley, P. (1968). Convergence of Probability Measures. John Wiley and Sons, Inc., New York.
• 3: Blomqvist, N. (1967). The Covarianee Function of the M/G/1 Queue. Skand. Akt. Tidskr., 50, 157-174.
• 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: John Craig Comfort, The design of a multi-microprocessor based simulation computer - II, Proceedings of the 16th annual symposium on Simulation, p.197-209, March 18-20, 1983, Tampa, Florida, United States
• 6: Comfort, J.C. (1984). The Simulation of a Master-Slave Event Set Processor. Simulation 42, 117-124.
• 7: Crane, M.A. and Iglehart, D.L. (1975). Simulating Stable Stochastic Systems, III: Regenerative Processes and Discrete Event Simulations. Operations Research 23, 33-45.
• 8: Doob, J.L. (1953). Stochastic Processes. John Wiley and Sons, Inc., New York.
• 9: Heidelberger, P. (1980). Variance Reduction Techniques for the Simulation of Markov Processes, I: Multiple Estimates. IBM Journal of Research and Development 24, 570-581.
• 10: Heidelberger, P. (1986). Discrete Event Simulations and Parallel Processing: Statistical Properties. IBM Research Report (to appear), Yorktown Heights, New York.
• 11: Jefferson, D. and Sowizral, H. (1985). Fast Concurrent Simulation Using the Time Warp Mechanism. Distributed Simulation 1985, The 1985 Society for Computer Simulation Multiconference, San Diego, California.
• 12: Karlin, S. and Taylor, H.M. (1975). A First Course in Stochastic Processes, Second Edition. Academic Press, New York.
• 13: M. S Lakshmi, A Study and Analysis of Performance of Distributed Simulation, University of Texas at Austin, Austin, TX, 1987
• 14: Meketon, M.S. and Heidelberger, P. (1982). A Renewal Theoretic Approach to Bias Reduction in Regenerative Simulations. Management Science 28, 173-181.
• 15: Dana L. Wyatt , Sallie Sheppard , Robert E. Young, An experiment in microprocessor-based distributed digital simulation, Proceedings of the 15th conference on Winter simulation, p.271-278, December 12-14, 1983, Arlington, Virginia, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  G. Mathematics of Computing

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

General Terms:
Design, Measurement, Performance, Theory