Browse Prior Art Database

Optimistic Parallel Simulation of Continuous Time Markov Chains Using Uniformization

IP.com Disclosure Number: IPCOM000121266D
Original Publication Date: 1991-Aug-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 5 page(s) / 223K

Publishing Venue

IBM

Related People

Heidelberger, P: AUTHOR [+2]

Abstract

Discrete event simulations can be computationally expensive. Therefore, researchers have looked to parallel processing techniques to speed up such simulations. There are currently two general approaches to parallel simulation: optimistic and conservative. (See (1) for a more complete discussion and a thorough bibliography.) In optimistic (Time Warp) simulations, a processor simulates events even though it may receive messages from other processors with a simulation time stamp in its past. In such cases, a rollback mechanism is employed to guarantee correctness. In conservative simulations, no processor simulates an event unless it is sure that it will not receive a message from another processor in its simulation past.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 27% of the total text.

Optimistic Parallel Simulation of Continuous Time Markov Chains Using
Uniformization

      Discrete event simulations can be computationally
expensive. Therefore, researchers have looked to parallel processing
techniques to speed up such simulations.  There are currently two
general approaches to parallel simulation: optimistic and
conservative.  (See (1) for a more complete discussion and a thorough
bibliography.)  In optimistic (Time Warp) simulations, a processor
simulates events even though it may receive messages from other
processors with a simulation time stamp in its past.  In such cases,
a rollback mechanism is employed to guarantee correctness.  In
conservative simulations, no processor simulates an event unless it
is sure that it will not receive a message from another processor in
its simulation past.

      We describe an optimistic parallel simulation approach that is
valid for certain Continuous Time Markov Chains (CTMCs). The
technique is based on uniformization (see (2,3)). Uniformization
allows processors to easily agree upon exactly what times they may
exchange messages.  For Time Warp simulations, this reduces state
saving overhead, simplifies some operations, and permits some new
possibilities.
Notation

      Suppose there are P processors.  Let X(t) = (X (1,t), ..., X(P,
t)) be a CTMC with generator matrix Q = (Q(s,s')). We assume that
processor i is responsible for maintaining that part of the state as
represented by X(i,t).  We assume that there are two types of
transitions: internal and external.  A transition is internal to
processor i if that transition only causes X(i,t) to change.  An
internal transition does not require the processor to notify any
other processors.  Let S(i,i) denote the set of internal transitions
to processor i.  External transitions are assumed to require
communication between two processors, and that two state components,
say X(i,t) and X(j,t)(i * j), change.  We view this as an event
occurring on processor i that triggers a change on processor j.  We
let S(i,j) denote the set of external transitions on processor i
requiring a message to be sent to processor j.  For example, in a
queueing network simulation, consider the event of a job completing
service at queue k and being routed to queue k'. If queues k and k'
are both managed by the same processor, then the transition is
internal; otherwise, it is external.
    Let g(i,j) / sup { Q (s,s') :(s,s') e S(i,j)}.  Let g =
S{i,j}g(i,j).
We assume that g < B, so that the chain can be uniformized with
uniformization rate g.  Let P (i,j) = g(i,j)/g.  We assume that N
transitions of the (uniformized) chain are to be simulated.
The Algorithm

      Processors first generate a global list E of potential
transitions.  This is done by randomly sampling the distribution
P(i,j) N times.  If (i,j) is drawn on transition n, then there is the
potential of a transition in S(i,j) occurring at (discrete) time n.
We denot...