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