Mapping Nested Loop Algorithms into Multidimensional Systolic Arrays

This paper is concerned with transforming depth p-nested for loop algorithms into q-dimensional systolic VLSI arrays where [formula omitted]. Previously there existed complete characterizations of correct transformations only for the cases when q = p – 1 or q = 1. We fill in this gap by giving formal necessary and sufficient conditions for correct transformation of a p-nested loop algorithm into a q-dimensional systolic array for any q, [formula omitted]. We also provide practical methods to derive optimal or suboptimal systolic array implementations. We apply the techniques developed by us to the automatic design of special purpose and programmable systolic arrays. Our results also contribute towards automatic compilation onto more general purpose programmable arrays. Synthesis of linear and planar systolic array implementations for a three-dimensional cube-graph algorithm and a reindexed Warshall-Floyd path-finding algorithm is used to illustrate our method.