THE MAGIC OF INTERLOCKING PROPERTY: FAST SYSTOLIC DESIGN

Abstract

This paper actually shows the magic of applying the interlocking property to 3D algorithms and 2D systolic arrays. The interlocking property along with the determinant presenting the characteristics of the linear transformations are results introduced by the authors in [1,2].

Here the interlocking property is used to implement the fast systolic design [3] to the matrix matrix multiply algorithm. Although the regularity of the derived design is proved, it is also shown how the transformations are done analytically.

The fast systolic design introduced for the matrix matrix multiply is 2,3 times more efficient than the regular H. T. Kung and C. E. Leiserson solution [4] it uses 45% less processors and executes the algorithm in 22% less time. No increased cell or array complexity is introduced.

Keywords:

• algorithm transformation
• Fast systolic design
• interlocking property
• linear transformation
• systolic array