PRODUCTIVITY IN PARALLEL COMPUTATION SCHEMATA
John P. Linderman · 1973
A general model for parallel computation is developed in three parts. One part, the data flow graph, describes how actors which transform and test values are connected to the locations in a finite memory. Another part, an interpretation, supplies information about the contents of memory and the detailed nature of the transformations and tests. The third part specifies how initiations and terminations of the actors are allowed to occur. We define this in a general way, using a set of sequences of initiation and termination events to model control. This allows us to prove results which apply to a broad class of control mechanisms. Our major results are analogous to a theorem of Karp and Miller. Their theorem defines a class of schemata for which conflict-freeness is necessary and sufficient for determinacy. We use a weaker notion of determinacy which depends only upon the final contents of a subset of the memory locations. To establish necessity, we introduce the property of productivity which expresses whether individual transformations and tests contribute to the final results of a computation.