Scheduling a system of nonsingular affine recurrence equations onto a processor array

Most work on the problem of scheduling computations onto a systolic array is restricted to systems of uniform recurrence equations. In this paper, this restriction is relaxed to include systems of affine recurrence equations. In this broader class, a sufficient condition is given for the system to be computable. Necessary and sufficient conditions are given for the existence of an affine schedule, along with a procedure that constructs the schedule vector, when one exists. This material is based upon work supported by the Office of Naval Research under contract nos. N00014-84-K-0664 and N00014-85-K-0553.