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

Тутатчиков В.С.

Дополнительные ссылки: eLibrary · Источник статьи

База данных: Каталог библиотеки СФУ

Библиографическое описание: Реализация параллельного варианта алгоритма вычисления двумерного быстрого преобразования Фурье по аналогу алгоритма Кули-Тьюки : доклад, тезисы доклада / В. С. Тутатчиков. - [Б. м. : б. и.], 2020. - Текст : непосредственный // Информационные технологии и нанотехнологии (ИТНТ-2020) : Сборник трудов по материалам VI Международной конференции и молодежной школы. В 4-х томах / Под редакцией В.А. Фурсова ; Информационные технологии и нанотехнологии (ИТНТ-2020) (2020 ; 26.05 - 29.05 ; Самара) : Самарский национальный исследовательский университет имени академика С.П. Королева, 2020. - 4. - С. 905-914. - ISBN 9785788315140. Перевод заглавия: Implementation of a parallel version of the algorithm for calculating a two-dimensional FFT using an analog of the Cooley-Turkey algorithm

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

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

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

Держатель оригинала документа: Сибирский федеральный университет

Количество экземпляров:

Твёрдая копия издания отсутствует в фонде библиотеки

Показать дополнительные сведения

ПРИМЕНЕНИЕ АНАЛОГА АЛГОРИТМА КУЛИ – ТЬЮКИ ДВУМЕРНОГО БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ ДЛЯ ЧАСТОТНОЙ…

Носков Михаил Валерианович и др.
2019 год

ПРИМЕНЕНИЕ ПАРАЛЛЕЛЬНОГО АНАЛОГА АЛГОРИТМА КУЛИ – ТЬЮКИ ДВУМЕРНОГО БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ…

Носков Михаил Валерианович и др.
2018 год

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

Альтман Е. А.
2019 год

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

Тутатчиков Валерий Сергеевич и др.
2015 год

О модификации быстрого одномерного преобразования фурье по алгоритму кули-тьюки

Сидорова Т.В. и др.
2015 год

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

Тутатчиков В.С. и др.
2013 год

Программа вычисления двумерного преобразования Фурье (Фурье MPI)

Тутатчиков Валерий Сергеевич и др.
2015 год

Алгоритмы прямого и обратного параметрического быстрого преобразования Фурье

Пономарева О. В. и др.
2022 год

Алгоритмы параметрического быстрого преобразования Фурье

Пономарева О. В. и др.
2021 год

ПРИМЕНЕНИЕ ДВУМЕРНОГО БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ ДЛЯ ЦИФРОВОЙ ОБРАБОТКИ СНИМКОВ ДИСТАНЦИОННОГО…

Киселев Олег Игоревич и др.
2016 год

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

Беспалов М. С.
2025 год

О быстром алгоритме вычисления преобразования Фурье

Алексашкина Анна Андреевна и др.
2021 год

О многомерном аналоге алгоритма Кули-Тьюки

Старовойтов Андрей Владимирович
2010 год

Основы высокопроизводительных вычислений. Параллельные вычислительные алгоритмы

Афанасьев К. Е. и др.
2012 год

Параллельный алгоритм вычисления функций роста в конечных двупорождённых группах периода 5

Кузнецова Александра Сергеевна и др.
2013 год

Реализация алгоритма синтеза диаграммы направленности антенной решетки с помощью итерационного…

Петров А. С. и др.
2021 год

Библиотечно-издательский комплекс СФУ

Похожие публикации