Günter Rote:
On the connection between hexagonal and unidirectional rectangular systolic
arrays
In: "VLSI Algorithms and Architectures - Aegean Workshop on Computing.
Loutraki, Greece, July 1986". Proceedings of AWOC'86. Editors: F. Makedon,
K. Mehlhorn, T. Papatheodorou, P. Spirakis. Lecture Notes in
Computer Science 227, Springer-Verlag, 1986, pp. 70-83.
Abstract
We define a simple transformation between systolic algorithms with hexagonal
and with rectangular processor arrays. Using this transformation we can
establish a direct correspondence between two independently developed systolic
arrays for solving the algebraic
path problem (matrix inversion, shortest paths in a network, transitive
closure of a relation).
The two systolic arrays are a
hexagonal one due to the author
and a rectangular one due to Yves Robert and Denis Trystram,
"An orthogonal systolic array for the algebraic path problem",
Computing 39, 187-199.
Then we derive a new hexagonal array for solving a certain type of dynamic
programming recursion that arises for example in context-free language
recognition, in the construction of optimal binary search trees , or in the
computation of an optimal sequence of multiplication for the evaluation of a
product of matrices.
A rectangular array for this problem is due to L. J. Guibas, H. T. Kung, and
C. D. Thompson, "Direct VLSI implementation of combinatorial algorithms",
Proc. CalTech Conference on VLSI. January 1979, pp.756-763.
In general, the type of transformation used here allows arbitrary systolic
arrays to be transformed into unidirectional ones, which are preferable from
the points of view of fault tolerance, two-level pipelining, and algorithm
partitioning.
Last update: October 26, 2001.