Optimal Systolic Design for the Transitive Closure and the Shortest Path Problems
- 1 May 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-36 (5) , 603-614
- https://doi.org/10.1109/tc.1987.1676945
Abstract
Due to VLSI technological progress, algorithm- oriented array architectures, such as systolic arrays, appear to be very effective, feasible, and economic. This paper discusses how to design systolic arrays for the transitive closure and the shortest path problems. We shall focus on the Warshall algorithm for the transitive closure problem and the Floyd algorithm for the shortest path problem. These two algorithms share exactly the same structural formulation; therefore, they lead to the same systolic array design. In this paper, we first present a general method for mapping algorithms to systolic arrays. Using this methodology, two new systolic designs for the Warshall-Floyd algorithm will be derived. The first one is a spiral array, which is easy to derive and can be further simplified to a hexagonal array. The other is an orthogonal systolic array which is optimal in terms of pipelining rate, block pipelining rate, and the number of input/output connections.Keywords
This publication has 17 references indexed in Scilit:
- Systematic approaches to the design of algorithmically specified systolic arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- An orthogonal systolic array for the algebraic path problemComputing, 1987
- Optimal Systolic Design for the Transitive Closure and the Shortest Path ProblemsIEEE Transactions on Computers, 1987
- A systolic array algorithm for the algebraic path problem (shortest paths; Matrix inversion)Computing, 1985
- VLSI Array processorsIEEE ASSP Magazine, 1985
- On supercomputing with systolic/wavefront array processorsProceedings of the IEEE, 1984
- Automatic synthesis of systolic arrays from uniform recurrent equationsACM SIGARCH Computer Architecture News, 1984
- Algebraic structures for transitive closureTheoretical Computer Science, 1977
- Algorithm 97: Shortest pathCommunications of the ACM, 1962
- A Theorem on Boolean MatricesJournal of the ACM, 1962