Design Of Optimal Systolic Algorithms For The Transitive Closure Problem
Title - Alternative
IEEE Trans. Comput.
Data Dependency; Linear Arrays; Parallel Algorithms; Parallel Machines; Rct Diagram; Systolic Arrays; Transitive Closure Problem; Vlsi; Wsi; Computer Science, Hardware & Architecture; Engineering, Electrical &; Electronic
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.
Ieee Transactions on Computers
Sarkar, D. and Mukherjee, A., "Design Of Optimal Systolic Algorithms For The Transitive Closure Problem" (1992). Faculty Bibliography. 1556.