Browse Prior Art Database

Conservative Parallel Simulation of Continuous Time Markov Chains Using Uniformization

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

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 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 39% of the total text.

Conservative 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 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.  Improvements to conservative algorithms include the
use of "lookahead", which allows processors to look into its future
and thereby guarantee another processor that it will not send a
message with a time stamps earlier than a certain time, sometimes
called an appointment (see [2]).  However, the ability to compute
lookahead as previously described is problem dependent.

      We describe a conservative parallel simulation approach that is
valid for certain Continuous Time Markov Chains (CTMCs). The
technique is based on appointments and uniformization (see [3,4]).
Uniformization allows processors to easily agree upon exactly what
times they may exchange messages, thus providing a general means for
computing and exploiting lookahead.
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 (uniformize...