Browse Prior Art Database

Parallel Simulation of Continuous Time Markov Chains Using Uniformization with Adaptive Rates

IP.com Disclosure Number: IPCOM000105236D
Original Publication Date: 1993-Jul-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 4 page(s) / 132K

Publishing Venue

IBM

Related People

Heidelberger, P: AUTHOR [+2]

Abstract

An algorithm, based on uniformization with adaptively controlled rates, for simulating certain Continuous Time Markov Chains on parallel processors is described.

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

Parallel Simulation of Continuous Time Markov Chains Using Uniformization with Adaptive Rates

      An algorithm, based on uniformization with adaptively
controlled rates, for simulating certain Continuous Time Markov
Chains on parallel processors is described.

      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.
Both optimistic and conservative approaches for parallel simulation
of certain Continuous Time Markov Chains (CTMCs) have been described
in [2,3,4,5].  These techniques are based on uniformization.
Uniformization allows processors to easily agree upon exactly what
times they need to exchange messages.  In the above algorithms, the
maximum possible rate of external events from processor i to
processor j, lambda (i,j), is identified for each pair of processors.
Poisson Processes, lbrace N(i,j, t) , t ge 0 rbrace with rates
lambda(i,j) are generated.  The times in these Poisson Processes are
used as synchronization points in the simulation.

      Let lambda(i,j,t) denote the actual (state-dependent) rate of
external i to j transitions at time t.  Suppose T is a random time
sampled from the Poisson Process lbrace N(i,j, t) rbrace.  Then T is
a real transition in the CTMC with probability lambda(i,j,T)/ lambda
(i,j) , and it is a "pseudo event"  with probability 1 -
lambda(i,j,T)/ lambda (i,j).

      Parallel simulations performed in this manner are efficient if
most events are internal (i.e., do not require communication between
two processors), and if there are not an excessive number of external
pseudo events resulting in an unnecessarily large number of
synchronizations.  If lambda(i,j,t) / lambda (i,j) ltlt 1 , for most
values of t, then the simulation may be inefficient.  Since
lambda(i,j) corresponds to the maximum possible rate of transitions
from i to j, it may be much larger than the typical rate of
transitions from i to j.  For example, in a queueing network, suppose
there are N queues assigned to processor i such that whenever a job
leaves one of these queues it goes to a queue assigned to processor
j.  Suppose the service times on each of these N queues have a common
hyperexponential distribution with rates r(1) and r(2).  Then
lambda(i,j)= N times 'max'( r(1),r(2)) which is obtained by assuming
that each queue is busy in the fastest phase.  However the transition
rate at time t is given by lambda (i,j,t) = N(1,t) times r(1) +
N(2,t) times r(2) where N(1,t) is the number of queues busy at rate
r(1) and N(2,t) is the number of queues busy at rate r(2).  If r(2)
gtgt r(1) but 'E' lbracket N(2,t) rbracket ltlt N, then, with high
probability, lambda(i,j,t) / lambda (i,j) ltlt 1.

      In this note, it is shown ho...