SYSTOLIC ALGORITHMS FOR MATRIX MULTIPLICATION ON SPACE OPTIMAL ONE-DIMENSIONAL SYSTOLIC ARRAYS

Branislav M Randjelovic, Emina I Milovanovic, Igor Z Milovanovic

DOI Number
-
First page
243
Last page
259

Abstract


In this paper we define and discuss various systolic algorithms for synthesis of one-dimensional systolic arrays (1DSA) with two-dimensional links, suitable for implementation of product of rectangular matrices. It is shown that using those algorithms, we can obtain space optimal systolic arrays, for any relation between dimensions of matrices.

Keywords


Systolic arrays, Parallel algorithms, Matrix multiplication

Full Text:

PDF

References


M. P. Bekakos, E. I. Milovanovic, N. M. Stojanovic, T. I. Tokic and I.Z. Milovanovic: Transformation matrices for systolic array synthesis. Journal of Elecrotechnics and Mathematics 7(1) (2003), 9–15.

H.T. Kung: Why systolic architecture?. Computer 15(1) (1982), 37–46.

I.Z. Milovanovic, T. I. Tokic, E. I. Milovanovic and M. K. Stojcev:

Determining the Number of Processing Elements in Systolic Array Facta Universitatis, Series Mathematics and Inormatics. 15(1) (2000), 123–132.

I. Z. Milovanovic, E. I. Milovanovic, B. M. Randjelovic and I. C. Jovanovic: Matrix multi-plication on bidirectional linear systolic arrays. FILOMAT 17(1) (2003), 135–141.

I. Z. Milovanovic, M. P. Bekakos, I. N. Tselepis, and E. I. Milovanovic: Forty-three ways of systolic matrix multiplication. International Journal of Computer Mathematics 87(6) (2007), 164–176.

I. Z. Milovanovic, E. I. Milovanovic and M. P. Bekakos: Synthesis of a unidirectional systolic array for matrix-vector multiplication. Mathematical and Computer Modeling 13(5-6) (2006), 612–619.

E. I. Milovanovic, M. P. Bekakos and I. Z. Milovanovic: Synthesis of space optimal systolic arrays for band matrix-vector multiplication. The Journal of Supercomputing 49(3) (2009), 269–290.

E. I. Milovanovic, M. B. Tosic, I. Z. Milovanovic and I. Z. Milentijevic: Designing processor-time optimal linear systolic arrays for matrix-vector multiplication. Journal of Elecrotechnics and Mathematics 3(1) (1999), 7–19.

I. Z. Milovanovic, E. I. Milovanovic, I. Z. Milentijevic and M. K.

Stojcev: Designing of processor time-optimal systolic arrays for band matrixvector multiplication. Computers and Mathematics with Applications 32(2) (1996), 1–11.

D. I. Moldovan: On the design of algorithms for VLSI systolic arrays. Proceedings of the IEEE 71(1) (1983), 113–120.

N. M. Novakovic, E. I. Milovanovic, M. K. Stojcev, T. I. Tokic and I. Z. Milovanovic: Optimization of bidirectional systolic arrays for matrix-vector multiplication. Journal of Elecrotechnics and Mathematics 4(1) (2000), 35–40.

B. M. Randjelovic, E. I. Milovanovic, I. Z. Milovanovic and M. P.

Bekakos: Synthesis of regular bidirectional linear systolic arrays for matrix multiplication. Journal of Technical University of Gabrovo 11(1) (2005), 98–102.

J. M. Ortega: Introduction to parallel and vector solution of linear systems. Plenum Press, New York and London, 1988.

S. G. Sedukhin: The designing and analysis of systolic algorithms and structures. Programming 2 (1991), 20-40.


Refbacks

  • There are currently no refbacks.




© University of Niš | Created on November, 2013
ISSN 0352-9665 (Print)
ISSN 2406-047X (Online)