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 + T heta(1) steps, where n is the size of the problem. The derivation of a loca lly connected space-time minimal solution with respect to the new schedulin g constitutes the second contribution of the payer. This new design require s n(2)/3 + Theta(n) elementary processors and solves the problem in 4n + Th eta(1) steps, and this includes loading and unloading time. This is an impr ovement over the best previously known bounds. 0 2000 Elsevier Science B.V. All rights reserved.