Analysis of the dependence of the fast Fourier transform performance on the amount of processed data
https://doi.org/10.46973/0201-727X_2023_1_136
Abstract
This paper gives brief analysis the algorithms performance dependence for computing the fast Fourier transform on the volume of processed data. All existing algorithms in work do not take into account hardware capabilities of computing devices in full. As a result of non-optimal use of processor memory for different data volumes, the number of operations can greatly increase. Visual analysis of graphs dependence FFT performance on its size allows us to suggest a piecewise continuous nature of this dependence and the reasons for various noncontinuous sections of the graph. When developing implementations of algorithms that use FFT, it is necessary to obtain a method for numerical evaluation of the boundaries of the graph sections. The method under development allows to determine with a high degree of reliability the boundaries of sections on the FFT performance dependence graph, on which the derivative of the graph changes. Algorithms of digital signal processing that uses FFT, it is desirable to develop in such a way that the FFT size does not exceed the boundary determined by the data cache size of the first level of memory cache.
About the Authors
E. A. Altman
Omsk State Transport University (OSTU)
Russian Federation
Russian Federation
Altman Eugeniy Anatolievich, Chair «Automation and Control Systems», Candidate of Engineering Sciences, Associate Professor
A. V. Aleksandrov
Omsk State Transport University (OSTU)
Russian Federation
Russian Federation
Aleksandrov Aleksander Vladimirovich , Chair «Automation and Control Systems», Postgraduate Student, Senior Lecturer
References
1. System of hidden information transmission on the basis of quasi-orthogonal signals / E. A. Altman, A. G. Malyutin, Y. V. Romanov [et al.] // Advances of modern radioelectronics. – 2012. – No. 11. – P. 26–31. – ISSN 2070– 0784.
2. Steven, G. J. A modified split–radix FFT with fewer arithmetic operations / G. J. Steven, M. Frigo // IEEE Transactions on Signal Processing. – 2007. – No. 55(1). – P. 111–119.
3. FFT Benchmark Methodology // FFTW : [website]. – URL: https://fftw.org/speed/method.html (date of access: 12/23/2022).
4. FFT Benchmark Results // FFTW : [website]. – URL: https://fftw.org/speed/ (date of access: 12/23/2022).
5. Intel Integrated Performance Primitives Reference Manual // NACAD. – URL: http://www.nacad.ufrj.br/online/intel/Documentation/en_US/ipp/ippsman.pdf (date of access: 12/23/2022).
6. Frigo, M. FFTW / M. Frigo // FFTW. – URL: https://www.fftw.org/fftw3.pdf (date of access: 12/23/2022).
7. SPIRAL User Manual // SPIRAL Team : [website]. – URL: https://spiral–software.github.io/spiral–software/ (date of access: 12/23/2022).
8. General Purpose FFT (Fast Fourier/Cosine/Sine Transform) Package // Research Institute for Mathematical Sciences (RIMS) : [website]. – URL: https://www.kurims.kyotou.ac.jp/~ooura/fft.html (date of access: 12/23/2022).
Review
For citations:
Altman E.A., Aleksandrov A.V. Analysis of the dependence of the fast Fourier transform performance on the amount of processed data. Vestnik Rostovskogo Gosudarstvennogo Universiteta Putej Soobshcheniya. 2023;(1):136-143. (In Russ.) https://doi.org/10.46973/0201-727X_2023_1_136
Views:
8
JATS XML
Email this article 