Parallel simulation of Markovian queueing networks

Philip Heidelberger, David M. Nicol

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

Abstract

Consider simulating a large queueing network, i.e., one with many queues and jobs, on a parallel computer. Suppose the network is partitioned so that each processor is assigned a set of queues to simulate. The basic difficulty in parallel simulation is synchronizing the simulation clocks on each of the processors so that events appear to get executed in the proper order. If the network possesses a Markovian structure, there are algorithms that can be used to simplify the clock synchronization problem. For appropriately structured queueing networks, these algorithms are quite efficient and large speedups have been obtained; in one example a speedup of 220 was measured on 256 processors of the Intel Touchstone Delta computer. The synchronization algorithms are based on uniformization. Specifically, a Poisson process with rate λij is generated. For the purpose of parallel simulation, the times of the uniformizing Poisson processes can be sampled in advance of actually running the simulation. By doing so, each processor can become aware of a superset of instances in time at which it (i) may receive jobs from another processor, and (ii) may be required to send jobs to another processor. Thus, the times of these Poisson processes become interprocessor synchronization times. Because these times are pre-sampled, all synchronization times are known in advance of actually running the simulation. A variety of parallel simulation algorithms can be devised that take advantage of these known synchronization times in somewhat different fashions.

Original languageEnglish (US)
Title of host publicationProceedings of the IEEE International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems
EditorsVijay Madisetti, Erol Gelenbe, Jean Walrand
PublisherPubl by IEEE
Pages35-36
Number of pages2
ISBN (Print)0818652926
StatePublished - Jan 1 1994
Externally publishedYes
EventProceedings of the 2nd International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems - Durham, NC, USA
Duration: Jan 31 1994Feb 2 1994

Publication series

NameProceedings of the IEEE International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems

Other

OtherProceedings of the 2nd International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems
CityDurham, NC, USA
Period1/31/942/2/94

ASJC Scopus subject areas

  • Engineering(all)

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

  • Cite this

    Heidelberger, P., & Nicol, D. M. (1994). Parallel simulation of Markovian queueing networks. In V. Madisetti, E. Gelenbe, & J. Walrand (Eds.), Proceedings of the IEEE International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (pp. 35-36). (Proceedings of the IEEE International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems). Publ by IEEE.