A parallel hardware-oriented algorithm for constant matrix-vector multiplication with reduced multiplicative complexity

摘要

This paper presents the algorithmic aspects of organization of a low-complexity fully parallel processor unit for constant matrix-vector products computing. To reduce the hardware complexity (number of two-operand multipliers), we exploit the Winograd's inner product calculation approach. We show that by using this approach, the computational process of calculating the constant matrix-vector product can be structured so that it eventually requires fewer multipliers than the direct implementation of matrix-vector multiplication.%W pracy został przedstawiony sprzętowo-zorientowany algorytm wyznaczania iloczynu wektora przez macierz stałych. W odróżnieniu od implementacji naiwnego sposobu zrównoleglenia obliczeń wymagającego N~2 układów mnożących proponowana równoległa struktura wymaga tylko N(M+1)/2 takich układów. A ponieważ układ mnożący pochłania znacznie więcej zasobów sprzętowych platformy implementacyjnej niż sumator, to minimalizacja liczby tych układów podczas projektowania dedykowanych układów obliczeniowych jest sprawą nadrzędną. Idea syntezy algorytmu oparta jest na wykorzystaniu do wyznaczania cząstkowych iloczynów skalarnych metody S. Winograda. Zaprezentowany w artykule algorytm może być z powodzeniem zastosowany do akceleracji obliczeń w podsystemach cyfrowego przetwarzania danych zrealizowanych na platformach FPGA oraz zaimplementowany 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.