The importance of using the linear transformation matrix in determining the number of processing elements in 2-dimensional systolic array for the algorithm of matrix-matrix multiplication
Halil Snopçe, Lavdrim Elmazi · 2008
Matrix multiplication plays very important role in many scientific disciplines because of fact that it is considered as the main tool for many other computations in different areas, like those in seismic analysis, different simulations (like galactic simulations), aerodynamic computations, signal and images processing etc. In this paper is using a special design named systolic arrays which are suitable for matrix multiplication algorithm and offer both pipeline ability and parallelism. On the area of systolic designs there are two main questions: the first one is how to choose the appropriate systolic array for certain application and the second question is how to minimize the number of processors. The main result in this work gives a possible answer for the second question mentioned above. In this work is given the so called transformation matrix, which maps the given index space in another index space. Transformation used in this new index space reduces the number of processing elements in the array. We illustrate all possible instances of transformation matrices and we show the importance of using the transformation matrix by comparing the number of processing elements of the array where we use it with another array where this transformation is not used. For this purpose is given a mathematical explanation using theorems 1 and 2. The comparison is made using the matrices of size N=4.