Analysis of parallel replicated simulations under a completion time constraint

ABSTRACT

We analyze properties associated with a simple yet effective way to exploit parallel processors in discrete event simulations: averaging the results of multiple, independent replications that are run, in parallel, on multiple processors. We focus on estimating expectations from terminating simulations, or steady state parameters from regenerative simulations. We assume that there is a CPU time constraint, t, on each of P processors. Unless the replication lengths are bounded, one must be willing to simulate beyond any fixed, finite time t on at least some processors in order to always obtain a strongly consistent estimator (as the number of processors increases). We therefore consider simulation experiments in which t is viewed as either being a strict constraint, or a guideline, in which case simulation beyond time t is permitted. The statistical properties, including strong laws, central limit theorems, bias expansions, and completion time distributions of a variety of estimators obtainable from such an experiment are derived. We propose an unbiased estimator for a simple mean value. This estimator requires preselecting a fraction of the processors. Simulation beyond time t may be required on a preselected processor, but only if no replications have yet been completed on that processor. being a strict constraint, or a guideline, in which case simulation beyond time t is permitted. The statistical properties, including strong laws, central limit theorems, bias expansions, and completion time distributions of a variety of estimators obtainable from such an experiment are derived. We propose an unbiased estimator for a simple mean value. This estimator requires preselecting a fraction of the processors. Simulation beyond time t may be required on a preselected processor, but only if no replications have yet been completed on that processor.

REFERENCES

