Parallel Discrete-Event Simulation of FCFS Stochastic Queueing Networks

Research output: Contribution to journalArticle

Abstract

Physical systems are inherently parallel; intuition suggests that simulations of these systems may be amenable to parallel execution. The parallel execution of a discrete-event simulation requires careful synchronization of processes in order to ensure the execution's correctness; this synchronization can degrade performance. Largely negative results were recently reported in a study which used a well-known synchronization method on queueing network simulations. In this paper we discuss a synchronization method, appointments, which has proven itself to be effective on simulations of FCFS queueing networks. The key concept behind appointments is the provision of lookahead. Lookahead is a prediction on a processor's future behavior, based on an analysis of the processor's simulation state. We show how lookahead can be computed for FCFS queueing network simulations, give performance data that demonstrates the method's effectiveness under moderate to heavy loads, and discuss performance trade-offs between the quality of lookahead, and the cost of computing lookahead.

Original languageEnglish (US)
Pages (from-to)124-137
Number of pages14
JournalACM SIGPLAN Notices
Volume23
Issue number9
DOIs
StatePublished - Jan 1 1988

Fingerprint

Queueing networks
Discrete event simulation
Synchronization
Costs

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design

Cite this

Parallel Discrete-Event Simulation of FCFS Stochastic Queueing Networks. / Nicol, David Malcolm.

In: ACM SIGPLAN Notices, Vol. 23, No. 9, 01.01.1988, p. 124-137.

Research output: Contribution to journalArticle

@article{78ddbb3c974645c8a3a6b55a16b2c382,
title = "Parallel Discrete-Event Simulation of FCFS Stochastic Queueing Networks",
abstract = "Physical systems are inherently parallel; intuition suggests that simulations of these systems may be amenable to parallel execution. The parallel execution of a discrete-event simulation requires careful synchronization of processes in order to ensure the execution's correctness; this synchronization can degrade performance. Largely negative results were recently reported in a study which used a well-known synchronization method on queueing network simulations. In this paper we discuss a synchronization method, appointments, which has proven itself to be effective on simulations of FCFS queueing networks. The key concept behind appointments is the provision of lookahead. Lookahead is a prediction on a processor's future behavior, based on an analysis of the processor's simulation state. We show how lookahead can be computed for FCFS queueing network simulations, give performance data that demonstrates the method's effectiveness under moderate to heavy loads, and discuss performance trade-offs between the quality of lookahead, and the cost of computing lookahead.",
author = "Nicol, {David Malcolm}",
year = "1988",
month = "1",
day = "1",
doi = "10.1145/62116.62128",
language = "English (US)",
volume = "23",
pages = "124--137",
journal = "ACM SIGPLAN Notices",
issn = "1523-2867",
publisher = "Association for Computing Machinery (ACM)",
number = "9",

}

TY - JOUR

T1 - Parallel Discrete-Event Simulation of FCFS Stochastic Queueing Networks

AU - Nicol, David Malcolm

PY - 1988/1/1

Y1 - 1988/1/1

N2 - Physical systems are inherently parallel; intuition suggests that simulations of these systems may be amenable to parallel execution. The parallel execution of a discrete-event simulation requires careful synchronization of processes in order to ensure the execution's correctness; this synchronization can degrade performance. Largely negative results were recently reported in a study which used a well-known synchronization method on queueing network simulations. In this paper we discuss a synchronization method, appointments, which has proven itself to be effective on simulations of FCFS queueing networks. The key concept behind appointments is the provision of lookahead. Lookahead is a prediction on a processor's future behavior, based on an analysis of the processor's simulation state. We show how lookahead can be computed for FCFS queueing network simulations, give performance data that demonstrates the method's effectiveness under moderate to heavy loads, and discuss performance trade-offs between the quality of lookahead, and the cost of computing lookahead.

AB - Physical systems are inherently parallel; intuition suggests that simulations of these systems may be amenable to parallel execution. The parallel execution of a discrete-event simulation requires careful synchronization of processes in order to ensure the execution's correctness; this synchronization can degrade performance. Largely negative results were recently reported in a study which used a well-known synchronization method on queueing network simulations. In this paper we discuss a synchronization method, appointments, which has proven itself to be effective on simulations of FCFS queueing networks. The key concept behind appointments is the provision of lookahead. Lookahead is a prediction on a processor's future behavior, based on an analysis of the processor's simulation state. We show how lookahead can be computed for FCFS queueing network simulations, give performance data that demonstrates the method's effectiveness under moderate to heavy loads, and discuss performance trade-offs between the quality of lookahead, and the cost of computing lookahead.

UR - http://www.scopus.com/inward/record.url?scp=84976842855&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84976842855&partnerID=8YFLogxK

U2 - 10.1145/62116.62128

DO - 10.1145/62116.62128

M3 - Article

AN - SCOPUS:84976842855

VL - 23

SP - 124

EP - 137

JO - ACM SIGPLAN Notices

JF - ACM SIGPLAN Notices

SN - 1523-2867

IS - 9

ER -