Matrix Multiplication on Linear Bidirectional Systolic Arrays

Authors: E. I. Milovanović, B. M. Randjelović, I. Ž. Milovanović, M. K. Stojčev

Keywords: matrix multiplication, linear systolic arrays, efficiency

Abstract:

This paper addresses the problem of rectangular matrix multiplication on bidirectional linear systolic arrays (SAs). We analyze all bidirectional linear SAs in term of number of processing elements, execution time and efficiency. We conclude that the efficiency depends on the relation between loop boundaries in systolic algorithm (i.e. matrix dimensions). We point out which SA is the best choice depending on the relation between matrix dimensions.

References:

[1] M. BEKAKOS, E. MILOVANOVIĆ, N. STOJANOVIĆ, T. TOKIĆ, I. MILOVANOVIĆ, I. MILENTIJEVIĆ, Transformation matrices for systolic array synthesis, J. Electrotech. Math., Vol. 1, (2002), 9-15. [2] M. P. BEKAKOS, I. Ž. MILOVANOVIĆ, E. I. MILOVANOVIĆ, T. I. TOKIĆ, M. K. STOJČEV, Hexagonal systolic arrays for matrix multiplication, In: Highly Parallel Computations: Algorithms and Applications (M. P. Bekakos, ed.), WITpress, Southampton, Boston, 2001, 175- 209. [3] D. J. EVANS, M. GUŠEV, The magic of interlocking property: Fast systolic design, Par. Algor. Appl., No 10, (1997), 195-209 [4] D. J. EVANS, C. R. WAN, Massive parallel processing for matrix multiplications: a systolic approach, In: Highly Parallel Computations: Algorithms and Applications (M. P. Bekakos, ed.), WITpress, Southampton, Boston, 2001, 139-173 [5] M. GUŠEV, D. J. EVANS, Non-linear transformations of the matrix multiplication algorithm, Inter. J. Comp. Math., No 45, 1992, 1-21 [6] M. GUŠEV, D. J. Evans, Procedures for folding transformations, Inter. J. Comp. Math., No 56, (1995), 19-22 [7] H. V. JAGADISH, T. KAILATH, A family of new efficient arrays for matrix multiplication, IEEE Trans. Comput., Vol 38, 1, (1989), 149-155. [8] H. T. KUNG, Why systolic architectures?, Computer, No 15, (1982), 37-46. [9] H. T. KUNG, C. E. LEISERSON, Systolic arrays for (VLSI), Introduction to VLSI Systems, (C. Meed, L. Conway, eds.), Addison-Wesley Ltd., Reading, MA, 1980. [10] S. Y. KUNG, VLSI array processors, Prentice Hall, New Jersey, 1988. [11] P. LEE, Z. M. KEDEM, Synthesizing linear array algorithms from nested loop algorithms, IEEE Trans. Comput., Vol 37, 12, (1988), 1578-1598. [12] L. MELKEMI, M. TCHUENTE, Complexity of matrix product on a class of orthogonally connected systolic arrays, IEEE Trans. Comput., Vol 36, 5, (1987), 615-619. [13] I. Z. MILENTIJEVIĆ, I. Ž. MILOVANOVIĆ, E. I. MILOVANOVIĆ, M. K. STOJČEV, The design of optimal planar systolic arrays for matrix multiplication, Comput. Math. Appl., Vol 33, 6, (1997), 17-35. [14] E. I. MILOVANOVIĆ, M. B. TOŠIĆ, I. Ž. MILOVANOVIĆ, I. Z. MILENTIJEVIĆ, Designing processor-time optimal systolic arrays for matrix-vector multiplication, J. Electrotechn. Math., No 1, (1998), 7-19. [15] I. Ž. MILOVANOVIĆ, E. I. MILOVANOVIĆ, I. Z. MILENTIJEVIĆ, M. K. STOJČEV, Designing of processor time-optimal systolic arrays for band matrix-vector multiplication, Comput. Math. Appl., Vol 32, 2, (1996), 21-31. [16] I. Ž. MILOVANOVIĆ, E. I. MILOVANOVIĆ, T. I. TOKIĆ, I. Z. MILENTIJEVIĆ, N. M. STOJANOVIĆ, A problem of optimizing space parameters in systolic array deigns, Proc: Second Conference of Informatics and Information Technology, CiiT’01, (M. Gušev, S. Markowski, eds.), Univ. ”ST. Cyril and Methodius”, Skopje, 2002, 273-281. [17] N. M. NOVAKOVIĆ, E. I. MILOVANOVIĆ, M. K. STOJČEV, T. I. TOKIĆ, I. Ž. MILOVANOVIĆ, Optimization of bidirectional systolic arrays for matrix-vector multiplication, J. Electrotechn. Math., No 4, (1999), 35-40. [18] I. V. RAMANKRISHNAN, D. S. FUSSELL, A. SILBERSCHATZ, Mapping homogenous graphs on linear arrays, IEEE Trans. Comput., Vol. 35, 3, (1986), 189-209. [19] S. G. SEDUKHIN, G. Z. KARAPETIAN, Design of optimal systolic systems for matrix multiplication of different structures, Report 85, Comput. Center Siberian Division of USSR Academy of Science, Novosibirsk, 1990. (In Russian) [20] T. I. TOKIĆ, I. Ž. MILOVANOVIĆ, D. M. RANDJELOVIĆ, E. I. MILOVANOVIĆ, Determining VLSI array size for one class of nested loop algorithms, In: Advances in Computer and Information Sciences, (U. Güdükbay, T. Dagor, A. Gürsay, E. Gelembe, eds.), IDS Press, 1998, 389-396. [21] C. R. WAN, D. J. EVANS, Nineteen ways of systolic matrix multiplication, Inter. J. Comput. Math., 68, (1998), 39-69. [22] J. XUE, Clossed-form mapping conditions for the synthesis of linear processor arrays, J. VLSI Signal Processing, Vol. 10, 2, (1995), 181-189. [23] J. XUE, C. LENGAUER, The synthesis of control signals for one-dimensional systolic arrays, Integration – The VLSI Journal, Vol 14, 1, (1992), 1-32.