A systolic array design methodology for sequential loop algorithms
Kee-Young Yoo · 1992
This thesis investigates a systematic design methodology for synthesizing a one or two-dimensional systolic array with input scheduling from a sequential loop algorithm of loop depth n. Our method consists of two steps: an algebraic analysis for a given sequential loop algorithm followed by a space-time mapping to a target systolic array. Theoretical foundations and practical procedures based on an algebraic approach to the design problem are presented in this thesis. We begin by investigating algebraic properties of the computation cell set of the sequential loop algorithm, presenting sufficient conditions for uniform pipelinability of array variables. Based on these conditions, we show how to analyze shift-invariant data flow vectors of array variables and the initial positions of the input data. Some array variables may not satisfy the uniform pipelinability condition. In this case, uniformization techniques such as folding, decomposition/renaming and translation, which make these variables uniformily pipelinable, are introduced. This approach does not require the algorithm written in a single assignment code, a condition that was assumed by most techniques in the literature. We continue by presenting the time, space and space-time conditions which are necessary and sufficient for a valid space-time transformation. We generate all geometrically distinct networks based on the space condition imposed by the processor domain and interconnection links. An algorithm for computing a space matrix which maps data flow vectors to a geometrically distinct network is developed. In addition, this thesis presents procedures that given a space matrix, compute a time matrix by using the multiple projection technique and linearize the time matrix to a schedule vector. Finally, we show how to compute an input scheduling function which gives an input layout for correct computations on the derived systolic array.