A hardware-oriented algorithm for complex-valued constant matrix-vector multiplication

• Autorzy: Cariow A. , Cariowa G.

Identyfikatory

DOI

10.15199/48.2017.01.21

Warianty tytułu

PL

Sprzętowo-zorientowany algorytm wyznaczania iloczynu macierzy stałych przez wektor zmiennych dla danych zespolonych

• Języki publikacji: EN

Abstrakty

EN

In this communication we present a hardware-oriented algorithm for constant matrix-vector product calculating, when the all elements of vector and matrix are complex numbers. The main idea behind our algorithm is to combine the advantages of Winograd’s inner product formula with Gauss's trick for complex number multiplication. The proposed algorithm versus the naïve method of analogous calculations drastically reduces the number of multipliers required for FPGA implementation of complex-valued constant matrix-vector multiplication. If the fully parallel hardware implementation of naïve (schoolbook) method for complex-valued matrix-vector multiplication requires 4MN multipliers, 2M N-inputs adders and 2MN two-input adders, the proposed algorithm requires only 3N(M+1)/2 multipliers and [3M(N+2)+1,5N+2] two-input adders and 3(M+1) N/2-input adders.

PL

W komunikacie został zaprezentowany sprzętowo-zorientowany algorytm mnożenia macierzy stałych przez wektor zmiennych w założeniu, gdy zarówno elementy macierzy jak i elementy wektora są liczbami zespolonymi. Główna idea proponowanego algorytmu polega na łącznym zastosowaniu wzoru Winograda do wyznaczania iloczynu skalarnego oraz formuły Gaussa mnożenia liczb zespolonych. W porównaniu z tradycyjnym sposobem realizacji obliczeń proponowany algorytm pozwala zredukować liczbę układów mnożących niezbędnych do całkowicie równoległej realizacji na platformie FPGA układu wyznaczania iloczynu wektorowo-macierzowego. Jeśli całkowicie równoległa implementacja tradycyjnej metody wyznaczania omawianych iloczynów wymaga 4MN bloków mnożących, 2M N-wejściowych sumatorów oraz 2MN sumatorów dwuwejściowych, to proponowany algorytm wymaga tylko 3N(M+1)/2 błoków mnożenia, [3M(N+2)+1,5N+2] sumatorów dwuwejściowych i 3(M+1) sumatorów N/2-wejściowych.

Słowa kluczowe

EN

algorithm design; algorithm analysis; FPGA; VLSI; high performance computing

PL

analiza algorytmów; FPGA; VLSI; wysokowydajne obliczenia

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2017
• Tom: R. 93, nr 1
• Strony: 87--90
• Opis fizyczny: Bibliogr. 17 poz., rys.

Twórcy

autor

Cariow A.

• Department of Computer Architectures and Telecommunications, Faculty of Computer Sciences, West Pomeranian University of Technology, Szczecin, ul. Żołnierska 51, 71-210 Szczecin

autor

Cariowa G.

• Department of Computer Architectures and Telecommunications, Faculty of Computer Sciences, West Pomeranian University of Technology, Szczecin, ul. Żołnierska 51, 71-210 Szczecin

Bibliografia

• [1] Blahut, R.E. Fast algorithms for digital signal processing, Addison-Wesley Publishing company, Inc. 1985
• [2] Pratt, W.K. Digital Image Processing (Second Edition), John Wiley & Sons, New York, 1991.
• [3] Fujimoto, N. Dense matrix-vector multiplication on the CUDA architecture, Parallel Processing Letters, vol. 18, no. 4, 511- 530, 2008.
• [4] Qasim, S.M., Telba, A.A. and Al Mazroo, A. Y. FPGA Design and Implementation of Matrix Multiplier Architectures for Image and Signal Processing, IJCSNS International Journal of Computer Science and Network Security, vol.10, no.2, 168-176, 2010.
• [5] Fam, A.T. Efficient complex matrix multiplication, IEEE Transactions on Computers, vol. 37, no. 7, 877-879, 1988.
• [6] Connolly, F.T. Yagle, A.E. Fast algorithms for complex matrix multiplication using surrogates, IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 37, no. 6, 938 – 939, 1989.
• [7] Ollila , E. Koivunen, V. Poor, H. V. Complex-valued signal processing — essential models, tools and statistics, Information Theory and Applications Workshop, 6-11 Feb. 2011, 1 – 10.
• [8] Guoqiang Li, Liren Liu Complex-valued matrix-vector multiplication using twos complement representation”. Optics Communications, vol. 105, no. 3-4, 161-166.
• [9] Barazesh B., Michalina J. and Picco A. A VLSI signal processor with complex arithmetic capability. IEEE Transactions on Circuits and Systems, 35(5), 495–505, 1988.
• [10] Gustafsson O., Ohlsson H. and Wanhammar L., Lowcomplexity constant coefficient matrix multiplication using a minimum spanning tree approach, Proceedings of the 6th Nordic Signal Processing Symposium (NORSIG 2004), June 9 - 11, Espoo, Finland, 141-144, 2004.
• [11] Boullis N. Tisserand A. Some optimizations of hardware multiplication by constant matrices, IEEE Transactions on Computers, 2005, vol. 54, no 10, 1271 – 1282.
• [12] Kinane A. Muresan V. Towards an optimized VLSI design algorithm for the constant matrix multiplication problem. In: Proc. IEEE International Symposium on Circuits and Systems (ISCAS-2006), 5111 – 5114, 2006.
• [13] Cariow A., Cariowa G., An algorithm for complex-valued vector-matrix multiplication. Electrical Review, R 88, no 10b, 213-216, 2012.
• [14] Cariow A., Cariowa G., A rationalized algorithm for complex-valued inner product calculation, Measurement Automation and Monitoring, no 7, pp. 674-676, 2012.
• [15] Winograd S. A new algorithm for inner Product, IEEE Transactions on Computers, vol. C-17, no 7, 693 – 694, 1968.
• [16] Knuth D. E., The Art Of Computing Programming, vol. 2, Semi-numerical Algorithms, Addison-Wesley, Reading, MA, USA, Second Ed., 1981.
• [17] Regalia P. A. and Mitra K. S., Kronecker Products, Unitary Matrices and Signal Processing Applications, SIAM Review., vol. 31, no. 4, pp. 586-613, 1989

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).