Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску


Простой алгоритм Кули-Тьюки
Последовательный алгоритм
Последовательная сложность [math]O (n log_{2} n)[/math]
Объём входных данных [math]n[/math]
Объём выходных данных [math]n[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]O (log_{2} n)[/math]
Ширина ярусно-параллельной формы [math]n[/math]


Основные авторы описания: А.В.Фролов, Вад.В.Воеводин (раздел 2.2),А.М.Теплов (раздел 2.4)

Содержание

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Простой алгоритм Кули-Тьюки - один из вариантов быстрого преобразования Фурье для комплексных векторов с размерностью, равной степени двойки, без использования специфичных приёмов, использующихся для степеней четвёрки, восьмёрки и др.[1] Заключается в последовательном применении метода быстрого преобразования Фурье и сведении преобразования к последовательности преобразований Фурье размерности 2 и выполнения умножений на т.н. поворотные множители. Несмотря на то, что проигрывает алгоритмам Кули-Тьюки, разлагающим степени двойки на степени 4, 8 и др. и использующим их специфику, весьма распространён, что связано с самой простой из алгоритмов БПФ записью программной реализации.

1.2 Математическое описание алгоритма

Исходные данные: преобразуемый комплексный вектор [math]a[/math] (элементы [math]a_{i}[/math]).

Вычисляемые данные: комплексный вектор - результат преобразования [math]b[/math] (элементы [math]b_{i}[/math]).

Размерность векторов - [math]n[/math], причём [math]n = 2^l[/math]

1.2.1 Рекурсивное описание

Вектор записывается по строкам по 2 элемента в каждой. После этого над каждой строкой выполняется преобразование Фурье порядка 2, получившиеся элементы умножаются на поворотные множители [math]exp (2 \pi i(m-1)(j-1)/n)[/math] ([math]m[/math] - номер строки, [math]j[/math] - номер столбца), после чего выполняется БПФ порядка [math]n/2[/math] над каждым из столбцов. Поскольку для 1-го столбца поворотные множители равны 1, то реально умножение на них не выполняется, а умножения на поворотные множители элементов второго столбца соединяются с преобразованием Фурье порядка 2. Эта комбинация, называемая "бабочкой" в среде специалистов по БПФ, и является основной операцией в простом алгоритме Кули-Тьюки. "Бабочка" состоит из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего на каждом шаге выполняется [math]n/2[/math] "бабочек", а шагов - [math]l-1[/math]. Последний, [math]l[/math]-й шаг вычисляет только суммы и разности.

1.2.2 Тригонометрические функции

Несмотря на то, что в вычислениях используются поворотные множители [math]exp (2 \pi i(m-1)(j-1)/n)[/math], нецелесообразно вычислять их в процессе выполнения алгоритма Кули-Тьюки, поскольку вычисления косинусов и синусов (в мнимой экспоненте) тогда составили бы львиную долю вычислений алгоритма. Поэтому обычно (как и в других версиях БПФ) поворотные множители вычисляются заранее и хранятся в специальном массиве. Здесь мы будем предполагать, что алгоритм выполняется именно так.

1.3 Вычислительное ядро алгоритма

Вычислительное ядро алгоритма составляют "бабочки", состоящие из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего их [math](1/2) n log_{2} n [/math] штук, при этом в [math]n/2[/math] из них умножение не выполняется.

1.4 Макроструктура алгоритма

Макроструктура алгоритма лучше всего описывается рекурсивно, как [math]n/2[/math] преобразований Фурье порядка 2, умножение [math]n/2[/math] пар комплексных чисел и затем 2 БПФ порядка [math]n/2[/math].

1.5 Схема реализации последовательного алгоритма

Нерекурсивная схема организации состоит в том, что на каждом шаге (а всего их [math]log_{2} n [/math]) для выполнения "бабочки" все элементы разбиваются на [math]n/2[/math] пар. В зависимости от номера шага, разница координат для каждой пары элементов удваивается. На первом шагу она равна 1, на последнем - [math]n/2[/math]. При этом результат суммы записывается в элемент с меньшим номером, а результат вычитания с последующим умножением - в элемент с большим.

1.6 Последовательная сложность алгоритма

Если считать только главные члены выражений для последовательной сложности алгоритма, то простой алгоритм Кули-Тьюки может быть выполнен за [math]n log_{2} n[/math] операций комплексного сложения и [math](1/2) n log_{2} n [/math]операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к линейно-логарифмическому классу по последовательной сложности.

