Parallel Program Schemata and Maximal Parallelism II: Construction of Closures

Abstract

The phenomenon of maximal parallelism is investigated in the framework of a class of parallel program schemata. Part II is concerned with the actual realization of closures of schemata represented as "flowcharts." In the case that the flowchart is acyclic there is always a closure which is finite-state realizable. However in the case of cyclic flowcharts this is not generally true. Then realizations which are not finite-state are investigated. Of special concern is the class of counter realizations and the class of queue realizations, both a type of "real-time" automaton. It is shown that these form a proper hierarchy in the set of realizations for closures of flowcharts. A class of flowcharts is then presented all of which have queue realizations of their closure. It is shown that for this class, the existence of a finite-state realization for the closure is decidable.