Some Characteristics of Systolic Arrays

Authors: Halil Snopce, Ilir Spahiu

Abstract:

In this paper is investigated a possible optimization of some linear algebra problems which can be solved by parallel processing using the special arrays called systolic arrays. In this paper are used some special types of transformations for the designing of these arrays. We show the characteristics of these arrays. The main focus is on discussing the advantages of these arrays in parallel computation of matrix product, with special approach to the designing of systolic array for matrix multiplication. Multiplication of large matrices requires a lot of computational time and its complexity is O(n3 ). There are developed many algorithms (both sequential and parallel) with the purpose of minimizing the time of calculations. Systolic arrays are good suited for this purpose. In this paper we show that using an appropriate transformation implicates in finding more optimal arrays for doing the calculations of this type.

Keywords: Data dependences, matrix multiplication, systolicarray, transformation matrix.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330621

References:

[1] M.P. Bekakos, Highly Parallel Computations-Algorithms and Applications, Democritus University of Thrace, Greece, 2001.
[2] Efremides, O.B., and Bekakos, M.P., A nonlinear Approach to Design Processor Time Optimal Systolic Arrays for matrix-vector multiplication, HERCMA -98, athenc, Greece, pp. 327-336, 1998
[3] Esonu, M.O., Al-Khalili, A.J., Hariri, S. and Al-Khalili, D., Systolic Arrays: How to choose them, pp. 179-188, 1992
[4] Milentijevic, I.Z., Milovanovic, I.Z., E.I. and Stojcev, M.K., The Design of Optimal Planar Systolic Arrays for Matrix Multiplication, Comput. Math. Appl., pp. 17-35, 1997
[5] Bekakos, M.P., Milovanovic, E.I., Milovanovic, I.Z. and Milentijevic, I.Z., An Efficient Systolic Array for Matrix Multiplication, Proc. of the Fourth Hellenic European Conference on Computer Mathematics and its Applications (HERCMA -98), Athens -98, pp. 298-317, 1999
[6] Gusev, M., and Evans, D.J., A new matrix vector Product Systolic Array, Parallel Algorithms and Aplications, 22, 346-349, 1994
[7] C.N. Zhang, J.H. Weston, Y. F. Yan: Determining object functions in systolic array designs. IEEE Trans. VLSI Systems 2, No. 3 (1994), 357- 360
[8] Jagadish, H. V., and Kailath, T., A family of new efficient arrays for matrix multiplication. IEEE Trans. On Computers, 38(1), pp. 149-155, 1989
[9] Snopce, H., Elmazi, L., Reducing the number of processors elements in systolic arrays for matrix multiplication using linear transformation matrix, Int. J. of Computers, Communications and Control, Vol. III (2008), Suppl. issue: Proceedings of ICCCC 2008, pp. 486-490
[10] Kung, H.T. and Leiserson, C.E., Systolic arrays for (VLSI), Introduction to VLSI Systems, Addison-Wesley Ltd., Reading, MA, 1980.
[11] Yun YANG, Shinji KIMURA, The optimal architecture design of twodimension matrix multiplication jumping systolic array, IEICE Transactions on Fundamentals of Electronics, Communications and computer sciences, Volume E91-A, pp. 1101-1111, 2008
[12] A.K., Oudjida, S. Titri, M. Hamarlain, Latency 2I/O-Bandwidth 2Darray matrix multiplication algorithm, The int. Journal for computation and mathematics in electrical engineering, volume 21, pp. 377-392, 2002.