Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing

Richard M. Karp, Rayamond E. Miller

SIAM Journal on Applied Mathematics · 1966 · 420 citations · 3 references

Concepts

TL;DR

The analysis of parallel computations relies on the structure of maximal strongly connected subgraphs and loops within the computation graph. This work introduces a graph‑theoretic model for parallel computations and develops methods to determine termination, count step performances, and establish conditions for bounded queue lengths. In the model, computation steps are graph nodes, dependencies are branches carrying data queues, and the authors devise algorithms to assess termination and step counts. The authors prove that each computation graph uniquely defines a computation independent of operation times, that steps in a strongly connected subgraph are either all performed infinitely or none, and they derive necessary and sufficient conditions for queue lengths to stay bounded.

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.

References

3