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 1991. 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. © 1991, ACM. All rights reserved.