Анализ зависимости быстродействия быстрого преобразования Фурье от объема обрабатываемых данных

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

1. Система скрытой передачи информации на базе квазиортогональных сигналов / Е. А. Альтман, А. Г. Малютин, Ю. В. Романов [и др.] // Успехи современной радиоэлектроники. – 2012. – № 11. – С. 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.kyoto-u.ac.jp/~ooura/fft.html (date of access: 12/23/2022).