Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing
The work
| Authors | Richard M. Karp; Rayamond E. Miller |
|---|---|
| Editors | |
| Type | article |
| Year | 1966 |
| Citekey | karp1966properties |
Where it appeared
| Published in | SIAM Journal on Applied Mathematics |
|---|---|
| Publisher | Society for Industrial & Applied Mathematics (SIAM) |
| Volume | 14 |
| Issue | 6 |
| Pages | 1390--1411 |
Identifiers
| DOI | 10.1137/0114108 |
|---|---|
| ISSN | 0036-1399 |
Access
| Landing page | https://doi.org/10.1137/0114108 |
|---|
From crossref.
Abstract
This paper gives a graph-theoretic model for the description and analysis of parallel computations. Within the model, computation steps correspond to nodes of a graph, and dependency between computation steps is represented by branches with which queues of data are associated. First, it is shown that each such computation graphGrepresents a unique computation, determined independently of operation times. Next, methods of determining whether such a computation terminates and of finding the number of performances of each computation step are developed. The maximal strongly connected subgraphs of G and the loops within these subgraphs play aooutnal role in this analysis. For example, use is made of the result that either every computation step within a strongly connected snbgroph of G is performed an infinite number of times, or none is. Finally, necessary and sufficient conditions for the lengths of data queues to remain bounded are derived.
How it got here
| How it got here | agent via crossref |
|---|---|
| Added | 2026-10-25 20:54 UTC |
| Not denied by | a person 2026-10-29 17:12 UTC |
Cite it as
@article{karp1966properties,
title = {Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing},
author = {Richard M. Karp and Rayamond E. Miller},
year = {1966},
journal = {SIAM Journal on Applied Mathematics},
publisher = {Society for Industrial \& Applied Mathematics (SIAM)},
volume = {14},
number = {6},
pages = {1390--1411},
issn = {0036-1399},
doi = {10.1137/0114108},
}
This record lives at https://refs.drheap.org/karp1966properties/ and will keep doing so.