Derivation of systolic algorithms for the algebraic path problem by recurrence transformations
In this paper, we are interested in solving the algebraic path problem (APP) on regular arrays. We first unify previous contributions with recurrence transformations. Then, we propose a new localization technique without long-range communication which leads to a piecewise affine scheduling of 4n+?(1) steps, where n is the size of the problem. The derivation of a locally connected space-time minimal solution with respect to the new scheduling constitutes the second contribution of the paper. This new design requires n2/3+?(n) elementary processors and solves the problem in 4n+?(1) steps, and this includes loading and unloading time. This is an improvement over the best previously known bounds.
algebraic path problem uniform recurrence equations dependence graph systolic architectures