Сибирский федеральный университет

Перевод названия: Implementation of a parallel version of the algorithm for calculating a two-dimensional FFT using an analog of the Cooley-Turkey algorithm

Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций

Конференция: Информационные технологии и нанотехнологии (ИТНТ-2020); Самара; Самара

Год издания: 2020

Аннотация: В настоящее время в цифровой обработке сигналов широко применяется двумерное быстрое преобразование Фурье (БПФ). Обхчно оно вычисляется при помощи комбинации одномерных БПФ сначала для каждой строки, затем для каждого столбца. В этом случае алгоритм легко адаптируется для параллельных вычислений. В работе представлен способ распараллеливания алгоритма вычисления двумерного БПФ по аналогу алгоритма Кули-Тьюки, требующего меньшее количество комплексных операций сложения и умножения, чем стандартный способ. Главная сложность распараллеливания указанного алгоритма заключается в том, что двумерный аналог алгоритма Кули-Тьюки выполняется итерационно за s проходов при размере исходного сигнала 2s*2*s. При этом в каждой из s итераций происходит пересчет всего набора используемых данных. Описаны способы решения данной проблемы при распараллеливании в случае реализации алгоритма на языке программирования C++ с использованием библиотек параллельных вычислений 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 twodimensional 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.

Журнал: Информационные технологии и нанотехнологии (ИТНТ-2020)

Выпуск журнала: 4

Номера страниц: 905-914

Издатель: Самарский национальный исследовательский университет имени академика С.П. Королева

• Тутатчиков В.С. (Сибирский федеральный университет)

• Ядро РИНЦ (eLIBRARY.RU)