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. doi:10.1007/3-540-16766-8_7 →BibTeX

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

other papers about this subject

Note on priority

The remark on p. 82 (the thirteenth page), that any systolic array can be transformed into a unidirectional one, has been previously stated explicitly in J. A. B. Fortes and C. S. Raghavendra: Gracefully degradable processor arrays. IEEE Trans. Computers C-34 (1985), 1033–1044, doi:10.1109/TC.1985.1676536 (using a different construction).

Last update: September 30, 2025.