Synthesizing Linear Array Algorithms from Nested For Loop Algorithms

This paper is concerned with the mapping of algorithms structured as depth p-nested for loops into special purpose systolic VLSI linear arrays. The mappings are done by using linear functions transforming the original sequential algorithms into a form suitable for parallel execution on linear arrays. The derivation of feasible mapping is done by identifying formal criteria to be satisfied by both the original sequential algorithm and the proposed transformation function. Those formal criteria define the universe of feasible solutions we consider and thus enable us to derive large families of transformations; the target transformation can then be chosen using additional criteria. Among such criteria could be minimal execution time, smallest number of processors to be used, or the requirement to use a processor with specific characteristics provided to us. The methodology, which deals with general algorithms, is illustrated by synthesizing algorithms for matrix multiplication and a version of the Warshall-Floyd transitive closure algorithm.