A Method for Deriving Systolic Algorithms
Alexander Wagner, D M Landis · 1992
We can solve several problems, in particular the recognition of strings in context free grammars in Chomsky Normal Form, using dynamic programming methods in ${\rm O(n^3)}$ sequential time. Partial methods exist for mapping these algorithms onto systolic arrays that run in ${\rm O(2n)}$ time, similar to Kosaraju''s implementation of CNF recognition. These methods only accomplish a portion of the mapping; they involve pipelining steps that can require considerable insight and have a critical effect on the speed and complexity of the resulting algorithm. We present an alternative method for the derivation of a systolic implementation of these problems. We represent the algorithms as directed acyclic graphs (DAGs), where nodes represent specific computations and arcs indicate dependencies between these computations. The original DAG for an algorithm may have nodes of unlimited in-degree and out-degree, and thus captures all inherent parallelism in the algorithm. Then, we schedule the DAG by imposing two constraints: the maximum number of copies of any one operand that can exist at one time and the maximum number of operands that any one computation can accept in one timestep. By varying these constraints, we can derive a family of schedules of the computation. We then map these schedules into recurrence equations which represent systolic implementations that run at various speeds on different architectures. We derive a CNF-recognition implementation that runs in $n$ communication steps, roughly twice as fast as Kosaraju''s implementation $(2n -2)$.