Recursive folding for efficiency improvement of systolic arrays - part I

Abstract

In this paper, the mathematical theory of Recursive Folding for Processor Arrays is developed. The new theory shows that a ofold increase in efficiency of c-periodic (C=2) systolic arrays, obtained by the data dependence method, is achieved. Using c-times less processors than the original array, the new folded array is totally homogeneous and performs the algorithm in T{ot time steps, 7of < T{ot 7;ot + 2{c — 1), where Ttot is the time complexity of the original array. In the case of linear arrays, a new type of array named Switched Unidirectional Linear Array (SULA) is obtained that saves up to 50% of the communication links of the original Bidirectional Linear Array (BLA) in a special case.

Keywords:

• Processor arrays
• systolic
• folding

C.R. Categories:

• C.1.2
• F.1.1

^* Institue for informatics, Slovk Academy of Science,Bratislava and Nuclear Power Plant Reserch Institute, Trnava, Slovakia

^†Funded by Royal Society Fellowship Scheme

^* Institue for informatics, Slovk Academy of Science,Bratislava and Nuclear Power Plant Reserch Institute, Trnava, Slovakia

^†Funded by Royal Society Fellowship Scheme

Notes

^* Institue for informatics, Slovk Academy of Science,Bratislava and Nuclear Power Plant Reserch Institute, Trnava, Slovakia

^†Funded by Royal Society Fellowship Scheme