Folding and double mapping of the matrix multiplication algorithm

Abstract

The data dependence method for algorithm implementation on processor arrays is based on linear transformations of the data dependencies and the index set of the algorithm and results in a regular data flow, but the method is still unable to optimize the array size or the implementation. The presented implementations are developed using properties of some special linear transformations, i.e., symmetry interlocking translation and processors working in swapped active and inactive time moments. The 2D hex matrix multiplication systolic algorithm has all these properties. The array implementation from this example is folded and a triangular solution is obtained using a regular translated folding transformation and double mapping technique. A valid folding transformation is chosen to obtain no increase either in the data communication links or in processor operation.

Keywords:

• Folding transformation
• interlocking translation
• symmetric mapping
• systolic arrary
• algorithm transformation
• data dependence

^∗University “Kiril i Metodij” of Skopje, PMF Institut za Informatika, Arhimedova 5, p.f. 162, Yu-91000 Skopje, Yugoslavia, [email protected].

^∗University “Kiril i Metodij” of Skopje, PMF Institut za Informatika, Arhimedova 5, p.f. 162, Yu-91000 Skopje, Yugoslavia, [email protected].

Notes

^∗University “Kiril i Metodij” of Skopje, PMF Institut za Informatika, Arhimedova 5, p.f. 162, Yu-91000 Skopje, Yugoslavia, [email protected].