1.7 Информационный граф

Рисунок 1. Простой алгоритм Кули-Тьюки для n=8. Op+ - операция сложения двух комплексных чисел. Op- - операция вычитания двух комплексных чисел и умножения результата вычитания на комплексное число (поворотный множитель). В последнем столбце операций умножение не производится. Привязка вершин выполнена по оси абсцисс - к параметру внешнего цикла, по оси ординат - к обрабатываемым элементам массива

Как видно из рисунка, этот граф не является линейным ни по размерам, ни по формулам для дуг графа. По размерам он линейно-логарифмический, а формулы дуг имеют экспоненциальные компоненты.В элементарной "бабочке" на i-м шаге каждый раз участвует пара элементов массива, у которых запись их номеров, уменьшенных на единицу, в двоичной системе различается только в i-1-м бите.

1.8 Ресурс параллелизма алгоритма

Если считать только главные члены выражений, то простой алгоритм Кули-Тьюки имеет критический путь, состоящий из [math]log_{2} n [/math] операций комплексного сложения/вычитания и [math]log_{2} n [/math] операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к логарифмическому классу по параллельной сложности. По ширине ЯПФ сложность алгоритма линейна.

1.9 Входные и выходные данные алгоритма

Входные данные: вектор [math]a[/math] (элементы [math]a_{i}[/math]).

Объём входных данных: [math]n[/math] .

Выходные данные: вектор [math]b[/math] (элементы [math]b_{i}[/math]).

Объём выходных данных: [math]n[/math].

1.10 Свойства алгоритма

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является линейным.

При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – логарифмическая.

При этом алгоритм полностью детерминирован.

Заметим, что простой алгоритм Кули-Тьюки не является оптимальным даже для векторов размером степень двойки. Однако здесь мы не рассматриваем другие алгоритмы БПФ.

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

В простейшем варианте алгоритм на Фортране можно записать так, что входной и выходной массивы совпадают (здесь использован массив X):

         
        subroutine STEP2(x,y,pov)
        complex x, y, pov, u, v
        u = x + y
        v = (x-y)*pov
        x = u
        y = v
        return
        end
        subroutine FFT2(X, POV, N, N2, L)
C
C L = Log2N
C N2 = N/2
C
        complex X(0:N-1), POV(0:N2-1)
        DO I = 0, L-1
            DO J = 0, N2/2**I-1
            DO K = 0, 2**I-1
                call STEP2(X(2*J*2**I+K)), X(2*J*2**I+2**I+K), POV(J*2**I))
            END DO
            END DO
         END DO
         return
         end

Здесь предполагается, что поворотные множители первого шага (они потом используются и на последующих шагах) предвычислены заранее и лежат в элементах массива POV (а в его нулевом элементе - единица). К сожалению, подавляющее большинство реализаций простого алгоритма Кули-Тьюки вычисляет поворотные множители одновременно с вычислением "бабочки", что её значительно замедляет.

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности
Рисунок 2. Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки. Общий профиль обращений в память

На рис. 2 представлен профиль обращений в память для реализации простого алгоритма Кули-Тьюки быстрого преобразования Фурье для степеней двойки. Данный профиль состоит из обращений к двум массивам (разделены зеленой линией). В целом можно увидеть, что общее число обращений заметно больше числа задействованных данных, поэтому многие элементы используются повторно. Также видно, что вначале элементы обоих массивов перебираются последовательно, однако затем порядок обращений изменяется. Чтобы понять, как устроено это изменение, рассмотрим профиль подробнее.

На рис. 3 представлен фрагмент 1 – обращения к началу первого массива на протяжении всей программы. Видно, что при каждом следующем переборе массива задействуется все меньше элементов – возрастает шаг, с которым выбираются элементы. Такое поведение характеризуется средней локальностью – с каждой итерацией увеличивается шаг, а значит, и ухудшается пространственная локальность. Однако при этом число обращений на итерацию уменьшается, а значит, уменьшается время до повторного обращения, т.е. улучшается временная локальность.

Особенно стоит отметить конец фрагмента, где видно множество обращений к самому началу массива. Из рис. 2 видно, что есть еще несколько элементов массива, к которым в конце профиля выполняется множество обращений. Такой профиль является идеальным с точки зрения локальности – и пространственная, и временная локальности принимают практически максимальное значение.

