Uniformization of linear recurrence equations: a step toward the automatic synthesis of systolic arrays

Systems of linear recurrences are a very powerful means for specifying algorithms that need to be implemented on a systolic array or, more generally, on a parallel architecture. In particular, the class of linear recurrences called uniform recurrences can be mapped automatically on systolic arrays. However, it is often difficult to express the algorithm directly using strictly uniform recurrences, especially when the algorithm involves recursive computations, as in the transitive closure problem. Novel tools for the uniformization of linear recurrences are provided. Their use is illustrated by solving the so-called routing problem, which is a particular uniformization problem. Two routing strategies are presented, namely, hierarchical routing and split routing.<>