vrgupВестник Ростовского государственного университета путей сообщенияVestnik Rostovskogo Gosudarstvennogo Universiteta Putej Soobshcheniya0201-727XРостовский государственный университет путей сообщения10.46973/0201-727X_2023_1_136vrgup-73Research ArticleМОДЕЛИРОВАНИЕ СИСТЕМ И ПРОЦЕССОВMODELING SYSTEMS AND PROCESSESАнализ зависимости быстродействия быстрого преобразования Фурье от объема обрабатываемых данныхAnalysis of the dependence of the fast Fourier transform performance on the amount of processed dataАльтманЕ. А.AltmanE. A.

Альтман Евгений Анатольевич, кафедра «Автоматика и системы управления», кандидат технических наук, доцент

Altman Eugeniy Anatolievich, Chair «Automation and Control Systems», Candidate of Engineering Sciences, Associate Professor 

AltmanEA@gmail.comАлександровА. В.AleksandrovA. V.

Александров Александр Владимирович, кафедра «Автоматика и системы управления», аспирант, старший преподаватель

Aleksandrov Aleksander Vladimirovich , Chair «Automation and Control Systems», Postgraduate Student, Senior Lecturer 

Alexandrov_A_V@mail.ruОмский государственный университет путей сообщения (ОмГУПС)Omsk State Transport University (OSTU)20233003202301136143Copyright © Альтман Е.А., Александров А.В., 20232023Альтман Е.А., Александров А.В.Altman E.A., Aleksandrov A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.rgups.ru/jour/article/view/73

Приведен краткий анализ зависимости быстродействия алгоритмов расчета быстрого преобразования Фурье от объема обрабатываемых данных. Все существующие алгоритмы в работе не учитывают аппаратные возможности вычислительных устройств в полном объеме. В результате неоптимального использования памяти процессоров для различных объемов данных количество операций может сильно возрастать. Визуальный анализ графиков зависимостей производительности быстрого преобразования Фурье (БПФ) от его размера позволяет предположить кусочно-непрерывный характер этой зависимости и причины возникновения различных непрерывных участков графика. При разработке реализаций алгоритмов, использующих БПФ, необходимо получить метод численной оценки границ участков графиков. Разрабатываемый метод позволяет с высокой степенью достоверности определить границы участков на графике зависимости производительности БПФ от его размера, на которых изменяется производная графика. Алгоритмы цифровой обработки сигналов, использующие БПФ, желательно разрабатывать таким образом, чтобы размер БПФ не превышал границу, определяемую объемом кэш-памяти первого уровня.

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.

быстрое преобразование Фурьекусочно-линейная аппроксимациявычислительная эффективностьпроизводительностьбыстродействиеархитектура аппаратных средствграницы участковfast Fourier transformpiecewise linear approximationcomputational efficiencyperformancespeedhardware architecturearea boundariesReferencesСистема скрытой передачи информации на базе квазиортогональных сигналов / Е. А. Альтман, А. Г. Малютин, Ю. В. Романов [и др.] // Успехи современной радиоэлектроники. – 2012. – № 11. – С. 26–31. – ISSN 2070–0784.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.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.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.FFT Benchmark Methodology // FFTW : [website]. – URL: https://fftw.org/speed/method.html (date of access: 12/23/2022).FFT Benchmark Methodology // FFTW : [website]. – URL: https://fftw.org/speed/method.html (date of access: 12/23/2022).FFT Benchmark Results // FFTW : [website]. – URL: https://fftw.org/speed/ (date of access: 12/23/2022).FFT Benchmark Results // FFTW : [website]. – URL: https://fftw.org/speed/ (date of access: 12/23/2022).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).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).Frigo, M. FFTW / M. Frigo // FFTW – URL: https://www.fftw.org/fftw3.pdf date of access: 12/23/2022).Frigo, M. FFTW / M. Frigo // FFTW. – URL: https://www.fftw.org/fftw3.pdf (date of access: 12/23/2022).SPIRAL User Manual. // SPIRAL Team : [website]. – URL: https://spiral–software.github.io/spiral–software/ (date of access: 12/23/2022).SPIRAL User Manual // SPIRAL Team : [website]. – URL: https://spiral–software.github.io/spiral–software/ (date of access: 12/23/2022).General Purpose FFT (Fast Fourier/Cosine/Sine Transform) Package // Research Institute for Mathematical Sciences (RIMS) : [website]. – URL: https://www.kurims.kyoto-u.ac.jp/~ooura/fft.html (date of access: 12/23/2022).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).

The authors declare that there are no conflicts of interest present.