Folding of the plane and the design of systolic arrays (Q788490)

Systolic arrays as defined by \textit{H. T. Kung} [Comput. Mag. 15, No.1, 37-46 (1982)] are devices composed of processors of a few different types, which are regularly and locally connected. These processors are activated in a synchronous way by a unique clock which is the only global communication between them. The paper is motivated by the following observation. Assume we are given an iterative procedure and that the input processors need to be repetitively fed with the new outputs. This can be achieved by connecting directly the input with the output processors, thus ruining the regularity of the layout. We are concerned by stating conditions under which the plane can be ''folded'' in such a way that input and output processors are physically identified while still preserving the main features of systolic arrays. The price to pay for that is defining more complex processors, but the increase in complexity for a given problem is independent of the size of the actual layout. As far as practical implementations are concerned, a few solutions for folding can be imagined: implementation in two layers, multiplexing in time, etc. We first study the power of folding as a geometric transformation. Then as an application we show that two ''congruent'' sequences on a ''regular'' grid (such as hexagonal or square) can be identified by a limited number of foldings.