Folding transformations for processor arrays

Abstract

The nonlinear tranformations in the data dependence method for implementations on processor arrays offer many advantages such as more efficient work for the processing elements, smaller processor arrays, a decrease in I/O time, pipelineable implementations, circular data flow.

In this paper the folding transformation is used to realize these proposed ideas. The symmetric linear transformations are analyzed and certain characteristics are pointed out. Space time graphs are defined as objects where the folding transformation is implemented. It is shown that a direct implementation of a folding transformation according to the line of symmetry does not result in a valid and regular implementation, even if retiming is used.

The solution of this problem is offered for the space time graphs having the interlocking property, or implementations working in swapped active and inactive moments. It is proved that the folding transformation according to a translated line of symmetry offers valid and regular solutions. Some examples are given to demonstrate the idea of folding transformations. The comparison between the regular and the folded implementation shows an improvement of up to 50% of processors, circular data flow and decreased input and output.

Keywords:

• Folding
• nonlinear transformation
• symmetrical mapping
• interlocking translation
• data dependence
• algorithm transformation
• systolic array

C.R. CATEGORIES:

• F.1.1
• F.2.1
• B.7.1