Proceedings of the 1992 Winter Simulation Conference ed. J. J. Swain, D. Goldsman, R. C. Crain, and J. R. Wilson

RUN LENGTH CONTROL USING PARALLEL SPECTRAL METHOD

Kimmo E. E. Raatikainen

University of Helsinki, Department of Computer Science Teollisuuskatu 23, SF-00510 Helsinki, FINLAND

ABSTRACT

Distributed and parallel simulation has been a popular research topic in recent years. The research has primarily concentrated on correctness and speedup of distributed simulation. The statistical output analysis that is an essential part of simulating stochastic systems has attained only small attention.

Parallel simulation is often mentioned as an attractive alternative for steady-state simulations. However, empirical results are not widely reported. In this study we present results of the parallel spectral method. The results are based on 12 simulation models executed in simulated parallel environment and on measured executing times and message passing delays.

1 INTRODUCTION

Since the fundamental contribution by Chandy and Misra (1981) a number of articles has been published covering various aspects of distributed and parallel simulation. The research has primarily concentrated on distributed simulation in which several processors cooperate on a single realization of the stochastic process simulated. The empirical studies | see e.g. Baik and Zeigler (1985), Comfort (1984), Duda (1989), Fujimoto (1988), Nicol (1988a and 1988b), Reed (1985), Reed and Malony (1988), Reed et al. (1988), Reynolds and Kuhn (1987), Wagner and Lazowska (1989) | have reported only modest speedups unless the queueing process simulated has a special structure.

Parallel simulation in which each processor simulates independent realizations of the stochastic process is an attractive alternative for steady-state simulations, see e.g. Rego and Sunderam (1992). The attraction arises from the fact that only minor modifications to uniprocessor simulation software are needed. The most notable drawback is that the size of the

simulation model is restricted. Each processor must be able to simulate the whole model.

The research papers have considered primarily the correctness and speedup of the simulation. On the the other hand, statistical aspects of simulation have attained only minor attention. Notable exceptions include Heidelberger (1986 and 1988) and Glynn and Heidelberger (1990 and 1992). However, if we simulate a system having random input processes, the simulation study is only a programming exercise if the analysis of output processes is not properly carried out Pawlikowski (1990, p. 124).

In this paper we examine empirically one possible scheme for run length control in parallel simulation. The objective of run length control is to terminate the simulation as soon as the results are estimated to meet the given accuracy requirements. The importance of sequential estimation is widely recognized when stochastic queueing systems are examined through simulation.

The method examined combines the spectral method introduced in Heidelberger and Welch (1981) and the method of independent replications. Our objective is to find out whether a fixed number of independent replications executed in parallel and the spectral method can provide estimates that are accurate enough. Our second objective is to examine practical speedups gained through parallel execution. Finally, we want to learn the limitations of the method proposed.

In Section 2 we describe the method of parallel batch means. We give a brief mathematical description of the method. In addition, we outline the implementation. In Section 3 we report the observed coverages and estimated expected practical speedups. The results are based on 12 simulation models executed in simulated parallel environment and on measured executing times and message passing delays.

594