Parallel simulation of Markovian queueing networks using adaptive uniformization

David M. Nicol, Philip Heidelberger

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper describes a method for simulating a large class of queueing network models with Markovian phase-type distributions on parallel architectures. The method, which is based on uniformization, exploits Markovian properties that permit one to first build schedules of simulation times at which processors ought to synchronize, and then simulate a mathematically correct sample path through the pre-chosen schedule. While the technique eliminates many of the overheads incurred by other synchronization methods, it may suffer when the maximum rate (in simulation time) at which one processor might possibly ever send jobs to another is much larger than the average rate at which it actually does. We show how to reduce these overheads, sometimes doubling the execution rate as a result. We discuss experiments performed on the Intel iPSC/2 and Touchstone Delta architectures, where speedups in excess of 155 are observed on 256 processors.

Original languageEnglish (US)
Title of host publicationProceedings of the 1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1993
PublisherAssociation for Computing Machinery, Inc
Pages135-145
Number of pages11
ISBN (Electronic)0897915801, 9780897915809
DOIs
StatePublished - Jun 1 1993
Externally publishedYes
Event1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1993 - Santa Clara, United States
Duration: May 10 1993May 14 1993

Publication series

NameProceedings of the 1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1993

Other

Other1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1993
CountryUnited States
CitySanta Clara
Period5/10/935/14/93

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Parallel simulation of Markovian queueing networks using adaptive uniformization'. Together they form a unique fingerprint.

Cite this