A Regular Folding Procedure

Abstract

Folding transformations on processor arrays result in smaller processor arrays, more efficient work for the processing elements, a decrease in I/O time, pipelineable implementations and circular data flow are presented in [1]. In this paper the folding transformation is defined via symmetric transformations and interlocking translations implemented on the space time graphs. The regular folding transformation according to a translated line of symmetry offers valid and regular solutions. Two generalized procedures for regular folding are given here keep the complexity of the data communications, the processor operations, the regular data flow and avoid data collision. The matrix vector multiplication algorithm is given as an example of the proposed procedures and the best folding transformation is determined.
The efficiency analysis shows that the implementation obtained utilizes the processor array with double efficiency. Moreover, by using the same processor array, problems with double the dimension can be solved. Also, the circular data flow can be used for cascaded algorithms.