A rationalized structure of processing unit to multiply 3x3 matrices

• Autorzy: Cariow A. , Sysło W. , Cariowa G. , Gliszczyński M.

Warianty tytułu

PL

Zracjonalizowana struktura jednostki procesorowej do mnożenia macierzy trzeciego stopnia

• Języki publikacji: EN

Abstrakty

EN

This paper presents a high-speed parallel 3x3 matrix multiplier structure. To reduce the hardware complexity of the multiplier structure, we propose to modify the Makarov's algorithm for 3?3 by 3?3 matrix multiplication. The process of matrix product calculation is successively decomposed so that a minimal set of multipliers and fewer adders are used to generate partial results which are combined to generate the final results. Thus, our proposed modification reduces the number of adders compared to the direct implementation of the Makarov's algorithm, and takes advantage of parallelism of calculation offered by field-programmable gate arrays (FPGA's).

PL

W pracy została przedstawiona struktura jednostki procesorowej do wyznaczania iloczynu dwóch macierzy trzeciego stopnia. W odróżnieniu od implementacji naiwnego sposobu zrównoleglenia obliczeń wymagającego 27 układów mnożących proponowana równoległa struktura wymaga tylko 22 układa mnożących. A ponieważ układ mnożący pochłania znacznie więcej zasobów sprzętowych platformy implementacyjnej niż sumator, to minimalizacja układów mnożących przy projektowaniu mikroelektronicznych jednostek procesorowych jest sprawą nadrzędną. Zasada budowy proponowanej jednostki oparta jest na realizacji autorskiej modyfikacji metody Makarova, z tym, że implementacja naszej modyfikacji wymaga o 38 sumatorów mniej niż implementacja metody Makarova. Zaproponowana struktura może bycz z powodzeniem zastosowana do akceleracji obliczeń w podsystemach cyfrowego przetwarzania danych zrealizowanych na platformach FPGA oraz zaimplementowana w dowolnym środowisku sprzętowym, na przykład zrealizowana w postaci układu ASIC. W tym ostatnim przypadku niewątpliwym atutem wyróżniającym przedstawione rozwiązanie jest to, że zaprojektowany w ten sposób układ będzie zużywać mniej energii oraz wydzielać mniej ciepła.

Słowa kluczowe

EN

matrix multiplier; hardware complexity reduction; FPGA implementation

PL

układ mnożenia macierzy; redukcja złożoności sprzętowej; implementacja na FPGA

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2012
• Tom: R. 58, nr 7
• Strony: 677--680
• Opis fizyczny: Bibliogr. 10 poz., rys., wzory

Twórcy

autor

Cariow A.

autor

Sysło W.

autor

Cariowa G.

autor

Gliszczyński M.

• West pomeranian University of technology, Szczecin, Żołnierska St. 49, 71-210 Szczecin,

Bibliografia

• [1] Amira Bouridane A. and Milligan P.: Accelerating matrix product on reconfigurable hardware for signal processing, in Proc. 11th Int. Conf. Field-Programmable Logic Appl. (FPL), 2001, pp. 101-111.
• [2] Jang J., Choi S. and Prasanna V. K.: Energy-efficient matrix multiplication on FPGAs, in Proc. Int. Conf. Field Programmable Logic Appl., 2002, pp. 534-544.
• [3] Jang J. W., Choi S. and Prasanna V. K.: Area and time efficient implementations of matrix multiplication on FPGAs, in Proc. IEEE Int.Conf. Field Programmable Technol., 2002, pp. 93-100.
• [4] Ţariov A.: Algorithmic models and structures of high-performance DSP processors, Szczecin, Informa, 2001. (in Russian).
• [5] Charles-Éric Drevet, Md. Nazrul Islam and Éric Schost: Optimization techniques for small matrix multiplication, Theoretical Computer Science, Volume 412, Issue 22, 2011, pp. 2219-2236.
• [6] Makarov M.: An algorithm for multiplying 3 x 3 matrics, Journal, USSR Computational Mathematics and Mathematical Physics archive Volume 26, Issue 1, May 1, 1987 pp. 293-294.
• [7] Johnson R. and McLoughlin A.: Noncommutative bilinear algorithms for 3x3 matrix multiplication. SIAM J. Comput., 15 (2): 595-603, 1986.
• [8] Laderman J. D.: A noncommutative algorithm for multiplying 3 × 3 matrices using 23 multiplications, Bull. Amer. Math. Soc. 82 (1976), no. 1, 126-128.
• [9] Nicolas T. Courtois, Gregory V. Bard and Daniel Hulme: A New General-Purpose Method to Multiply 3x3 Matrices Using Only 23 Multiplications., Miscellaneous papers in Computer and Information Science, Numerische Mathematik, 14 Aug. 20011: http://arxiv.org/abs/ 1108.2830.
• [10] Hopcroft J. E. and Kerr L. R.: On minimizing the number of multiplications necessary for matrix multiplications, SIAM J. Appl. Math., 1971, vol. 20, no. 1, pp. 35-36.