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 deri- vation 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 n~2/3 + Θ(n) ele- mentary 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.