Discrete Event Simulations and Parallel Processing: Statistical Properties

This paper addresses statistical issues that arise when discrete event, or Monte Carlo, simulations are run on parallel processing computers. In particular, the statistical properties of estimators obtained by running parallel independent replications on a multiple processor computing system are considered. Because of the effects of parallelism, care must be taken in order to obtain estimators with the proper statistical properties. A variety of estimators are considered. The convergence properties, including strong laws, central limit theorems and bias expansions of these estimators are derived. It is shown that some of the more obvious estimators are guaranteed to converge to the wrong quantity as the number of processors increases. Strong laws and central limit theorems for completion times of the estimators are also given. The application of results from reliability and scheduling theory yields bounds on expected completion times under a variety of distributional assumptions. Based on these results, it does not appear possible to obtain a strongly consistent estimate in finite expected time as the number of processors increases, unless the computational time to complete a single replication is bounded.