Optimistic Parallel Simulation of Continuous Time Markov Chains Using Uniformization

David M. Nicol, P. Heidelberger

Research output: Contribution to journalArticlepeer-review

Abstract

In an earlier paper we described how uniformization can be used as the basis of a conservative parallel simulation algorithm for simulating a continuous time Markov chain (CTMC). The fundamental notion is that uniformization permits the calculation (in advance of actually running the simulation) of instants where processors will synchronize, achieving much lower synchronization overhead than is usually attributed to conservative methods. In this paper we extend the idea further, showing how to use uniformization in the context of an optimistic parallel simulation to reduce the frequency of state-saving, schedule intelligently, and eliminate the Global Virtual Time (GVT) calculation. We demonstrate the efficiency of the method by implementation on a 16-processor Intel iPSC/2 and on 256 processors of the Intel Touchstone Delta.

Original languageEnglish (US)
Pages (from-to)395-410
Number of pages16
JournalJournal of Parallel and Distributed Computing
Volume18
Issue number4
DOIs
StatePublished - Aug 1993
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Optimistic Parallel Simulation of Continuous Time Markov Chains Using Uniformization'. Together they form a unique fingerprint.

Cite this