The DOI matches its Crossref record.
Analytic Queueing Network Models for Parallel Processing of Task Systems
Abstract
This paper is concerned with the performance evaluation of a realistic model of parallel computations. We present an efficient algorithm to determine the mean completion time and related performance measures for a task system: a set of tasks with precedence relationships in their execution sequence, such that the resulting graph is acyclic. A queueing network (QN) is used to model tasks executing on a single or multicomputer system. In the case of multicomputer systems, we take into account the delay due to interprocess communication. A straight- forward application of a QN solver to the problem is not possible due to variations in the state of the system (composition of tasks in execution). An accurate algorithm based on hierarchical decomposition is presented for solving task systems. At the higher level, the system behavior is specified by a Markov chain whose states correspond to the combination of tasks in execution. The state transition rate matrix for the Markov chain is triangular (since the task system graph was assumed to be acyclic), therefore it can be solved efficiently to compute the state probabilities and the task initiation/completion times. At the lower level, the transition rates among the states of the Markov chain are computed using a QN solver, which determines the throughput of the computer system for each system state. The model and the solution method can be used in performance evaluation of applications exhibiting concurrency in centralized/distributed systems where there are conflicting goals of load balancing and minimizing interprocess communication overhead.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Stochastic analytical models and statistical performance models can predict program performance on multiprocessors accurately.
“Stochastic analytical models [14][28] and statistical performance models [7][27] can predict program performance on multiprocessors accurately.”
From Roofline: an insightful visual performance model for multicore architectures (2009) · cites this paper as [28]
Citations
Cites
No references could be resolved yet.
Research works printed but not linked: 27
- courtois, 1977, Decomposability Queueing and Computer System Applications
- 10.1145/356876.356883 · DOI
- 10.1109/TC.1983.1676120 · DOI
- 10.1109/TC.1982.1675926 · DOI
- 10.1109/TC.1983.1676125 · DOI
- 1983, Computer Performance Modeling Handbook
- lazowska, 1984, Quantitative System Performance Computer System Analysis Using Queueing Network Models
- 10.1109/TC.1982.1675884 · DOI
- 10.1145/320434.320449 · DOI
- 10.1109/TC.1982.1676110 · DOI
- trivedi, 1982, Probability and Statistics with Reliability Queueing and Computer Science Applications
- bay, 1984, Queueing network models of distributed systems
- 10.1145/359619.359622 · DOI
- 10.1145/356612.356615 · DOI
- 10.1109/TC.1973.5009151 · DOI
- 10.1145/356842.356846 · DOI
- 10.1109/MC.1980.1653419 · DOI
- 10.1145/800189.805490 · DOI
- 10.1145/190.191 · DOI
- 1976, Computer and Job-Shop Scheduling Theory
- 10.1145/800215.806572 · DOI
- peterson, 1983, Petri Net Theory and the Modeling of Systems
- thomasian, 1981, computational algorithms for queueing network models of multiprogrammed computers using generating functions, Comput Perform, 2, 100
- 10.1145/359046.359053 · DOI
- 10.1145/800040.801397 · DOI
- thomasian, 1983, performance characteristics of batch workloads executing on multiprogrammed computer systems, Proc The Comput Meas Group Confer XIV, 135
- thomasian, 1983, Performance '83, 61
Cited by
Sorted by citations
Williams, S., Waterman, A., & Patterson, D. A. (2009) · Communications of the ACM · doi:10.1145/1498765.1498785 · Cited by 2,798
Williams, S., Waterman, A., & Patterson, D. (2009) · doi:10.2172/1407078 · Cited by 110
Metadata
- Authors
- Thomasian, & Bay
- Affiliations
- IBM Research - Thomas J. Watson Research Center (US)
- Venue
- IEEE Transactions on Computers
- Published
- 1986-12
- Volume
- C-35
- Issue
- 12
- Pages
- 1045-1054
- ISSN
- 0018-9340 (ISSN-L)
- 1557-9956
- 2326-3814
- OpenAlex
- W2005253807
- Cited by
- 104
- References
- 0
- Citations by year
- 2022: 2 · 2020: 2 · 2019: 1 · 2018: 2 · 2017: 1 · 2016: 1 · 2014: 2 · 2012: 3
- FWCI
- 6.80
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- Locations
- IEEE Transactions on Computers (publishedVersion)
- Topics
- Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Queuing Theory Analysis
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed and Parallel Computing Systems
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Keywords
- queueing network model, task system, parallel computing, mean completion time, hierarchical decomposition, Markov chains, multicomputers, throughput, load balancing, performance evaluation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
