An improved systolic algorithm for the algebraic path problem
Sanjay V. Rajopadhye · 1992
Abstract We systematically derive a systolic algorithm for the algebraic path problem (APP). We start with an algorithm with (parallel) running time 3 n , but whose data dependencies are not local. The first step in obtaining a systolic algorithm is to localize these dependencies. The standard localization (used by all authors till nor), forces slowdown the algorithm to the point that it takes 5 n −4 time steps. We show that much of this can be avoided, and give a new localization scheme which reduces the time to 4 n −2 (or 4 n −3 if n is odd). We also introduce a new approach to the problem of scheduling such parallel algorithms: we treat the equations defining the algorithm as an executable specification, but execute it on a non standard value domain. Such an abstract interpretation of the program then computes the optimal schedule of the original algorithm. A closed form can be inferred by observing a trace of this execution. We use this approach to obtain optimal schedules for all the algorithms in the paper—local as well as non-local.