Рисунок 3. Профиль обращений, фрагмент 1

Далее рассмотрим рис. 4, на котором представлен характерный фрагмент для второго массива. Здесь можно увидеть, что строение каждой итерации очень похоже, только при переходе к следующей итерации увеличивается в 2 раза шаг по памяти, в результате чего видимые отрезки на рисунке увеличиваются вдвое. Такой фрагмент обладает не очень высокой пространственной локальностью, что связано с изменением шага, а также не очень высокой временной локальностью, поскольку между повторными обращениями на разных итерациях выполняется достаточно много обращений.

Рисунок 4. Профиль обращений, фрагмент 2

В целом можно сказать, что основная масса обращений общего профиля показывает среднюю локальность, как пространственную, так и временную. Однако отмеченные в конце первого массива обращения к одним и тем же элементам могут в значительной степени повлиять на общую оценку.

2.2.1.2 Количественная оценка локальности

Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен здесь (функция Kernel). Условия запуска описаны здесь.

Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

На рисунке 5 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что данная программа показывает результат немного хуже среднего, что примерно соответствует нашим ожиданиям согласно качественной оценке. Отметим, что вывод относительно среднего значения делается на основе анализа абсолютных значений, а не положения на графике (здесь не представлена часть программ с низкими значениями). Обратим внимание, что значение daps очень близко к daps для реализации уравнения Пуассона. Это вполне закономерно, поскольку данная реализация построена с использованием данной реализации БПФ.

Рисунок 5. Сравнение значений оценки daps

Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.

Рисунок 6. Сравнение значений оценки cvg

На рисунке 6 значения приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что данная реализация показывает наилучшее значение cvg среди всех рассмотренных программ. Это в определенной степени не соответствует качественному анализу и оценка daps. По всей видимости, здесь повлиял отмеченный выше фрагмент с обращениями к одним и тем же элементам, который в значительной степени улучшил значение оценки. Вероятно, стоит рассмотреть возможность модификации cvg для более аккуратного учета таких случаев.

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

  • число процессоров [4, 8 : 64] с шагом 8;
  • размер вектора [128 : 32768] с шагом равным степени двойки.

В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:

  • минимальная эффективность реализации 0.000000002% (1.85994069951e-09%);
  • максимальная эффективность реализации 0.00002% (2.07351573426e-05%).

На следующих рисунках приведены графики производительности и эффективности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.

Рисунок 7. Параллельная реализация алгоритма. Изменение производительности в зависимости от числа процессоров и размера области.
Рисунок 8. Параллельная реализация алгоритма. Изменение эффективности в зависимости от числа процессоров и размера матрицы.

Алгоритм в силу своих особенностей имеет крайне низкую эффективность параллельного выполнения, связанную с крайне малым объемом вычислений на каждый процесс. Из-за этого накладные расходы на организацию параллельного выполнения становятся доминирующими при выполнении алгоритма.

Исследованная параллельная реализация алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

Для проведения экспериментов использовалась реализация алгоритма Кули-Тьюки, в реализации, доступной здесь. Все результаты получены на суперкомпьютере "ГрафИТ!". Использовались процессоры Intel Xeon X5570 с пиковой производительностью в 94 Гфлопс, а также компилятор Gnu 4.4.7. На рисунках показана эффективность реализации алгоритма Кули-Тьюки на 64 процессах.

Рисунок 9. График загрузки CPU при выполнении алгоритма Кули-Тьюки

На графике загрузки процессора видно, что почти все время работы программы уровень загрузки составляет около 20%. Это указывает на существенную недозагруженность вычислениями процессора.

Рисунок 10. График операций с плавающей точкой в секунду при выполнении алгоритма Кули-Тьюки

На Рисунке 11 показан график количества операций с плавающей точкой в секунду. На графике видна общая низкая производительность вычислений.

Рисунок 11. График кэш-промахов L1 в секунду при работе алгоритма Кули-Тьюки

На графике кэш-промахов первого уровня видно, что число промахов достаточно большое для нескольких ядер и находится на уровне 25 млн/сек. В среднем по всем узлам значения значительно ниже. Это указывает на неравномерное распределение вычислений.

Рисунок 12. График кэш-промахов L3 в секунду при работе алгоритма Кули-Тьюки

