Ч а с т ь I главный редактор


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



Pdf көрінісі
бет20/77
Дата01.10.2023
өлшемі7,26 Mb.
#183162
1   ...   16   17   18   19   20   21   22   23   ...   77
Байланысты:
moluch 366 ch1

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

Топология получившейся системы 
представлена на Рисунке 2.


“Young Scientist”


Достарыңызбен бөлісу:
1   ...   16   17   18   19   20   21   22   23   ...   77




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет