Optimizing Space-Time Parameters of Hexagonal Systolic Arrays
Authors: I. Ž. Milovanović, E. I. Milovanović, T. I. Tokić, M. K. Stojčev, N. M. Stojanović
Keywords: systolic arrays, space-time parameters
Abstract:
In this paper we synthesize a family of hexagonal arrays, SA(r), that implement matrix multiplication. We have observed that the execution time of hexagonal array, that has minimal number of processing elements for a given problem size, can be reduced if the number of PEs is increased. Since the execution time and the number of PEs are two most important performance measures of the systolic array, we take their product AT^2 , AT^2 = Ω_{r}(n)T^2_{exe}, to compare the arrays from this family. With respect to this performance measure the best array is obtained for r = [n/2], where n is a dimension of square matrices while r indicates the extension, in terms of rows, of the array that has minimal number of processing elements for a given problem size.
References:
[1] H. T. KUNG, C. E. LEISERSON, Systolic arrays for VLSI, Introduction to VLSI systems, (C. Mead, L.Conway, eds.), Addison-Wesley Ltd., Reading, MA, 1980.
[2] H. T. KUNG, Why systolic architectures?, Computer, 15 (1982), 37-46.
[3] M. CHEN, A design methodology for synthesizing parallel algorithms and architectures, J. Parallel Distributed Comput., (1986), 461-491.
[4] A. L. DECEGAMA, Parallel processing architectures and VLSI hardware, Prentice Hall, New Jersey, Vol. 1, 1989.
[5] J. A. FORTES, K. S. FU, B. W. WAH, Systematic design approaches for algorithmically specified systolic arrays, (V. Milutinovic, ed.), Computer Architectures, Elsevier Ltd., New York, 1988, 454-494.
[6] H. V. JAGADISH, T. KAILATH, A family of new efficient arrays for matrix multiplication, IEEE Trans. Comput., 38 (1) (1989), 149-155.
[7] C. LANGAUER, A view of systolic design, In: Proc. International Conference Parallel Computing Technologies, (N. N. Mirenkov, ed.), Novosibirsk’91, World Scientific, Singapore, 1991, 32-46.
[8] G. J. LI, B. W. WAH, The design of optimal systolic arrays, IEEE Trans. Comput., 34 (1) (1985), 66-77.
[9] I. Z. MILENTIJEVIĆ, I. Ž. MILOVANOVIĆ, E. I. MILOVANOVIĆ, M. K. STOJČEV, The design of optimal planar systolic arrays for matrix multiplication, Computers Math. Applic. 33, 6 (1997), 17-35.
[10] E. I. MILOVANOVIĆ, I. Z. MILENTIJEVIĆ, I. Ž. MILOVANOVIĆ, Designing of processor–time optimal systolic array for matrix multiplication, Comput. Artificial Intelligence, 16 (1) (1997), 1-11.
[11] M. P. BEKAKOS, E. I. MILOVANOVIĆ, I. Ž. MILOVANOVIĆ, I. Z. MILENTIJEVIĆ, An efficient systolic array for matrix multiplication, Proc. of the Fourth Hellenic European Conference on Computer Mathematics and its Applications (HERCMA’98), Athens’98, (E. A. Lipitakis, ed.), Vol.1 (1999), 298-317.
[12] E. I. MILOVANOVIĆ, G. V. MILOVANOVIĆ, I. Ž. MILOVANOVIĆ, D. MILOSAVLJEVIĆ, Designing hexagonal systolic array by composite mappings, Facta Univ. Ser. Math. Inform., Vol. 1 (1997), 1-11.
[13] D. I. MOLDOVAN, On the design of algorithms for VLSI systolic arrays, IEE Proc., 71 (1983), 113-120.
[14] W. SHANG, J. A. FORTES, On time mapping of uniform dependence algorithms into lower dimensional processor arrays, IEEE Trans. Parallel Distr. Syst., 3 (3) (1992), 350-363.
[15] S. G. SEDUKHIN, The designing and analysing systolic algorithms and structures, Programming, 2(1990), 20-40 (In Russian).
[16] S. G. SEDUKHIN, G. Z. KARAPETIAN, Design of optimal systolic systems for matrix multiplication of different structures, Report 85, Comput. Center Sibirian Division of USSR Academy of Science, Novosibirsk, 1990.
[17] C. R. WAN, D. J. EVANS, Nineteen ways of systolic matrix multiplication, Intern. J. Computer Math., Vol. 98 (1998), 39-69.
[18] M. O. ESONU, A. J. AL-KHALILI, S. HARIRI, D. AL-KHALILI, Fault-tolerant design methodology for systolic array architecture, IEE Proc. Comput. Digit. Tech., Vol. 141 (1) (1994), 17-28.
[19] C. N. ZHANG, T. M. BACHTIAR, W. K. CHOU, Optimal fault-tolerant design approach for VLSI processors, IEE Proc. Comput. Digit. Tech., Vol. 144 (1) (1997), 15-21.
[20] C. N. ZHANG, Systematic design of systolic arrays for computing multiple time instances, Microelectronic Journal, 23 (1992), 543-553.
[21] I. Ž. MILOVANOVIĆ, T. I. TOKIĆ, M. K. STOJČEV, E. I. MILOVANOVIĆ, N. M. NOVAKOVIĆ, Mapping matrix multiplication algorithm onto optimal fault-tolerant systolic array, Proc. 22nd Inter. Conf. Microelectronics (MIEL 2000), Nis’00, 711-714. ˇ
[22] M. GUŠEV, D. J. EVANS, Nonlinear transformations of the matrix multiplication algorithm, Inter. J. Comput. Math., Vol. 45 (1992), 1-21.
[23] D. J. EVANS, M. GUŠEV , The magic of interlocking property: Fast systolic design, Par. Algor. Appl., 10 (1997), 195-209.
[24] T. I. TOKIĆ, E. I. MILOVANOVIĆ, N. M. NOVAKOVIĆ, I. Ž. MILOVANOVIĆ, M. K. STOJČEV, Matrix multiplication on non-planar systolic arrays, Facta Univ. Ser. Electr. Energ., Vol. 13, 2 (2000), 157-165.
[25] O. B. EFREMIDIS, M. P. BEKAKOS, A nonlinear approach to design processor-time optimal systolic arrays for matrix-vector multiplication, Proc. of the Fourth Hellenic European Conference on Computer Mathematics and its Applications (HERCMA’98), Athens’98, (E. A. Lipitakis, ed.), Vol. 1 (1999), 327-345.
[26] N. NOVAKOVIĆ, E. MILOVANOVIĆ, M. STOJČEV, T. TOKIĆ, I. MILOVANOVIĆ, Optimization of bidirectional systolic arrays for matrix-vector multiplication, J. Electrotechn. Math., 4 (1999), 35-40.
[27] I. Ž. MILOVANOVIĆ, E. I. MILOVANOVIĆ, I. Z. MILENTIJEVIĆ, M. K. STOJČEV, Designing of processor-time optimal systolic arrays for band matrix-vector multiplication, Computers Math. Applic., Vol. 32, 2 (1996), 21-31.