## 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.