Decoupling the Dimensions of a System of Affine Recurrence Equations

Most work on the problem of synthesizing a systolic array from a system of recur-rence equations is restricted to systems of uniform recurrence equations. In this paper, this restriction is relaxed to include systems of affine recurrence equations. A system of uniform recurrence equations typically can be embedded in spacetime so that the distance between a variable and a dependent variable does not depend on the prob-lem size. Systems of affine recurrence equations which are not uniform, do not enjoy this property. A method in another paper has been presented for converting a system of affine recurrence equations to an equivalent system of recurrence equations that is uniform, except for points near the boundaries of its index sets