Диссертация (1150736), страница 24
Текст из файла (страница 24)
Это соответствует современнойинженерной практике разработки цифровых полупроводниковых устройств смалыми литографическими нормами.Тогда производительность такого устройства определяется количествомчтений в алгоритме и длиной конвейера, учитывать арифметические операции не требуется. Операции записи также не требуется учитывать, если однаоперация чтения порождает не более одной операции записи, в противномслучае следует учитывать операции записи.Будем рассматривать алгоритм Шура в терминах векторных операций надкомплексными данными, для вещественных данных - над парами вещественных чисел.
Псевдокод для реализации рассматриваемого алгоритма приведенв таблице 4.1.Здесь ̂︀ () = −1 ( ()−(0)), ̂︀ () = −1 то есть мы отрезаем (0) ≡ 1и (0) ≡ 0. - преобразование Фурье длины , - обратное преобразование Фурье, · - поэлементное умножение. Обозначим , () = ˜, (). ()+ означает часть обобщенного полинома с неотрицательными степенями.Мы не будем использовать двойную интерполяцию, вычисляя ее по определению при помощи БПФ. Это приводит к увеличению арифметическойсложности на 25%, однако позволяет использовать эффективную реализациюБПФ и векторных опреаций на основе реконфигурируемых вычислительныхблоков, что позволяет сократить общую сложность блока в 2 раза и болеепо сравнению с блоком на основе микропроцессора за счет уменьшения памяти программ, декодера инструкций и накладных расходов на организациюциклов.150Таблица 4.1: Псевдокод быстрого алгоритма Шура.(0,−1 (), 0,−1 ()) = ℎ(̂︀0 (), ̂︀0 (), )>1(0,/2−1 (), 0,/2−1 ()) = ℎ(̂︀0 (), ̂︀0 (), /2) = ̂︀0 (), = ̂︀0 () = ˜0,/2−1 () · + 0,/2−1 () · = ˜0,/2−1 () · + 0,/2−1 () · () = , () = (/2,−1 (), /2,−1 ()) = ℎ(( −/2 ())+ , ( −/2 ())+ , /2) 0,−1 () = 0,/2−1 () · /2,−1 () + 0,/2−1 () · ˜/2,−1 () 0,−1 () = 0,/2−1 () · /2,−1 () + 0,/2−1 () · ˜/2,−1 ()0,−1 () = 0,−1 ()0,−1 () = 0,−1 () = −̂︀(0)0,0 () = 1/(1 − ||2 )0,0 () = ¯ /(1 − ||2 )151При этом одна векторная операция соответствует одной инструкции архитектурного шаблона акселератора (определение 12).
Элементарными операциями будут: стадия комплексного БПФ/ОБПФ по основанию 4, стадиякомплексного БПФ/ОБПФ по основанию 2, последняя стадия вещественного БПФ по основанию 2, последняя стадия вещественного БПФ по основанию 4, первая стадия вещественного ОБПФ по основанию 2, первая стадиявещественного ОБПФ по основанию 4, листовая стадия алгоритма Шура, векторное комплексное умножение, векторное комплексное сложение, векторноевещественное умножение, векторное вещественное сложение.Количество операций чтения для комплексных операций равно суммарнойдлине векторов входных данных, а для вещественных - половине длины.Наиболее сложной по вычислительным операциям является стадия БПФпо основанию 4.
Из расчета на одно комплексное данное для ее выполнения требуется 1 комплексный умножитель, 2 комплексных сумматора и блокаппроксимации комплексных экспонент. Блоки комплексных вычислений могут быть использованы для вещественных вычислений. Блок аппроксимациикомплексных экспонент может быть использован для деления путем аппроксимации 1/.Оценим энергопотребление устройства по методу, предложенному в главе 1.
Для этого нам требуется оценить длину критического пути в тактах ивремя работы алгоритма в тактах. То есть требуется оценить количество чтений во всем алгоритме и на критическом пути при описанном выше выбореэлементарных операций.4.5.1Оценка количества комплексных чтений в вещественном алгоритме ШураРассмотрим отсортированный по глубине граф потока данных, соответствующий псевдокоду в таблице 4.1 с дополнительнми ограничениями. Наодной глубине могут находиться только однотипные операции и максимальная ширина векторных операций комплексного чтения на одной глубине непревосходит , при длине входных векторов .Граф потока данных изображен на рисунке 4.2.152Schurn/2FnFnFnFn*n*n*n*n+n+nWnWnSchurn/2*nFnFn*n*n+n+nWnWn*nРис.
4.2: Граф потока данных быстрого алгоритма Шура для реализации нареконфигурируемом вычислительном блоке.153Пусть = 2 . Количество стадий для вещественного БПФ по основанию4 и длины = ⌈log4 ⌉ = ⌈/2⌉.Результаты подсчета операций чтения для обработки в одном узле c длинойвещественных входных данных = 2 приведены в таблице 4.2.Таблица 4.2: Количество операций чтения в быстром алгоритме Шура.ОперацияДлинаК-воСтадиина узелЧтенийна стадиюВещ. БПФ6 ⌈log4 ⌉/2Вещ. ОБПФ4 ⌈log4 ⌉/2Ком.
умножение81/2Ком. сложение41/2/2211Рекурс. вызовЛист. оп.1 (/2)11Докажем вспомогательное утверждение.Лемма 23 Пусть (2 ), ∈ Z+ описывается следующей рекуррентной формулой(1) = (2 ) = 2 + 2 + + + 2(2−1 ).Тогда(2 ) = 2−1 2 + ( + 2)2−1 + ( + 2 + 2)2 − − 2.Доказательство. Сгруппируем слагаемые и просуммируем получившиеся ряды.(2 ) = 2 +∑︁2− (2 + 2 + + )=1(︃= 2 +∑︁)︃ + + 2− + 2−=1= 2 + ( + + 2)2−1 + (2+1 − − 2) + 2−1154= 2−1 2 + ( + 2)2−1 + ( + 2 + 2)2 − − 2.Лемма 24 Количество операций чтения 1 (2 ) в реализации быстрого алгоритма Шура удовлетворяет неравенстам 1 (2 )− ≤ 1 (2 ) ≤ 1 (2 )+ , где1 (2 )− = 1.25 · 2 2 + 7.25 · 2 ,1 (2 )+ = 1.25 · 2 2 + 9.75 · 2 .Доказательство.
С помощью таблицы 4.2 составим рекуррентную формулудля количества операций чтения в реализации быстрого алгоритма Шура.1 (1) = 11 (2 ) = 10⌈/2⌉2−1 + 12 · 2−1 + 21 (2−1 ).Используем оценку/2 ≤ ⌈/2⌉ ≤ /2 + 0.5,∈N(4.1)1 (1)− = 1 (1) = 1 (1)+ = 11 (2 )− = 2.5 · 2 + 6 · 2 + 21− (2−1 )1 (2 )+ = 2.5 · 2 + 8.5 · 2 + 21+ (2−1 ).Тогда по лемме 231 (2 )− = 2.5 · 2−1 2 + (2.5 + 12)2−1 + 2 = 1.25 · 2 2 + 7.25 · 21 (2 )+ = 2.5 · 2−1 2 + (2.5 + 17)2−1 + 2 = 1.25 · 2 2 + 9.75 · 2 .4.5.2Оценка длины критического путиАлгоритм не может быть распараллелен более, чем длина его критическогопути.
Она является ограничивающим фактором параллелизма, поскольку всеоперации на критическом пути выполняются последовательно.155Результаты подсчета операций чтения для обработки в одном узле c длинойвещественных входных данных = 2 приведены в таблице 4.3. Таблица 4.3отличается от таблицы 4.2 поскольку все операции, кроме сложения, выполняются раздельно над каждым генератором или многочленом Шура и могутбыть распараллелены в два раза.Таблица 4.3: Количество операций чтения на критическом пути быстрогоалгоритма Шура.ОперацияДлинаК-воСтадии Ширинана узелВещ. БПФ2⌈log4 ⌉2Вещ.
ОБПФ2⌈log4 ⌉Ком. умножение212Ком. сложение212 (/2)11Рекурс. вызов/2Лист. оп.11Аналогично предыдущему с помощью таблицы 4.3 составим рекуррентную формулу для количества операций чтения на критическом пути в реализации быстрого алгоритма Шура.Лемма 25 Количество операций чтения (2 ) на критическом путив реализации быстрого алгоритма Шура удовлетворяет неравенстам (2 )− ≤ (2 ) ≤ (2 )+ , где (2 )− = 13 · 2 − 2 − 4, (2 )+ = 17 · 2 − 2 − 4.Доказательство.
Используем оценку 4.1 для вычисления верхней и нижнейоценок (2 ). (2 )− ≤ (2 ) ≤ (2 )+ (1)− = (1) = (1)+ = 1− (2 )− = 2 + 4 + 2(2−1 )156+ (2 )+ = 2 + 6 + 2(2−1 ).Тогда по лемме 23 (2 )− = (1 + 4 + 8)2 − 3 − 6 = 13 · 2 − 2 − 4 (2 )+ = (1 + 4 + 12)2 − 3 − 6 = 17 · 2 − 2 − 4.Таким образом, мы можем заключить, что максимальное ускорение от распараллеливания алгоритма Шура - не более log22 раз.Сделаем дополнительное предположение об отсутствии переупорядочивания скалярных операций между векторными операциями, что следует из определения 12 инструкции архитектурного шаблона.При этом предположении время исполнения равно , где - длинаконвейера, если количество вычислительных блоков больше или равно максимальному параллелизму самой широкой векторной операции.
Самые широкиевекторные операции находятся на верхнем уровне рекурсии алгоритма Шура.При выполнении одного чтения за такт длина конвейера не может бытьменьше размера бабочки БПФ, поскольку для вычисления результата бабочкитребуется считывание всех входных данных.4.5.3Оценка времени вычислений быстрого алгоритма Шура для вещественных данных на 2 конвейерных процессорахРассмотрим 2 вычислительных блоков, которые могут исполнять за одинтакт 2 операции комплексного сложения, одну операцию комплексного умножения и две операции вычисления вещественнозначных элементарных функций, одну операцию записи и одну операцию чтения комплексных данных.Как и до этого, сделаем предположение об отсутствии переупорядочиванияскалярных операций между векторными операциями.В соответствии со столбцом "Ширина"таблицы 4.3 Данное количество блоков соответствует максимальному распараллеливанию для алгоритма Шура157длины 2−1 для вещественных данных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
