A study model for parallel computation

A generalization is given of a model for parallel computation as formulated by Karp and Miller (R. M. Karp and R. E. Miller. Properties of a model for parallel computations: determinacy termination, queueing. IBM Research Paper RC-1285). A parallel computation is viewed as a directed graph in which a node represents a sequence of operations to be performed upon data on the node input branches with the results of an operation being placed upon the output branches. An operation associated with a node n may initiate if and only if, for each input branch d to n, the data queue length on d is greater than, or equal to, some threshold T. It is shown that a unique computation is defined independently of the timing of the node operations. Methods are derived for determining whether a computation terminates and for finding the number of performances of each node computation step involved. In particular, an algorithm is given which yields the number of performances of each node computation step for the set of terminating nodes of a computation graph. Necessary and sufficient conditions for data queue lengths to remain bounded are derived. (Author)