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

1 Описание свойств и структуры алгоритма

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

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

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

2.2.2 Описание локальности реализации алгоритма

2.2.2.1 Описание структуры обращений в память и качественная оценка локальности

Рисунок 12.1. Нерекурсивная реализация БПФ для степеней двойки. Общий профиль обращений в память

На рисунке 12.1 представлен профиль обращений в память для нерекурсивной реализации быстрого преобразования Фурье. Исходя из исходного кода, можно увидеть, что в программе задействовано 3 массива. Фрагменты двух из них отмечены на рис. 12.1 зеленым, к третьему массиву относится вся остальная часть профиля.

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

Гораздо интереснее устроен последний фрагмент. Его можно разбить на 4 этапа, которые выделены на рис. 12.1 оранжевым цветом. Первый этап по времени совпадает с фрагментом 1, и сам профиль также похож на последовательный перебор. Из исходного кода видно, что обращения этапа 1 – это запись в массив data либо 0, либо значений, считываемых во фрагменте 1 из массива dIn:

for( i = 0; i < nn; i++ ) {
data [ i ] = 0;
data[ i * 2 + 1 ] = dIn[ i ];
}

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

Рассмотрим более подробно этап 2 (рис. 12.2). Можно увидеть, что в начале этого этапа происходят обращения по всему массиву, но чем ближе к концу этапа, тем ближе к концу массива происходят обращения. Видно, что часть обращений (кривая внизу рисунка) расположены близко друг к другу, а остальные обращения разбросаны достаточно далеко и образуют нечто похожее на случайный доступ.

Рисунок 12.2. Основной фрагмент, этап 2

Исходный код, в котором происходят обращения данного этапа, устроен следующим образом:

while( i < n ) {
if( j > i ) {
tempr = data[ i ]; data[ i ] = data[ j ]; data[ j ] = tempr;
tempr = data[ i + 1 ]; data[ i + 1 ] = data[ j + 1 ]; 
data[ j + 1 ] = tempr;
}
m = n >> 1;
while( ( m >= 2 ) && ( j > m ) ) {
j = j - m;
m = m >> 1;
}
j = j + m;
i = i + 2;
}

Можно увидеть, что действительно обращения выполняются по двум независимым индексам – на основе переменных i и j; при этом обращения на основе индекса i образуют кривую внизу рис. 12.2, а обращения на основе индекса j – остальные, разбросанные по всему массиву обращения.

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

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

Теперь перейдем к рассмотрению самого длительного этапа 3. Отдельно данный фрагмент представлен на рис. 12.3. Исходя из рисунка, можно увидеть, что данный фрагмент состоит из нескольких итераций, причем первая итерация состоит из единичного перебора элементов массивов с некоторым шагом, вторая итерация состоит из двух проходов с одинаковым шагом (большим, чем на первой итерации), третья – из 4-х проходов и т.д., пока число проходов на итерации не начинает уменьшаться в обратную сторону. Итерации разделены на рис. 12.3 оранжевыми линиями.

Рисунок 12.3. Основной фрагмент, этап 3

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

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

Более подробное изучение каждого прохода (рис. 12.4, на которой приближена выделенная зеленым часть рис. 12.3) показывает, что он обладает более сложной структурой, чем просто перебор элементов массива с некоторым шагом: в данном случае происходит серия близких друг к другу обращений, и затем сдвиг на некоторый шаг. Это приводит к некоторому улучшению как пространственной, так и временной локальности.

Рисунок 12.4. Основной фрагмент, небольшая часть этапа 3

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

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

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

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

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

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

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