Analysis of Parallel, Replicated Simulations Under a Completion Time Constraint

摘要

This paper analyzes properties associated with a simple yet effective way toexploit 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 Central Processing Units 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 pre-selecting a fraction of the processors. Simulation beyond time t may be required on pre-selected processor, but only if no replications have yet been completed on that processor. (Author) (kr)