• 1: V. C. Bhavsar , J. R. Isaac, Design and analysis of parallel Monte Carlo algorithms, SIAM Journal on Scientific and Statistical Computing, v.8 n.1, p.73-95, January 2, 1987 [doi>10.1137/0908014]
• 2: BILMNGSLE~, P. Convergence of Probability Measures Wiley, New York, 1968.
• 3: CHOW, Y. S., HsIuN(~, C. A, A~D LAI, T. L. Extended renewal theory and moment convergence in Anscombe's theorem. Ann Probab~ltty 7 (1979), 304-318.
• 4: CHUNG, K L. A Course in Probabzht~ Theory 2nd ed., Academic Press, New York, 1974.
• 5: Cox, D, R. Renewal Theory. Methuen, London, 1962.
• 6: CRAftieR, H. Mathematzcal Methods of Statistics Princeton Umversity Press, Princeton, N.J., 1946.
• 7: CRANE, M. A, AND IGLm~ART, D L. Simulating stable stochastic systems, III: Regenerative processes and discrete event simulations. Oper. Res. 23 (1975), 33 45
• 8: DAWD, H A. Order Stat*stzcs. 2nd ed, Wiley~ New York, 1981.
• 9: FELLER, W. An Introduction to Probability Theocv and Its Applications, Vol. I 3rd ed., Wiley, New York, 1968.
• 10: FU.JIMOq'O, R. M. Time warp on a shared memory multiprocessor In Proceed~.nEs of the 1989 Internatmnal Conference on Parallel Processing III. The Pennsylvania State University Press, 1989, 242-249.
• 11: 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]
• 12: GLYNN, P W A low bias steady-state estimator for equilibrmm processes. Tech., Rep. Dept. of Industrial Engineering, Univ. of W~sconsin, Madison, 1987
• 13: GLYNN, P. W, AND HEmELBERGER, P. Analysis of initial transient deletion for rephcated steady-state simulations IBM Res Rep. RC 15259. Yorktown Heights, N.Y, 1989.
• 14: GLYNN, P. W., AND HEIDELBERGER, P Analysis of initial transmnt deletion for parallel steady-state simulations. IBM Res. Rep. RC 15260. Yorktown Hmghts, N.Y, 1989.
• 15: GLYNN, P. W, AND HEmELBERCER, P. Jackknifing under a budget constraint. IBM Res. Rep RC 15261 Yorktown Hmghts, N.Y, 1989.
• 16: Peter W. Glynn , Philip Heidelberger, Bias properties of budget constrained simulations, Operations Research, v.38 n.5, p.801-814, Sep./Oct. 1990 [doi>10.1287/opre.38.5.801]
• 17: GLYNN, P. W., AND HErDELBERGER, P Expemments with initial transient deletion for parallel, replicated steady-state simulations. IBM Res Rep RC 15770 Yorktown Heights, N Y., 1990.
• 18: GoH, P., HEmEI~BER(;ER, P., TOWSLE~, D, AND YU, Q Processor assignment and synchronization in parallel simulatmn of multistage interconnection networks. In Distributed Slmulatmn. D. Nicol, Ed. The Society for Computer Smmlation International, 1990, 181-187
• 19: Philip Heidelberger, Statistical analysis of parallel simulations, Proceedings of the 18th conference on Winter simulation, p.290-295, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318448]
• 20: 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]
• 21: KA~HN, S., AND TAYLOR, H.M. A F*rst Course ~n Stochastic Processes. 2nd ed., Academic Press, New York, 1975.
• 22: K~M~S, W K Completeness and unbmsed estimatmn for sum-quota sampling J Am. Star. Assoc. 81 (1986), 1070-1073.
• 23: L~ADBErT~, M. R., L~ND(mEN, G, AND ROOTZ~N, H . Extremes and Related Properties of Random Sequences and Processes. Springer-Verlag, New York, 1983.
• 24: L~}~MANN, E.L. Theory of Point Estimation. Wiley, New York, 1983,
• 25: B. D. Lubachevsky, Efficient distributed event-driven simulations of multiple-loop networks, Communications of the ACM, v.32 n.1, p.111-123, Jan. 1989 [doi>10.1145/63238.63247]
• 26: MEKETON, M. S., AND HEIDELBERGER, P. A renewal theoretic approach to bias reduction in regenerative simulations. Manage. Sci. 28 (1982), 173-181.
• 27: MmLER, R. G. The jackknife--A review. Biometr~ka 61 (1974), 1-15.
• 28: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 29: 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
• 30: NICOL, D., ED. Distributed Simulation. Simulation Series 22, No. 2. The Society for Computer Simulation International, San Diego, Calif., 1990.
• 31: PATHAK, P.K. Unbiased estimation in fixed cost sequential sampling schemes. Ann. Star. 4 (1976), 1012-1017.
• 32: RIGRTER, R., AND WALRAND, J.C. Distributed simulation of discrete event systems. Proc. IEEE 77 (1989), 99-113.
• 33: Ross, S.M. Stochastic Processes. Wiley, New York, 1983.
• 34: SMITH, W.L. Regenerative stochastic processes. Proc. Roy. Soc. A. 232 (1955), 6-31.
• 35: SMITH, W. L. Renewal theory and its ramifications. J. Roy. Stat. Soc. B. 20 (1958), 243-302.
• 36: UNCER, B., AND FUJIMOTO, R., EDS. Distributed Simulation, 1989. Simulation Series 21, No. 2. The Society for Computer Simulation International, San Diego, Calif., 1989.
• 37: Brian W. Unger, Distributed simulation, Proceedings of the 20th conference on Winter simulation, p.198-205, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318189]
• 38: W. Whitt, Planning queueing simulations, Management Science, v.35 n.11, p.1341-1366, Nov. 1989 [doi>10.1287/mnsc.35.11.1341]
• 39: Yu, Q., TOWSLEY, D., AND HEIDELBERGER, P. Time-driven parallel simulation of multistage interconnection networks. In Distributed S~mulation, 1989. B. Unger and R. Fujimoto, Eds. The Society for Computer Simulation International, San Diego, Calif, 1989, 191-196.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

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

General Terms:
Algorithms, Theory

Keywords:
bias, discrete event simulation, estimation, multiple replications, parallel processing, renewal theory