Folding of the plane and the design of systolic arrays. (English) Zbl 0531.68009

Systolic arrays as defined by 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.


68Q80 Cellular automata (computational aspects)
51M15 Geometric constructions in real or complex geometry
94C30 Applications of design theory to circuits and networks


[1] Ii, K. Culik; Pachl, J.: Folding and unrolling systolic arrays. ACM SIGACT-SIGOPS symp. On principles of distributed computing (1982)
[2] Kung, H. T.: Why systolic architectures?. Comput. magazine 15, No. 1, 37-46 (1982)
[3] Mead, C.; Conway, L.: Introduction to VLSI systems. (1981)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.