Design Of Optimal Systolic Algorithms For The Transitive Closure Problem

We present new optimal systolic algorithms for the transitive closure problem on ring and linear array of processors. The data dependency of the Warshal-Floyd algorithm is exploited to obtain highly pipelined parallel algorithms. One of the algorithms is asymptotically seven times cost-effective than the existing algorithms for computing transitive closure problems. We introduce a new expository device, called the RCT diagram, that depicts simultaneous flow of data and computation for parallel algorithms