Диссертация (1150736), страница 26
Текст из файла (страница 26)
Уменьшение статической мощности от использования этой архитектуры составляет 27%. Также мы можем заключить,что быстрый алгоритм Шура достаточно плохо поддается распараллеливаниюна конвейерном вычислительном блоке. Основными факторами, препятствующими распараллеливанию, являются длинный критический путь алгоритма идлинный конвейер блока.163Кроме того, оценка мощности и параллелизма с помощью закона Амдалаобеспечивает одинаковые качественные результаты по сравнению со значительно более трудоемкой оценкой на основе анализа алгоритма.4.6Гибридный алгоритм фильтрации с малой задержкойДля решения задачи фильтрации требуется вычислить линейную сверткусигнала и коэффициентов фильтра ℎ:(ℎ * )() =−1∑︁ℎ()( − )=0Импульсная характеристика ℎ разбивается на блоки неравной длины ℎ =[ℎ , .
. . , ℎ+1 ], где 0 = 0, < +1 , = . Обозначим = +1 − длинублока с номером .(ℎ * )() =−1 ∑︁ −1∑︁ℎ ()( − − ) ==0 =0−1∑︁(ℎ * )( − )=0Обозначим свертку () = (ℎ * )( − ) =∑︀ −1=0ℎ ()( − − ).Свертка с первым блоком 0 реализуется по определению.Значения , 0 < < вычисляются поблочно при помощи ДПФ длины 2 .Обозначим задержку блока = − . - расстояние в отсчетах междупоследним значением (), необходимым для вычисления , и моментом использования результата вычислений. Таким образом, / - это максимальноевремя, доступное для вычисления .Рассмотрим разбиение на блоки длины{}−1= {2, , , 2, 2, 4, 4, ..}0(4.3)Лемма 27 Разбиение (4.3) обеспечивает ≥ , > 0.
То есть время на вычисление свертки не меньше времени на сбор данных.Доказательство. Для четных = 2, 2 = 2 + 2−1 − 2 − 1 = 2 ≥ 2−1 ; длянечетных = 2 − 1, 2−1 = 2 − 2 − 1 = 2−1 .164Таким образом, все блочные свертки могут выполняться одновременно иобеспечивается равномерная загрузка процессора.Мы можем оценить максимальные вычислительные затраты алгоритма на∑︀один отсчет = −1=0 / , где - вычислительная сложность нахождениясвертки с одним блоком.Лемма 28 Сложность алгоритма при разбиении (4.3) порядка 4 + 2.5 log22 на отсчет.Доказательство. Для нулевого блока 0 / = 4. Следующие блоки разобьемна пары, поскольку блоки в паре имеют одинаковый размер, сложение можно выполнять в частотной области.
Пусть 2 ℎ вычислен заранее, тогда длявычисления сверток пары блоков нам требуется одно прямое и одно обратноеДПФ.Поэтому(2+1 + 2+2 )/(2 ) = 2(2+1 )/(2 ) = 5( + 1) + (1).Введем обозначение = 2 log2 − 2 log2 − 1.Просуммировав члены, получаем:(−1)/2−1 = 4 + 5∑︁=05( + (1)) = 4 + 2 + () = 4 + 2.5 log22 + (log ).8Поскольку сигнал воспроизводится через динамик с небольшой задержкой, то можно положить ℎ0 ≡ 0 и исключить линейное слагаемое из оценкисложности.Для вычислений может переиспользоваться блок вычисления БПФ, используемый для вычисления оптимального фильтра.165ЗаключениеЭнергоэффективность является ключевым параметром современных беспроводных малопотребляющих устройств.
При переходе к технологиям производства полупроводниковых схем с малыми нормами (45 нм и менее) определяющее влияние на энергопотребление начинают оказывать токи утечки,пропорциональные площади компонент, подключенных к питанию. В работе предлагается эффективный метод оценки и выбора оптимального параллелизма аппаратной вычислительной схемы на основе характеристик вычислительного алгоритма.
Решается задача разработки энергоэффективных вычислительных устройств для широкого класса алгоритмов цифровой обработкисигналов на основе БПФ. За основу взят универсальный векторный вычислительный блок для расчёта БПФ и блок вычисления элементарных функций.Также продемонстрированы улучшения энергоэффективности для каждой изкомпонент за счет уменьшения числа вычислительных операций и использования более энергоэффективной памяти по сравнению с опубликованными результатами. Продемонстрировано применение данного блока для более сложного алгоритма сверхбыстрой факторизации тёплицевых матриц и приведенанализ энергоэффективности и оптимального параллелизма.Основные результаты работы заключаются в следующем.1. Разработана модель энергопотребления для малопотребляющей цифровой схемы, выполняющей известный вычислительный алгоритм.
Модельвключает динамические и статические потери энергии и возможностьотключения во время простоя. Решена задача выбора оптимального параллелизма в данной модели.2. Задача минимизации энергопотребления при расчёте значений стандартных функций сведена к минимизации длины таблиц. Разработаны но166вые методы аппроксимации квазисплайнами с неравномерным табулированием, удобные для аппаратной реализации, при помощи которыхудалось сократить длины таблиц всех основных стандартных функцийпо сравнению с известными аналогами, что привело к существенномууменьшению энергопотребеления и увеличению скорости аппаратныхвычислительных блоков.3.
Доказана теорема о размещении данных БПФ в многобанковой памятипри вычислении по произвольным смешанным основаниям, гарантирующая гомогенность графа синхронного потока данных для вычислений,что обеспечивает максимальную скорость вычислений при заданном параллелизме и нулевой размер буферной памяти. Получены явные формулы БПФ в виде произведений Кронекера по стадиям произвольныхпорядков.4. Доказана теорема о самосортирующейся модификации БПФ в многобанковой памяти по смешанным основаниям, а также аналогичная теоремадля вычислительного устройства с однопортовой памятью.5. Для быстрого алгоритма Шура найден минимальный объём памяти, вычислена длина критического пути и проведена оценка оптимального параллелизма.Предложенные методы и вычислительные алгоритмы были апробированыпри практической разработке малопотребляющих полупроводниковых схем смалыми геометрическими нормами.167Список иллюстраций1.1 Базовая архитектура блока.
. . . . . . . . . . . . . . . . . . . . .322.1 Архитектура блока интерполяции функций . . . . . . . . . . . .753.1 Архитектура блока потокового вычисления БПФ с 1r1w памятью. 803.2 Архитектурный шаблон блока потокового вычисления БПФ. . .833.3 Архитектурный шаблон блока потокового вычисления БПФ c1r1w памятью. . .
. . . . . . . . . . . . . . . . . . . . . . . . . .973.4 Архитектура блока потокового вычисления БПФ с 1rw памятью. 1083.5 Архитектурный шаблон блока потокового вычисления БПФ c1rw памятью. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1084.1 Модель эхоподавления . . . . . . . . . . . . . . . . . . .
. . . . . 1194.2 Граф потока данных быстрого алгоритма Шура для реализациина реконфигурируемом вычислительном блоке. . . . . . . . . . . 153168Список таблиц1.1 Методы оптимизации энергопотребления. . . . . . . . . . . . . .281.2 Относительный размер ячейки, включая накладные расходы. . .361.3 Относительный размер и задержка базовых вычислительныхблоков. . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .391.4 Относительный размер и задержка базовых вычислительныхблоков. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .401.5 Относительный размер памяти и вычислительных блоков. . . .431.6 Сравнение процессоров ARM, отличающихсяпо наличию MMU.502.1 Относительный размер блока при задержке 5 нс . . . . . .
. . .762.2 Относительный период максимальной тактовой частоты . . . .772.3 Относительный размер блока по сравнению с вещественнымумножителем . . . . . . . . . . . . . . . . . . . . . . . . . . . . .774.1 Псевдокод быстрого алгоритма Шура. . . . . . . . . . . . . . . . 1514.2 Количество операций чтения в быстром алгоритме Шура. . .
. 1544.3 Количество операций чтения на критическом пути быстрого алгоритма Шура. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1564.4 Размер вычислительной части блока в вещественных умножителях FP32 w/o denorm . . . . . . . . . . . . . . . . . . . . . . . 1604.5 Зависимость мощности от параллелизма при использовании регистровой памяти. . . . .
. . . . . . . . . . . . . . . . . . . . . . 163C.1 Псевдокод метода с активным множеством ограничений. . . . . 200C.2 Псевдокод метода ветвей и границ для целочисленного линейного программирования . . . . . . . . . . . . . . . . . . . . . . . 202169Литература1. Volder J. E. The CORDIC Trigonometric Computing Technique // ElectronicComputers, IRE Transactions on. 1959. Sept. Vol.
EC-8, no. 3. P. 330–334.2. Das Sarma D., Matula D. W. Faithful bipartite ROM reciprocal tables // Computer Arithmetic, 1995., Proceedings of the 12th Symposium on / IEEE. 1995.P. 17–28.3. Strollo A. G. M., Caro D. D., Petra N. Elementary Functions Hardware Implementation Using Constrained Piecewise-Polynomial Approximations // IEEETransactions on Computers.
Los Alamitos, CA, USA, 2011. Vol. 60, no. 3.P. 418–432.4. Johnson S. G., Frigo M. A Modified Split-Radix FFT With Fewer Arithmetic Operations. // IEEE Transactions on Signal Processing.2007.Vol. 55, no. 1. P. 111–119. URL: "http://dblp.uni-trier.de/db/journals/tsp/tsp55.html#JohnsonF07".5. Sorensen H., Heideman M., Burrus C. On computing the split-radix FFT //Acoustics, Speech and Signal Processing, IEEE Transactions on. 1986.
Feb.Vol. 34, no. 1. P. 152–156.6. Johnson L. Conflict free memory addressing for dedicated FFT hardware // Circuits and Systems II: Analog and Digital Signal Processing, IEEE Transactionson. 1992. Vol. 39, no. 5. P. 312–316.7. Jo B. G., Sunwoo M. H. New continuous-flow mixed-radix (CFMR) FFT processor using novel in-place strategy // Circuits and Systems I: Regular Papers,IEEE Transactions on.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
