Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing
Richard M. Karp, Rayamond E. Miller · SIAM Journal on Applied Mathematics · 1966
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.