Effectiveness of Fast Fourier Transform implementations on GPU and CPU

• Autorzy: Puchała D. , Stokfiszewski K. , Szczepaniak B. , Yatsymirskyy M.

Identyfikatory

DOI

10.15199/48.2016.07.14

Warianty tytułu

PL

Porównanie efektywności wybranych wariantów algorytmów szybkiej transformaty Fouriera (FFT) realizowane na procesorach graficznych (GPU) i jednostkach centralnych (CPU)

• Języki publikacji: EN

Abstrakty

EN

In this paper, we present the results of comparison of the effectiveness of selected variants of radix-2 Fast Fourier Transform (FFT) algorithms implemented on both Graphics (GPU) and Central (CPU) Processing Units. The considered algorithms differ in memory consumption and the arrangement of data-flow paths which affects the global memory coalescing and cache memory exploitation. The obtained results allow to indicate the variants of FFT algorithms which are best suited for GPU and CPU architectures, to confirm the advisability of GPU oriented calculations of FFT and to formulate a guideline for implementations of fast algorithms of various linear transforms.

W niniejszej pracy przedstawiono wyniki porównania efektywności wybranych wariantów algorytmów szybkiej transformaty Fouriera (FFT) typu radix-2 realizowanych zarówno dla procesorów graficznych (GPU) jak i typowych jednostek centralnych (CPU). Rozważane algorytmy różnią się zapotrzebowaniem pamięciowym oraz postaciami grafów przepływu danych, które mają wpływ na spójność wykorzystania pamięci globalnej oraz pamięci cache jednostek GPU i CPU. Uzyskane wyniki pozwalają na wskazanie wariantów algorytmów FFT, które są najlepiej dostosowane dla architektur GPU i CPU, pozwalają też potwierdzić celowość realizacji implementacji FFT zorientowanych na wykorzystanie jednostek GPU, a także sformułować ogólne wytyczne dla implementacji zorientowanych na wykorzystanie jednostek GPU algorytmów szybkich przekształceń liniowych.

Słowa kluczowe

EN

fast Fourier transform; parallel computation; GPU computation

PL

szybkie przekształcenie Fouriera; obliczenia równoległe; GPU; CPU

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2016
• Tom: R. 92, nr 7
• Strony: 69--71
• Opis fizyczny: Bibliogr. 11 poz., rys., tab., wykr.

Twórcy

autor

Puchała D.

• Institute of Information Technology, Faculty of Technical Physics, Computer Science and Applied Mathematics, Technical University of Lodz, ul. Wólczanska 215, 90-924 Łódz, Poland

autor

Stokfiszewski K.

• Institute of Information Technology, Faculty of Technical Physics, Computer Science and Applied Mathematics, Technical University of Lodz, ul. Wólczanska 215, 90-924 Łódz, Poland

autor

Szczepaniak B.

• Institute of Applied Computer Science, ul. Stefanowskiego 18/22, 90-924 Łódz, Poland

autor

Yatsymirskyy M.

• Institute of Information Technology, Faculty of Technical Physics, Computer Science and Applied Mathematics, Technical University of Lodz, ul. Wólczanska 215, 90-924 Łódz, Poland

Bibliografia

• [1] J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. E. Lefohn, T. Purcell, A survey of generalpurpose computation on graphics hardware, Computer Graphics Forum, vol. 26, no. 1, pp. 80–113, Mar. 2007.
• [2] N. K. Govindaraju, B. Lloyd, Y. Dotsenko, B. Smith, J. Manferdelli, High Performance Discrete Fourier Transforms on Graphics Processors, Proc. 2008 ACM/IEEE Conf. on Supercomputing, IEEE Press Piscataway, NJ, USA 2008.
• [3] U. N. Ahmed, K. R. Rao, Orthogonal Transforms for Digital Signal Processing, Springer-Verlag New York, Inc., Secaucus, NJ, USA. ISBN 0-387-06556-3.
• [4] D. Puchala, K. Stokfiszewski, Parametrized Orthogonal Transforms for Data Encryption, Computational Problems of Electrical Engineering Journal, vol. 3, no. 1, pp. 93-97, 2013.
• [5] M. Yatsymirskyy, K. Stokfiszewski, P. S. Szczepaniak, Image compression using fast transforms realized through neural network learning, Modelling of Computer Science Technologies, Ukrainian National Academy of Sciences vol. 23, pp. 95–99, 2003.
• [6] J. W. Cooley, J. W. Tukey, An algorithm for the machine calculation of complex Fourier series, Mathematics of Computation vol. 19, no. 90, pp. 297–301, Apr. 1965.
• [7] M. Yatsymirskyy, Fast algorithms for orthogonal trigonometric transforms’ computations, (in Ukrainian), Lviv Academic Express, ISBN 966-7094-16-2, Lviv, 1997.
• [8] T. Wiechno, M. Yatsymirskyy, Two-stage Fast Fourier and Hartley Transform of Real Data Sequence, Przegląd Elektrotechniczny, vol. 86, no. 1, pp. 41-43, 2010.
• [9] K. Moreland, E. Angel, The FFT on a GPU, in Proc. ACM SIGGRAPH/EUROGRAPHICS Conf. on Graphics Hardware, 2003, pp. 112–119.
• [10] J. Spitzer, Implementing a GPU-efficient FFT, SIGGRAPH Course on Interactive Geometric and Scientific Comput. with Graphics Hardware, 2003.
• [11] J. J. Rodriguez, An Improved FFT Digit-Reversal Algorithm, IEEE Trans. on Acoustics, Speech and Signal Processing, vol. 37. no. 8, pp. 1298-1300, 1989.

Uwagi

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