The Flow Graph Schemata Model of Parallel Computation

摘要

Flow Graph Schemata are introduced as uninterpreted models of parallel algorithms, operating asynchronously and reflecting physical properties inherent to any implementation. Three main topics are investigated: (1) determinacy, (2) equivalence, and (3) equivalence-preserving transformations on the control structure of a Flow Graph Schemata. A model is determinate if the results of a computation depend only on the initial values and not on any timing constraints within the model. Equivalence is undecidable in general, but for a large class of determinate Flow Graph Schemata which are in a maximum parallel form, equivalence is shown decidable. In equivalence-preserving transformations, sufficient tested conditions for equivalence are formulated that depend only on the portion of the structure to be transformed. Current and future computational systems are evaluated in terms of results obtained for Flow Graph Schemata. A number of interesting extensions of the work are suggested.