DATA FLOW REPRESENTATION OF ITERATIVE ALGORITHMS FOR SYSTOLIC ARRAYS

Abstract

An algebraic representation is proposed for regular iterative algorithms that can be described as bundles of data flows with different wavefronts. Modeling data flows with a generating function of power series, this form corresponds to the geometric representation such as a dependence graph. The main attributes of systolic algorithms and arrays are revealed by a unique data flow representation. This provides the ability to pipeline two or more systolic arrays solving different subproblems without intermediate buffering. We use an example to show the case with which our technique can be used.