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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:52718", author = "Halil Snopce and Ilir Spahiu", title = "Some Characteristics of Systolic Arrays", 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.", volume = "4", number = "4", pages = "462-6", }