Search

This paper describes an approach to discrete event simulation modeling that appears to be effective for developing portable and efficient execution of models of large distributed systems and communication networks. In this approach. the modeler develops sub-models using an existing sequential simulation modeling tool, using the full expressive power of the tool. A set of modeling language extensions permit automatically synchronized communication between sub-models; however the automation requires that any such communication must take a non-zero amount of simulation time. Within this modeling paradigm, a variety of conservative synchronization protocols can transparently support conservative execution of sub-models on potentially different processors. A specific implementation of this approach. U P.S. (Utilitarian Parallel Simulator), is described, along with performance results on the Intel Paragon.

We have previously shown that the mathematical technique of uninformization can serve as the basis of synchronization for the parallel simulation of continuous-time Markov chains. This paper reviews the basic method and compares five different methods based on uninformization, evaluating their strengths and weaknesses as a function of problem characteristics. The methods vary in their use of optimism, logical aggregation, communication management, and adaptivity. Performance evaluation is conducted on the Intel Touchstone Delta multiprocessor, using up to 256 processors.

This paper considers efficient simulation techniques for estimating steady-state quantities in models of highly dependable computing systems with general component failure and repair time distributions. Earlier approaches in this application setting for steady-state estimation rely on the regenerative method of simulation which can be used when the failure time distributions are exponentially distributed. However, when the failure times are generally distributed the regenerative structure is lost and a new approach must be taken. The approach we take is to exploit a ratio representation for steady-state quantities in terms of cycles that are no longer independent and identically distributed. A splitting technique is used in which importance sampling is used to speed up the simulation of rare system failure events during a cycle, and standard simulation is used to estimate the expected cycle length. Experimental results show that the method is effective in practice.

A simple and effective way to exploit parallel processors in discrete event simulations is to run multiple independent replications, in parallel, on multiple processors and to average the results at the end of the runs. We call this the method of parallel replications. This paper is concerned with using the method of parallel replications for estimating steady-state performance measures. We report on the results of queueing estimators that can be formed using this method. The theoretical asymptotic properties of these estimators were determined in Glynn and Heidelberger (1989a and 1989b). Both the theory and the experimental results reported here strongly indicate that a nonstandard (in the context of steady-state simulation), yet easy to apply, estimator procedure is required on highly parallel machines. This nonstandard estimator is a ratio estimator. The experiments also show that use of the ratio estimator is advantageous even on machines with only a moderate degree of parallelism. (kr)

This paper analyzes 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 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.

The problem of computing dependability measures of repairable systems with general failure, repair and maintenance processes is a hard problem to solve in general either by analytical or by numerical methods. Monte Carlo simulation could be used to solve this problem, however, standard simulation takes a very long time to estimate system reliability and availability with reasonable accuracy because typically the system failure is a rare event. When the failure and repair time distributions are exponential, importance sampling has been used successfully in the past to reduce simulation run lengths. In this paper, we extend the applicability of importance sampling to non-Markovian models with general failure and repair time distributions. We show that by carefully selecting a heuristic for importance sampling, orders of magnitude reduction in simulation run-lengths can be obtained. We illustrate the effectiveness of the technique by modeling a large repairable computing system. Also, we study the effect of periodic maintenance on systems with components having increasing and decreasing failure rate.

In this paper we present a unified framework for simulating Markovian models of highly dependable systems. Since the failure event is a rare event, the estimation of system dependability measures using standard simulation requires very long simulation runs. We show that a variance reduction technique called Importance Sampling can be used to speed up the simulation by many orders of magnitude over standard simulation. This technique can be combined very effectively with regenerative simulation to estimate measures such as steady- state availability and mean time to failure. Moreover, it can be combined with conditional Monte Carlo methods to quickly estimate transient measures such as reliability, expected interval availability and the distribution of interval availability. We show the effectiveness of these methods by using them to simulate large dependability models. We also discuss how these methods can be implemented in a software package to compute both transient and steady-state measures simultaneously from the same sample run.

This paper considers the problem of estimating a parameter alpha that can be expressed as a nonlinear function of samples means. We develop a jackknife estimator for alpha that is appropriate to computational settings in which the total computer budget to be used is constrained. Despite the fact that the jackknifed observations are not i.i.d., we are able to show that our jackknife estimator reduces bias without increasing asymptotic variance. This makes the estimator particularly suitable for small sample applications. Because a special case of this estimator problem is that of estimating a ratio of two means, the results in this paper are pertinent to regenerative steady-state simulations., Prepared in cooperation with IBM T.J. Watson Research Center, Yorktown Heights, NY, 10598.

Suppose two alternative designs for a stochastic system are to be compared. These two systems can be simulated independently or dependently. This paper presents a method for comparing two regenerative stochastic processes in a dependent fashion using common random numbers. A set of sufficient conditions is given that guarantees that the dependent simulations will produce a variance reduction over independent simulations. Numerical examples for a variety of simple stochastic models are included which illustrate the variance reduction achieved. (Author)

Simulators frequently wish to estimate parameters of the limiting distribution of stable stochastic processes. Several new methods for reducing the variance of such estimates will be proposed and discussed. The methods are applicable to regenerative Markov processes in both discrete and continuous time as well as to semi-Markov processes. The methods are similar to the technique of multiple control variables yet differ in the important respect that it is not necessary to calculate the means of the controls. This is because the controls are chosen in such a way that their means actually equal the parameter of interest. The methods do require a certain amount of computation to be done before the simulation begins, although their cost should be relatively minor compared with that of the simulation. Numerical results demonstrating the effectiveness of the techniques for a simple queueing model are presented. (Author)

Let (x sub n, n or = 0) be an irreducible, aperiodic, Markov chain with finite state space E, transition matrix P, and stationary distribution pi. Let f be a real valued function on E and define r = pi f. A method of reducing the variance of simulation estimates for r is presented. The method combines the techniques of numerical analysis and simulation by partially solving an appropriate system of linear equations using some matrix iterative procedure and then estimating the difference between the true and partial solutions via simulation. After k iterations of the iterative procedure, functions f sub nu, nu = 0, ..., k are defined so that r = pi f sub nu for each nu., See also AD-A051 431.

One of the main difficulties with the regenerative method of simulation is that even though a process may be known to be regenerative, regenerations may occur quite infrequently. A class of methods, based on Dynkin's formula, is considered that increases the frequency of regenerations when the process being simulated is a Markov chain. Instead of simulating the original Markov chain, a new Markov chain is simulated from which point estimates and confidence intervals for parameters of the original chain's stationary distribution may be formed. Because regenerations occur more frequently in the new chain, such confidence intervals will usually be shorter than is otherwise possible. (Author), See also report dated Oct 77, AD-A047 950.