Computing transitive closure on systolic arrays of fixed size

Summary Forming the transitive closure of a binary relation (or directed graph) is an important part of many algorithms. When the relation is represented by a bit matrix, the transitive closure can be efficiently computed in parallel in a systolic array.Here we propose two novel ways of computing the transitive closure of an arbitrarily big graph on a systolic array of fixed size. The first method is a simple partitioning of a well-known systolic algorithm for computing the transitive closure. The second is a block-structured algorithm. This algorithm is suitable for execution on a systolic array that can multiply fixed size bit matrices and compute transitive closure of graphs with a fixed number of nodes. The algorithm is, however, not limited to systolic array implementations; it works onany parallel architecture that can perform these bit matrix operatons efficiently.The shortest path problem, for directed graphs with weighted edges, can also be solved in the same manner, devised above, as the transitive closure is computed.Björn Lisper was born in 1956 in Solna, Sweden. He received the M. Eng. Physics degree in 1980 and the Ph.D. degree in Computer Science in 1987, both from the Royal Institute of Technology in Stockholm. Currently he shares his time between the Royal Institute of Technology and the Swedish Institute of Computer Science. His research interests are mainly in the area of formal methods for deriving efficient parallel implementations of algorithms, including synthesis of fixed hardware structures for specific algorithms and compilation techniques for tightly coupled parallel systems. Dr. Lisper is a member of the European Association for Theoretical Computer Science.