Разработка алгоритма быстрого преобразования Фурье на базе модели акторов Гребень Никита Владимирович, студент;
Елькина Анна Александровна, студент;
Пашкин Илья Андреевич, студент
Санкт-Петербургский государственный университет
В данной работе авторами представлен параллельный алгоритм быстрого преобразования Фурье, универсальным примитивом выполнения вычислений которого является семейство акторов. Ключевые слова: модель акторов, параллельное программирование, быстрое преобразование Фурье. М
одель акторов является обобщением сетей конечных ав-
томатов, не имеющих ограничений на глобальную син-
хронизацию и определенный порядок поступления сообщений,
что дает новые возможности в написании параллельных про-
грамм. В основном модель используется как теоретическая
база для создания параллельных систем, в частности, в насто-
ящее время находит применение в мультиагентных системах
и облачных вычислениях [1]. В виду конкурентности (concur-
rency) модели и её фундаментально отличительных концепций,
интересно проследить возможность адаптаций традиционных
последовательных алгоритмов под данный вид модели парал-
лельных вычислений, а также выявить её недостатки.
Цель данной работы состоит в разработке параллельного
алгоритма быстрого преобразования Фурье, путем создания
подходящей топологии системы акторов и распределения вы-
числительных компонентов по её узлам, а также сравнительный
анализ относительно последовательного аналога.
На первом этапе алгоритма происходит инициализация си-
стемы акторов — получение значений вектора коэффициентов
многочлена, создание актора с поведением
fft , который ответ-
ственен за вычисление быстрого преобразования Фурье, прои-
нициализированный размером вектора, первообразными кор-
нями из единицы, и адресом идентификатора актора, куда будет
отправлен результат преобразования [2]. Затем происходит пе-
ресылка сообщения в созданный актор, инициирующая на-
чало вычислений. Следующим этапом происходит развер-
тывание классического алгоритма быстрого преобразования
Фурье в виде двоичного дерева. Корень дерева отвечает за все
компоненты коэффициентов полинома, где для всех остальных
вершин, кроме листьев, каждому левому потомку соответ-
ствуют элементы, стоящие на четных местах предка, а каждому
правому — на нечетных (Рис. 1). Задача для акторов поведения
fft заключается в управлении и передачи необходимых параме-
тров для инициализаций акторов с поведением
merge , выпол-
няющих пересчет DFT и слияние результатов преобразования,
а также определение листовых элементов — моментов окон-
чания создания новых акторов типа
fft [3]. Для их выявления
каждому актору, помимо первообразных корней и PID порож-
дающего процесса [4], необходимо пересылать переменную, на-
капливающую сумму степеней двойки для правых потомков на
каждой глубине дерева (Рис. 1).
Процессы типа
merge выполняют несколько функций: они
ожидают прихода двух последовательностей, производят их
слияние, создают новый актор и передают ему данные для пере-
расчета DFT над вектором коэффициентов. При ожидании двух
последовательностей, акторы реализуют простейшего рода
ба- рьерную синхронизацию [5]
. Топология получившейся системы
представлена на Рисунке 2.