A processor-time minimal systolic array for transitive closure

A directed acyclic graph (DAG) model of algorithms is used. For a given DAG the authors focus on processor-time minimal multiprocessor schedules: time minimal multiprocessor schedules that use as few processors as possible. The Kung, Lo and Lewis (KLL) algorithm (S.-Y. Kung et al., 1987) for computing the transitive closure of a relation over a set of n elements requires at least 5n-4 steps. Their systolic array comprises n² processing elements. Here, it first is shown that any multiprocessor that achieves this 5n-4 time bound needs at least [n²/3] processing elements. Then, a processor-time minimal systolic array realizing the KLL algorithm´s DAG is constructed. Its [n² /3] processing elements are organized as a cylindrically connected 2-D mesh, when n≡0 mod 3. When n is not identical to 0 mod 3, the 2-D mesh is connected as a twisted torus