Диссертация (1150736), страница 23
Текст из файла (страница 23)
Как и в приложении D,сложность комплексного БПФ на отсчётов обозначим (), вещественногоБПФ — (), а двойной вещественной интерполяции — ().Лемма 19 Сложность () реализации быстрого алгоритма Шура для размерности = 2 удовлетворяет уравнению (2) = 2 () + 4() + 4 (2) + (34 + 2) R +(24 − 2) R .Доказательство.
Докажем лемму индукцией по высоте бинарного дерева. Алгоритм обхода бинарного дерева высоты + 1 состоит в обходе двухбинарных деревьев высоты , с корневыми вершинами, имеющими мультииндексы 0 и 1, а также в обработке этих двух вершин. Поэтому величина143 (2) − 2 () = ∆ равна сумме количества операций в чётной и нечётнойвершине дерева.Интерполяция ДПФ одного вещественного многочлена с на 2 отсчётов требует () операций. Для двух многочленов Шура и для двух вершинполучается 4() операций.Рассмотрим обработку чётной вершины.
В п. 1 выполнение двух ДПФ на2 вещественных отсчётов требует 2 (2) операций.̂︀ , ̂︀ )2−1 , затем выполняются два вещеВ п. 2 вычисляются векторы (=0ственных ОДПФ на 2 отсчётов и результат делится на вещественное число.Все комплекснозначные векторы в алгоритме являются ДПФ от вещественных массивов. Поэтому в памяти достаточно хранить только половину их зна̂︀ , ̂︀ ), а также ( , ) и ( , ) — вещественные причений. Значения ( = 0 и при = .
Кроме них, в памяти хранятся значения при 1 ≤ ≤ − 1,которые комплексные. Реализация умножения при = 0 или при = требует4 вещественных умножения и 2 вещественных сложения. Реализация умножения при 1 ≤ ≤ − 1 требует 4 комплексных умножения и 2 комплексныхсложения,.−1̂︀ −1Наконец, умножение вещественных векторов (̂︀ )−1тре=0 и ( )=0 на бует 2 вещественных умножений.В п. 3 выполняется одно вещественное умножения и одно вещественноесложение, а также одна операций обращения вещественного числа.Итого, количество операций в п. 2 и 3 обработки чётной вершины составляет∆2 = ( − 1)(4 C +2 C ) + 2(4 R +2 R ) + 2 (2) + 2 R +2 R + R .Рассмотрим обработку нечётной вершины. Вычисление остаточной дисперсии состоит в одном вещественном умножении.
Вычисление ( , )при = 0 или при = требует 4 вещественных умножения и 2 вещественных сложения. При 1 ≤ ≤ − 1 эта операция комплексная. Сложностьреализации обработки нечётной вершины равна∆3 = ( − 1)(4 C +2 C ) + 2(4 R +2 R ) + R .144Итого, общее количество операций равно∆ = 4()+4 (2)+2(−1)(4 C +2 C )+4(4 R +2 R )+(2+2) R +2 R ,что соответствует утверждению леммы.При = 0 число = 2 не является чётным, и поэтому лемма 19 неприменима.Лемма 20 Количество операций для нахождения многочленов Шура порядка = 2 равно (2) = 20 R +15 R .Доказательство. Пусть заданы многочлены Шура порядка 1 в двух соседних вершинах нулевого уровня: (0 (), 0 ()) = (1, 0 ) и (1 (), 1 ()) = (1, 2 ).Рассмотрим работу алгоритма обхода дерева в этом случае.Интерполяция с = 1 значений (0 (), 0 ()) и (0 (), 0 ()) на 2 отсчётов не требует вычислений, так как это константы.Обработка нулевой вершины состоит из трёх пунктов.
В п. 1 требуетсявычислить значения двух многочленов первой степени в точках 0 = 1 и 1 =−1. Это требует 4 вещественных сложений.В п. 2 умножение матриц для = 0 и = 1 требует всего 8 умножений и 4сложения. В следущих двух ОДПФ на 2 отсчёта достаточно вычислить только̂︀0 и ̂︀0 , для чего нужно 2 сложения.
К ним добавляются два умножения на −1 .В п. 3 выполняются одно умножение, одно сложение и одно обращениевещественного положительного числа.При обработке нечётной вершины выполняется 4 умножения и 2 сложенияпри = 0 и при = 1. Кроме того, умножаются значения −1 .В итоге общее количество операций соответствует заключению леммы.Для расчёта значений () применим следующее вспомогательное утверждение, в котором = log2 .Лемма 21 ( [78]) Пусть последовательность положительных чисел (())∞=1удовлетворяет уравнению( + 1) = 2() + 2 0 + 2 1 + 2 + 3 + 4 (−1) .145Тогда() = 2−2 2 0 + 2−2 (21 − 0 ) + 2−1 (22 + 3 − 1 − 4 /3 + (1))−2 − 2 + 4 (−1) /3.Доказательство. Решение линейного разностного уравнения( + 1) = 2() + ()с произвольной входной последовательностью имеет вид() = 2 (1) +−1∑︁2−−1 ().=1Остаётся вычислить суммы−1∑︁2−−1 2 = 2−1=1−1∑︁−1∑︁ = 2−1=12=1−1∑︁−−1 2−−12= =−1∑︁( − 1),22−1 = 2−1 ( − 1),=1−1 ∑︁∑︁−−12=−1 ∑︁−1∑︁=1 =1=1=−1∑︁2−−1=1 =(2− − 1) = 2 − − 1,=1−1∑︁2−−1 = 2−1 − 1,=1−1∑︁=112−−1 (−1) = − (2−1 + (−1) ).3Подстановка слагаемых приводит к заключению леммы.При помощи леммы 21 можно рассчитать точную сложность быстрого алгоритма Шура, в котором выбран один из способов реализации БПФ.
Прилюбом способе реализации вещественное БПФ имеет половинную сложностьв главном члене по сравнению с комплексным, а двойная интерполяция имееттот же порядок: () ∼ (/2),() ∼ () + (/2).146Следствие 7 Пусть реализация комплексного БПФ имеет сложность() = ( R + R ) log2 + ().Тогда сложность реализации алгоритма Шура имеет порядок () = 2( R + R ) log22 + ( log2 ).Доказательство. Воспользуемся леммами 19 и 21. Главный член в суммеиз рекуррентного уравнения в лемме 194() + 4 (2) ∼ 4( () + (/2)) + 4() ∼ 8().имеет порядок log2 и множитель при нём0 = 8( R + R ).По лемме 21 главный член решения () меет порядок log22 и множитель0 /4, что и утверждается в следствии.Как обсуждалось в 2, поскольку БПФ используется для вычисления свертки, то порядок данных в промежуточных векторах не важен.
Таким образом,можно использовать для БПФ адресацию типа прореживания по частоте адля ОБПФ типа прореживания по времени. Это позволяет исключить операцию перестановки. Как обсуждалось в разделе 1.7, сумматоры следует учитывать только при использовании чисел с плавающей точкой. Для вычисленийс фиксированной точкой если количество операций умножения и сложенияотличается не сильно, то стоимостью операций сложения можно пренебречь,поскольку она качественно не влияет на общую стоимость вычислений.
Поскольку вычисление комплексного умножения при аппаратной реализации несводится к вещественным умножениям, следует раздельно учитывать сложность алгоритма в терминах комплексного умножения и сложения.Для аппаратной реализации БПФ более предпочтительным является алгоритм по основанию 4, имеющий на 6% больше операций умножения посравнению с алгоритмам по разделенному основанию, но регулярную структуру данных. Варианты распараллеливания этого алгоритма для однопортовойи двухпортовой оперативной памяти приведены в главе 2.147Вычислим количество комплексных операций при использовании комплексного БПФ по основанию 4. Количество комплексных умножений вБПФ составляет (3/8) log2 + ( log2 ), а сложений log2 + ( log2 ).Подставляя значения для и в формулу из следствия 7, получаем(3/2) log22 + ( log2 ) комплексных умножений и 4 log22 + ( log2 )комплексных сложений.
Эти значения соответствуют результатам [78].Также необходимо оценить количество операций доступа к адресуемой памяти и к памяти или блоку вычисления комплексных экспонент. Количествокомплексных экпонент в точности равно количеству умножений, для упрощения не будем рассматривать группировку бабочек для их переиспользования.В предположении сохранения промежуточных результатов вычислений внеадресуемых регистрах размером (1) для каждой стадии БПФ по основанию 4 требуется чтений и записей комплексных данных. В этом случаеполучаем 2 log22 + ( log2 ) чтений для алгоритма Шура и такое же количество записей комплексных данных. Для вещественного алгоритма Шураполучаем log22 + ( log2 ) операций доступа к адресуемой памяти каждого типа.Для работы алгоритма кроме БПФ требуется выполнять векторные операции сложения и умножения с общей сложностью ( log2 ).
Кроме того,требуется выполнять операции деления. Операции деления могут быть заменены на вычисление 1/ и умножение.4.4.2Общая оценка количества адресуемой памятиОценим минимальное необходимое количество ячеек памяти. Память требуется для хранения входных и выходных данных и промежуточных значений.Кроме того, память может потребоваться для хранения комплексных экспонент. Если для вычисления комплексных экспонент используется специализированный блок вычисления элементарных функций из главы 3, то память дляних не требуется.Реализация Аммара алгоритма Шура требует 6 комплексных либо вещественных ячеек данных в зависимости от типа данных алгоритма Шура безучета комплексных экспонент.148Лемма 22 Для реализации быстрого алгоритма Шура длины = 2 достаточно () = 4 ячеек памяти, вещественных или комплексных в зависимости от типа входных данных.Доказательство.
Бинарное дерево, представляющее быстрый алгоритмШура, обходится в лексикографическом порядке. Алгоритм рекуррентный,поэтому каждой вершине соответствует одна и та же задача, но с разнымичисловыми параметрами и разными размерностями. Входные данные (, )для вершины уровня имеют размерность 2 . Выходными данными являютсяДПФ от пары многочленов Шура (, ) размера 2 .Из корневой вершины дуги с индексами 0 и 1 ведут к вершинам бинарных поддеревьев, которые в силу рекуррентности алгоритма обрабатываютсянезависимо. Сначала обрабатывается поддерево с вершиной, в которую ведётдуга 0.
Исходными данными являются половина компоненет векторов и ,поэтому для расчёта требуется (/2) ячеек памяти. Результатом являютсявекторы и размерности = 2 , равные ДПФ от соответствующей парымногочленов Шура. Они занимают 2 ячеек.Обработка второго поддерева, в которое ведёт дуга 1, начинается с расчётаначальных данных в соответствии с п. 1 алгоритма. На этом шаге производятся ДПФ от исходных данных , длины . Они, как предполагается, выполняются на месте, без привлечения дополнительной памяти. Наконец, ДПФ отмногочленов Шура, полученных от обоих поддеревьев, умножаются покомпонентно.Таким образом, () = 2 + max{2, (/2)}, (1) = 4.Поэтому () = 4.Полученная оценка лучше на 33%, чем результат Аммара. Ее удается достигнуть на практике при использовании вычисления БПФ на месте.1494.5Оценка оптимального параллелизма и времени вычислений быстрого алгоритма Шура наустройстве с аппаратным ускорением БПФБудем рассматривать устройство с насыщением по вычислениям из расчета на одну операцию обращения к памяти, то есть обладающее достаточным набором вычислительных блоков, чтобы каждый такт запускать обработку одного прочитанного данного в конвейере.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
