Bounds for Maxium Parallelism in a Bilogic Graph Model of Computations

Abstract

Given an acyclic directed graph where vertices represent computational tasks, arcs represent transfer of control, and two labels—called input and output logics—associated with each vertex show either the concurrency or the mutual exclusiveness of tasks, procedures are given to determine a lower and an upper bound on the number of processors required for maximum parallelism. The lower bound is obtained via a mean path length approach, while the upper bound is based on the structure of the graph. A detailed algorithm is given for the latter. First, some reduction rules are applied yielding a subset of the vertices which can be performed in parallel. Then the maximum cut in the graph is determined taking into account mutually exclusive vertices. Results are given for example graphs.