Диссертация (Синтез алгоритмов обработки сигналов с ограничениями на минимальный параллелизм и объём памяти), страница 5
Описание файла
Файл "Диссертация" внутри архива находится в папке "Синтез алгоритмов обработки сигналов с ограничениями на минимальный параллелизм и объём памяти". PDF-файл из архива "Синтез алгоритмов обработки сигналов с ограничениями на минимальный параллелизм и объём памяти", который расположен в категории "". Всё это находится в предмете "физико-математические науки" из Аспирантура и докторантура, которые можно найти в файловом архиве СПбГУ. Не смотря на прямую связь этого архива с СПбГУ, его также можно найти и в других разделах. , а ещё этот архив представляет собой кандидатскую диссертацию, поэтому ещё представлен в разделе всех диссертаций на соискание учёной степени кандидата физико-математических наук.
Просмотр PDF-файла онлайн
Текст 5 страницы из PDF
Для упрощения блока декодирования инструкций большинство специализированныхпроцессоров декодируют инструкции по одной в порядке выборки из памяти.Инструкции декодируются в темпе одной инструкции за такт синхронизации.Современные процессоры выполняют инструкции в конвейере. То есть однаинструкция проходит несколько стадий обработки: выборка из памяти, декодирование, чтение данных из регистров или памяти, вычисление результата,вычисление адреса следующей инструкции, запись результата в регистры илипамять.
Если стадия выполнения инструкции занимает несколько тактов син-21хронизации, то результаты последовательных инструкций могут переупорядочиваться, в случае, если они независимы по данным.Большинство алгоритмов, используемых в обработке сигналов и адаптивном управлении, состоят в применении небольшого вычислительного ядра кзначительному объему данных. В программном коде это отображается в циклы с небольшим телом и значительным числом итераций. При выборе расширения набора инструкций должны учитываться накладные расходы на декодирование инструкции и организацию циклов, длительность исполнения инструкции и возможность их переупорядочивания. Эти накладные расходы могут быть сравнимы с затратами на сами вычисления.
В случае значительныхнакладных расходов для эффективной реализации алгоритма вычислительныйблок необходимо разрабатывать не как расширение набора инструкций, а какакселератор вычисления библиотечных функций, поскольку в этом случае онне взаимодействует с конвейером процессора, и накладные расходы сводятсяк минимуму.Реализация полупроводниковых схем может выполняться на языках логического синтеза Verilog, VHDL или с использованием средств высокоуровнего логического синтеза из языков C, C++, SystemC, System Verilog, BlueSpecSystem Verilog, Haskell.
Использование высокоуровневого логического синтеза в разы сокращает время разработки и верификации логических схем. Этотспособ был использован в данной работе.Существует два основных подхода к разработке энергоэффективных схемс точки зрения выбора оптимального параллелизма вычислений и тактовойчастоты:1. “равномерная работа”, когда производительность и тактовая частотаподбираются в соответствии с вычислительной нагрузкой;2.
“рывок ко сну”, когда устройство функционирует с максимальной эффективной частотой и по окончании работы засыпает с отключениемпитания от части блоков.Критическим отличием малопотребляющих литографических процессов смалыми геометрическими нормами (45 нм и менее) от более старых является22доминирование потерь мощности из-за токов утечки над активной мощностью, связанной с переключением логических состояний схемы при работе внизкоэнергетических режимах с пониженной тактовой частотой.
Токи утечки фактически пропорциональны площади подключенной к питанию схемына кристале. Подход “рывок ко сну” может являться более предпочтительнымдля таких схем по нескольким причинам:1. площадь блоков памяти, как правило, доминирует над площадью вычислительных схем, при этом размер памяти является характеристикойалгоритма и слабо зависит от скорости вычислений;2. на время простоя возможно полное отключение от питания блоков включая часть памяти для экономии энергии;3. не требуется динамическое управление тактовой частотой в низкоэнергетических режимах, что упрощает процесс разработки;4. устройство имеет запас вычислительных ресурсов, что увеличивает возможности модернизации и переиспользования без изменения архитектуры.Базовыми алгоритмическими блоками для алгоритмов цифровой обработки сигналов являются сумматоры, умножители и запоминающие устройства.Для сумматоров и умножителей основным способом уменьшения энергопотребления является уменьшение количества используемых вентилей.
Для реализации сумматоров используется троичная арифметика и древовидная структура вычислений [24]. Это позволяет избежать длинных цепочек переносов,что приводит к выравниванию путей и уменьшению задержки на критическомпути. Для реализации умножителей используется комбинация методов Уоллеса [25] и Бута [26]. Умножение рассматривается как суммирование результатовпоразрядных умножений в троичной арифметике. Это позволяет эффективно комбинировать сложение и умножение в графах зависимых вычислений,вставляя полный сумматор с переносом только перед записью значений в регистр или в память.
Для реализации полного сумматора обычно используютсясхемы с цепным переносом, схема ускоренного переноса [27], и параллельный префиксный метод [28]. Эти методы отличаются по соотношению коли23чества вентилей и длины критического пути. Средства логического синтезавыполняют автоматические оптимизации графов вычислений из сумматорови умножителей для достижения оптимальной площади схемы при заданнойцелевой частоте, которое достигается при выравнивании длины путей в схеме. Ручные оптимизации на уровне базовых операций как правило приводят кхудшим результатам по энергопотреблению по сравнению с автоматическимиоптимизациями в средствах логического синтеза.На следующем уровне располагаются параллельные векторные операциинад малыми векторами, векторное сложение, умножение, операции над кватернионами, линейная фильтрация.
Энергоэффективная реализация этих операций не представляет сложностей с алгоритмической точки зрения, однако требует выбора и учета специфики архитектуры памяти, для обеспечениянеобходимого уровня параллелизма без дополнительных энергозатрат на однуоперацию по сравнению с последовательной реализацией.1.1Общая модель энергопотребления тактируемых логических схемРассмотрим факторы, влияющие на энергоэффективность вычислительныхблоков при построении малопотребляющих полупроводниковых схем, специализированных для группы алгоритмов. Будем учитывать и другие два дополнительных критерия - скорость разработки и удобство композиции вычислительных блоков для реализации сложных алгоритмов.К физическим факторам относятся пороговое напряжение, токи утечки,паразитная емкость.
Другими факторами являются архитектура, тип и размерпамяти, точность промежуточных вычислений, методы логического синтеза.Проанализируем взаимосвязь этих факторов и их влияние на энергопотребление.Поскольку рассматриваемые схемы работают непрерывно, то для характеризации их энергопотребления используется мощность. Мощность полупроводниковой схемы складывается из активной и статической рассеиваемой24мощности.
= + Активная мощность обусловлена переключением состояния полупроводниковой схемы и связана с интенсивностью вычислений. Статическая мощностьне зависит от вычислений, а только от количества аппаратуры, подключеннойк питанию.Сложные вычислительные блоки разрабатываются в виде тактируемых полупроводниковых схем. Схема состоит из регистров, хранящих состояние, икомбинационных логических схем, описывающих переход между состояниями. Переход между состояниями происходит по стробу тактирующего сигнала.Такая схема может быть представлена как конечный автомат. = (, , Σ); Σ ⊂ ⊂ {0, 1} ; : ↦→ Здесь - множество допустимых состояний, Σ - множество начальных состояний, - функция перехода.
Функция перехода в полупроводниковой схемереализуется как направленный ациклический граф элементарных библиотечных функций или вентилей. Вентили могут реализовывать такие функции какAND, OR, NOR, XOR, мультиплексор, селектор и т.д. На более низком уровневентили состоят из транзисторов. Состояние системы хранится в регистрах.Такой уровень детализации описания логических схем называется уровнемрегистровых передач (Register Transfer Level).1.2Мощность КМОП устройствДля оценки мощности будем опираться на базовую модель, описанную вовторой главе [29].Для одного вентиля мощность определяется как = + .Здесь - активная мощность, зависящая от данных, - статическая мощность, не зависящая от данных. = + , = 25Здесь - динамическая мощность, - потери мощности от токов утечки, - потери мощности в результате короткого замыкания при переключении транзисторов.
≃ 2 (1.1)Здесь - паразитная емкость, - напряжение питания, - тактовая частота, - коэффициент частоты переключения, показывающий среднюю вероятность открытия вентилей на каждом такте. Для сигнала строба = 1, длядругих в среднем 0.1. Максимальная тактовая частота работы схемы при данном напряжении питания связана с задержкой на критическом пути, то естьцепочке вентилей, имеющей самую большую задержку переключения.∑︁ ≤ 1/ , =Задержка на одном вентиле также связана с напряжением по следующейформуле: ≃ , >> .(1.2)2( − )Здесь - емкость нагрузки, которая состоит из перезаряжаемых входом( ) ∝емкостей затворов транзисторов и паразитных емкостей проводов. = Здесь - емкость затвора транзистора, - пороговое напряжение, удельная емкость оксида затвора, , - ширина и длина затвора транзистора.Из-за дефектов изготовления цифровые схемы работают неустойчиво принапряжениях, близких к ; существует минимальное напряжение 0 >> ,обеспечивающее устойчивую работу схемы.
При этом напряжении схема может работать на максимальной тактовой частоте 0 = 1/ (0 ). Схема можетработать и при меньшей тактовой частоте, если скорость ее работы достаточна для решения задачи. На интервале частот ∈ (0, 0 ] рост мощности отчастоты линеен. При больших тактовых частотах ∝1∝ , > 0 .Таким образом, объединяя эти две оценки, получаем оценку{︃, ≤ 0 ( ) ∝ 3 , > 026Потери мощности в результате короткого замыкания при переключениитранзисторов определяются по следующей формуле: ≃ , = + 2Здесь , - время роста и спада сигнала соответственно. Для логических схем мал и может не учитываться.
Мы не будем его учитывать вдальнейших расчётах.Статическая мощность обусловлена в основном токами утечки, протекающими через вентили в закрытом состоянии и определяется для одного вентиляпри комнатной температуре как ≃ , ∝ /(1.3)Таким образом, при уменьшении геометрических норм токи утечки растут.Наилучшая энергоэффективность достигается при = 0 . Пороговое напряжение увеличивается с увеличением длины затвора , что уменьшает токутечки.В библиотеке компонентов для одной технологии могут быть вентили сразличной геометрией и различным пороговым напряжением . Увеличениепорогового напряжения приводит к уменьшению быстродействия.1.3Методы оптимизации энергопотребленияОптимизация энергопотребления может происходить на различных уровнях. Шерази [30] дает обзор таких оптимизаций.
Оптимизации перечислены втаблице 1.1.Транзисторный и вентильный уровни рассмотрены во множестве работ идостаточно хорошо изучены. Верхние уровни и их взаимодействие друг с другом рассматриваются редко. В работе мы будем в основном рассматривать системный и архитектурный уровни оптимизации. Основным видом системнойоптимизации является алгоритмическая оптимизация. Легко видеть, что сложность алгоритма влияет на его энергопотребление. Однако сложность определяется в рамках некоторой модели вычислений, которая, в свою очередь,определяется архитектурой полупроводникового устройства и его крупных27Таблица 1.1: Методы оптимизации энергопотребления.УровеньОптимизацияТранзисторныйУменьшение напряжения питанияНесколько напряжений питанияМасштабирование транзисторовСдвиг потенциала подложкиВентильныйНесколько сигналов тактированияОтключение тактированияУменьшение переходных процессовСтекирование транзисторовВентили с различными порговыми напряжениямиМикроархитектурный Дупликация блоковКонвейеризацияРаспределение ресурсовОптимизация представления данныхАрифметические оптимизацииОтключение питанияМультиплексирование ресурсов по времениСистемныйДинамическое управление частотойи напряжением питанияИспользование параллельных алгоритмов28функциональных блоков.
Наибольшее влияние на энергопотребление оказывает реализация сложных вычислительных алгоритмов. К ним часто относятсяалгоритмы цифровой обработки сигналов.Краткое описание методов оптимизации энергопотребления приведено вприложении A.1.4Методы логического синтезаЛогическая схема синтезируется из библиотечных элементов, которые являются частью технологического процесса. Библиотека обычно содержит различные типы вентилей и различные реализации вентиля в зависимости оттребуемой задержки.