Parallel Algorithms for Simulating Continuous Time Markov Chains

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1992
Accession Number
ADA260713

Entities

People

  • David M. Nicol
  • Philip Heidelberger

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computers
  • Computing System Architectures
  • Contracts
  • Engineering
  • Markov Chains
  • Mesh Networks
  • Multiprocessors
  • Operating Systems
  • Probability
  • Random Number Generators
  • Random Variables
  • Scheduling (Production)
  • Simulations
  • Simulators
  • Stochastic Processes

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Parallel and Distributed Computing.
  • Systems Analysis and Design