The authors present a systematic methodology for mapping commonly used digital signal processing algorithms to VLSI array processors, such as the systolic array and the wavefront array. A concise description of the proposed methodology is presented to show the flexibility and usefulness of the method. The advantages of this methodology include: (1) algorithms in different expressions, such as sequential programs, signal flow graphs, or dataflow graphs can be mapped to array processors easily; (2) the mapping procedure is systematic and optimal designs can be efficiently searched; and (3) the methodology can be automated as software tools to assist the array processor designers.>

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.