На графике кэш-промахов третьего уровня видно, что число промахов все еще достаточно большое для небольшого числа процессов и находится на уровне 1,5 млн/сек, однако в среднем по всем узлам значения низкие.

Рисунок 13. График количества чтений из оперативной памяти при работе алгоритма Кули-Тьюки

На графике чтений из памяти на наблюдается неравномерная активность чтения из памяти процессами: несколько читают очень активно, остальные используют значительно менее эффективно. Однако активность тех нескольких процессов чтения из памяти достаточно высока, что в сочетании с показаниями достаточно высокого уровня кэш-промахов указывает на достаточно большой процент промахов из кэш в оперативную память.

Рисунок 14. График количества записей в оперативную память при работе алгоритма Кули-Тьюки

На графике записей в память видна похожая картина неравномерности вычислений, при которой одновременно активно выполняют запись только несколько процессов. Это коррелирует с другими графиками выполнения и указывает на низкую эффективность данной реализации.

Рисунок 15. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Кули-Тьюки

На графике скорости передачи данных по сети Infiniband наблюдается достаточно низкая скорость передачи данных в байтах в секунду. Это говорит о том, что процессы между собой обмениваются небольшими порциями данных.

Рисунок 16. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Кули-Тьюки

На графике скорости передачи данных в пакетах в секунду наблюдается очень высокая интенсивность передачи данных выраженная в пакетах в секунду. Это говорит о том, что, вероятно, процессы обмениваются сообщениями очень низкой длины, но очень интенсивно. Так же наблюдается меньший дизбаланс между процессами чем наблюдаемый в графиках использования памяти и вычислений. Это указывает на то, что при поступлении необходимых данных часть процессов начинает интенсивные вычисления, хотя другие продолжают простаивать.

Рисунок 17. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Кули-Тьюки

На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно и приблизительно равняется 3. Это свидетельствует о стабильной работе программы с загруженной только частью вычислительных узлов. Это указывает на очень нерациональную и статичную загрузку аппаратных ресурсов процессами. И показывает низкую эффективность выполняемой реализации. В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала неэффективно, но стабильно. Использование памяти и коммуникационной среды достаточно интенсивное, при этом объемы передаваемых данных являются крайне малыми. Это указывает на необходимость использования оптимизаций алгоритмической части программы. Низкая эффективность связана судя по всему с недостаточным объемом вычислений на каждом процессе, интенсивными обменами малой длины сообщений. Это приводит к постоянному ожиданию процессами данных для вычислений и простою даже в рамках одного вычислительного узла.

2.6 Выводы для классов архитектур

Граф простого алгоритма Кули-Тьюки лучше всего из коммуникационных сетей отображается на сеть типа гиперкуб. Распространённость БПФ в методах решения различных задач поэтому привела к популярности идеи вычислительных систем с сетью типа гиперкуб в начале развития различных параллельных вычислительных систем. В настоящее время, однако, массово такие вычислительные системы не используются по физическим причинам, делающим гиперкуб большой размерности труднореализуемым на практике. Как видно из графа, при простом его разбиении на части прямыми, параллельными оси шагов, на первых шагах алгоритма обмены между разными частями будут отсутствовать, но, начиная с некоторого момента, они станут составлять величину, сопоставимую с количеством арифметических операций. Этого, однако, можно избежать, если примерно посередине алгоритма переупорядочить все данные. В графе это будет соответствовать смене разбиения на части. При выполнении указанных рекомендаций, алгоритм можно будет реализовать более эффективно, чем в настоящее время, и на архитектурах типа кластерной и на других архитектурах, реализующих разбиение процесса на независимые ветви.

2.7 Существующие реализации алгоритма

Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки весьма распространён среди начинающих, использующих БПФ, и его сравнительно легко можно найти в Интернете с помощью поисковых сайтов. Как правило, эти реализации не используют описанных выше приёмов улучшения эффективности вычислений - ни для последовательной, ни для параллельной архитектуры. Связано это с тем, что сам по себе простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки проигрывает другим алгоритмам Кули-Тьюки, которые используют специфику, например, чётных степеней двойки, и потому более экономичны. Поэтому большинство исследователей, которым нужны более быстрые программы БПФ, не улучшают эффективность этого алгоритма, а меняют его на другой. Это же рекомендуем делать и читателям.

3 Литература

  1. В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.