Folding of the plane and the design of systolic arrays
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.
- Topological transformations as a tool in the design of systolic networks
- Decoupling the dimensions of a system of affine recurrence equations
- Implementation of folding transformations on linear VSLI processor arrays
- Optimisation of bidirectional systolic arrays with sparse input by ``folding
- Folding and double mapping of the matrix multiplication algorithm
This page was built for publication: Folding of the plane and the design of systolic arrays
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q788490)
