A Comparative Study of Parallel Algorithms for Simulating Continuous Time Markov Chains

David M. Nicol, Philip Heidelberger

Research output: Contribution to journalArticlepeer-review

Abstract

This article describes methods for simulating continuous time Markov chain models, using parallel architectures, The basis of our method is the technique of uniformization; within this framework there are a number of options concerning optimism and aggregation, We describe four different variations, paying particular attention to an adaptive method that optimistically assumes upper bounds on the rate at which one processor affects another in simulation time, and recovers from violations of this assumption using global checkpoints. We descmbe our experiences with these methods on a variety of Intel multiprocessor architectures, including the Touchstone Delta, where excellent speedups of up to 220 using 256 processors are observed.

Original languageEnglish (US)
Pages (from-to)326-354
Number of pages29
JournalACM Transactions on Modeling and Computer Simulation (TOMACS)
Volume5
Issue number4
DOIs
StatePublished - Oct 1 1995
Externally publishedYes

Keywords

  • Markov chains
  • simulation

ASJC Scopus subject areas

  • Modeling and Simulation
  • Computer Science Applications

Fingerprint Dive into the research topics of 'A Comparative Study of Parallel Algorithms for Simulating Continuous Time Markov Chains'. Together they form a unique fingerprint.

Cite this