Реализация параллельного варианта алгоритма вычисления двумерного быстрого преобразования Фурье по аналогу алгоритма Кули-Тьюки

Abstract

В настоящее время в цифровой обработке сигналов широко применяется двумерное быстрое преобразование Фурье (БПФ). Обычно оно вычисляется при помощи комбинации одномерных БПФ сначала для каждой строки, затем для каждого столбца. В этом случае алгоритм легко адаптируется для параллельных вычислений. В работе представлен способ распараллеливания алгоритма вычисления двумерного БПФ по аналогу алгоритма Кули-Тьюки, требующего меньшее количество комплексных операций сложения и умножения, чем стандартный способ. Главная сложность распараллеливания указанного алгоритма заключается в том, что двумерный аналог алгоритма Кули-Тьюки выполняется итерационно за s проходов при размере исходного сигнала 2^s*2^s. При этом в каждой из s итераций происходит пересчет всего набора используемых данных. Описаны способы решения данной проблемы при распараллеливании в случае реализации алгоритма на языке программирования С++ с использованием библиотек параллельных вычислений OpenMP и MPI. Приведены результаты численного эксперимента, в которых показано, что при распараллеливании достигается ускорение вычислений до 4 раз по сравнению со стандартным способом вычисления двумерного БПФ. Currently, two-dimensional fast Fourier transform (FFT) is widely used in digital signal processing. It is usually calculated using a combination of one-dimensional FFTs, first for each row, then for each column. In this case, the algorithm is easily adapted for parallel computing. The paper presents a method of parallelizing the algorithm for calculating a two- dimensional FFT using an analogue of the Cooley-Tukey algorithm, which requires fewer complex operations of addition and multiplication than the standard method. The main difficulty in parallelizing this algorithm is that the two-dimensional analog of the Cooley- Tukey algorithm is iteratively performed in s passes with the size of the initial signal 2 ^ s * 2 ^ s. Moreover, in each of s iterations, the entire set of used data is recalculated. Methods for solving this problem during parallelization are described in the case of implementing an algorithm in the C ++ programming language using OpenMP and MPI parallel computing libraries. The results of a numerical experiment are presented, in which it is shown that parallelization achieves an acceleration of computations up to 4 times in comparison with the standard method for calculating two-dimensional FFT.