Диссертация (Синтез алгоритмов обработки сигналов с ограничениями на минимальный параллелизм и объём памяти), страница 6

Различные реализации одного вентиля могут отличатьсяпо площади, задержке и энергопотреблению до нескольких раз.Существует несколько методов синтеза логических схем. Наиболее старый- ручная сборка логических схем из базовых вентилей библиотеки. На сегодня ручная сборка используется только для высокопроизводительных систем,выпускаемых массовыми сериями.Для малопотребляющих систем в основном используется синтез из высокоуровневых языков описания логических схем Verilog, VHDL. Логическаясхема при этом описывается на уровне соединения библиотечных блоков через интерфейсы, неадресуемых регистров, хранящих переменные, арифметических и логических функций, таких как умножение, сложение, операции булевой алгебры.

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

Кроме того, может выполняться автоматическая вставка иудаление регистров и перенос вычислений между стадиями конвейера. Этипреобразования позволяют выровнять длину критического пути и остальныхпутей в схеме и использовать наиболее экономичные типы вентилей. Из-забольшого пространства поиска программе синтеза обычно не удается найти29глобально оптимальное решение, поэтому результаты синтеза часто неустойчивы к небольшим изменениям в описании схемы.Синтез из Verilog, VHDL обладает некоторыми недостатками. Вычислительная модель алгоритма обычно написана на императивных языках высокого уровня, таких как C, C++, Matlab.

Языки Verilog, VHDL имеют значительно более низкий уровень абстракции, что требует серьезного переписываниямодели и последующей верификации. Верификация выполнятся с помощьюкрайне медленных логических симуляторов. Эти причины увеличивают трудоемкость разработки, часто приводят к ошибкам и препятствуют внесениюизменений в алгоритм после конверсии модели в Verilog, VHDL.Постепенно набирает популярность новый метод логического синтеза изязыков высокого уровня (High Level Synthesis). Общей идеей является автоматизация конверсии алгоритма в логическую схему, таким образом, чторазработчику в основном необходимо специфицировать интерфейсы взаимодействия между блоками и структуру памяти, а вставка регистров для хранения промежуточных результатов и конвейеризация вычислений выполняются автоматически.

Существуют промышленные средства логического синтеза из алгоритмических языков высокого уровня Matlab, C, C++, SystemC,Bluespec Verilog. Существуют также экспериментальные средства синтеза изязыка Hardware Join Java, Haskell и других. Некоторым недостатком высокоуровневого синтеза является еще меньшая устойчивость результатов синтеза кизменениям модели из-за невозможности найти глобально оптимальную аппаратную реализацию алгоритма.

Это часто приводит к несколько худшему качеству синтеза по сравнению с синтезом эквивалентной реализации из языковVerilog, VHDL. Однако выигрыш по времени позволяет либо получить приемлемый результат значительно быстрее, либо полнее исследовать пространстводопустимых реализаций и получить значительно лучшие результаты синтезаза счет алгоритмических оптимизаций. Синтез может выполняться как в одинэтап из языка высокого уровня в граф библиотечных вентилей, так и в дваэтапа с промежуточной трансляцией в Verilog, VHDL. В работе применялсядвустадийный синтез с использованием на последнем этапе Synopsys DesignCompiler Ultra, который может учесть реальную геометрию компонентов накристале, в отличие от текущих реализаций средств HLS.

Учет реальной гео30метрии кристалла для литографических процессов с геометрическими нормами 45 нм и менее является важным из-за большой площади межвентильныхсоединений и схем тактирования, влияние которых не учитывается при синтезе в граф вентилей [31].В работе для описания высокоуровневых моделей использовался языкSystemC [32], являющийся языком моделирования параллельных систем и аппаратуры на основе C++, предназначенным для моделирования системногоуровня и верификации. SystemC является стандартом IEEE и позволяет моделировать систему, включающую программные и аппаратные компоненты наразличных уровнях от абстрактных синхронных и асинхронных транзакций доточного моделирования аппаратуры. Преимуществом языка SystemC является отсутствие необходимости переписывания вычислительных моделей, еслиони написаны на C++, скорость и простота верификации, простота включенияв модель программных компонент моделируемой системы.Опыт показывает, что правильная иерархическая декомпозиция схемы, использование идиом, таких как разделение логических и арифметических выражений и максимизация графов арифметических вычислений могут до двухраз влиять на результирующую площадь и мощность схемы.

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

1.1.Мощность такого такого блока складывается из статической мощностинеотключаемых от питания компонент и мощности компонент с управляемымпитанием. К неотключаемым компонентам относятся память кода и памятьсостояния, остальные компоненты можно отключать на время простоя. К отключаемым компонентам относятся вычислительные устройства, память про31Рис. 1.1: Базовая архитектура блока.межуточных данных и постоянное запоминающее устройство.

Использованиев постоянно работающих блоках энергонезависимой памяти на сегодняшниймомент не оправдано из-за высоких накладных расходов на чтение и запись.1.5.1Оценка рассеиваемой мощности акселератора прификсированном размере задачиПредположим, что фиксированный алгоритм выполняется на вычислительном блоке, в котором могут быть задействованы параллельно процессоров.Требуется найти , при котором потребляемая мощность блока минимальна.Обрабатываемый алгоритм характеризуется следующими постоянными параметрами:∙ - вычислительная сложность алгоритма, выраженная в количестве элементарных операций в секунду. Элементарная операция запускается наисполнение каждый такт.

Обычно операции выполняются в конвейере,то есть время выполнения операции составляет несколько тактов.∙ - нераспараллеливаемая доля алгоритма, равная отношению длиныкритического пути к длине всего алгоритма.Вычислительный блок характеризуется следующими постоянными параметрами:32∙ 0 - количество вентилей в неотключаемой части,∙ 1 - количество вентилей в отключаемой части без вычислительныхкомпонент,ˆ2 - количество вентилей в последовательной реализации вычислитель∙ ных компонент блока,∙ - тактовая частота.Количество вентилей в вычислительных компонентах блока с учетом паˆ2 .раллелизма определяется как 2 = В этих обозначениях, используя формулы 1.1 и 1.3, мощность вычислительного блока на участке линейного роста от частоты можно оценить как = = 0 (0 + (1 + 2 )) = = 1 (1 + 2 ) = + = 0 (0 + (1 + 2 )) + 1 (1 + 2 )где 0 , 1 - постоянные коэффициенты, а = () ≤ 1 - скважность илиотношение времени вычислений к общему времени, включающему простой.При = 1 скважность равна = / по определению.

При > 1 функцию () заменяют на функцию ускорения от параллелизма () в соответствии с уравнением.()Функцию () можно описать с помощью закона Амдала [33], который ис() =пользуется в области параллельного программирования для оценки ускоренияпри фиксированном размере задачи.() =.1 + ( − 1)Вопрос оптимального выбора параллелизма для минимизации энергопотребления при моделировании ускорения с помощью закона Амдала рассматривался Ву и Ли [34] для многоядерных суперскалярных процессоров. В отличие от рассматриваемой нами задачи, процессоры работают на высокой частоте и при высоком напряжении питания, что позволяет не учитывать энергопотребление памяти.33Таким образом, = 0 0 + (0 / + 1 )ˆ2 + 1()(1.4)При этом мощность достигает минимума на максимальной частоте линейного масштабирования 0 :arg min = 0 ., ≤0Лемма 1 Мощность достигает минимума по при значении(︃ √︃)︃1 (1 − )0 = arg min = max 1,.ˆ2 (1.5)При этом минимальная мощность имеет значение(︂)︂√︁ˆ2 + 1 + 2 1 ˆ2 (1 − ) .

(1.6)min = 0 0 +(0 /0 +1 ) (1 − )Доказательство. Минимизируемую функцию мощности можно представить в виде () = + + −1с подходящими коэффициентами , , . Дифференцированием находим условие минимума − −2 = 0. Отсюда тождественными преобразованиями получаем заключение леммы.Важным показателем качества распараллеливания является максимальнаяэкономия энергии энергии (1),minгде (1) есть мощность блока при отсутствии распараллеливания.=Следствие 1 При полном распараллеливании (при = 0)(0 /0 + 1 )1,minˆ2 .= 0 0 + (0 /0 + 1 ) = 1+min34В инженерной практике работы по распараллеливанию алгоритма имеетсмысл проводить, только если экономия энергии ≥ 1.2.Таким образом, в рамках данной архитектуры для хорошо распараллеливаемых алгоритмов с доминированием памяти промежуточных результатовповышение параллелизма ведет к экономии энергии. Экономия достигаетсяза счет уменьшения статической мощности памяти промежуточных данных спомощью отключения от питания.1.5.2Асимптотическая скорость роста мощности при ростеразмера задачиКроме задачи оценки оптимального параллелизма, рассмотрим задачуоценки роста мощности при увеличении размера задачи.

Хотя обычно размерзадачи в алгоритмах для низкоэнергетических устройств известен заранее, нов некоторых случаях его можно варьировать. Например, размер фильтров, количество оцениваемых параметров, разрешение изображений и т.п.Функция мощности зависит от параллелизма и размера задачи : (, ) = 0 0 () + ()(0 / + 1 )ˆ2 + 1 (),(, )где величины 0 (), 1 () зависят от размера памяти, который обычно растетˆ2 не зависит от , поскольку алгоритмс ростом размера задачи. Величина вычислений не меняется.Для оценки (, ) используем закон Густафсона-Барсиса [35], который используется в области параллельного программирования для оценок при ростеразмера задачи:(, ) = (1 − ) + .Закон Густафсона-Барсиса, предполагает, что непараллелизуемая часть задачине растет с ростом размерности, что часто встречается при независимостипараллельных подзадач друг от друга.Лемма 2 Пусть размер памяти 0 (), 1 () и сложность алгоритма ()растут линейно по размеру задачи.

Тогда при отсутствии распараллеливания35мощность (1, ) = (2 ), а минимальная мощность min () = () при → ∞.Доказательство. Подставим линейные функции и закон ГустафсонаБарсиса:ˆ 2 + 1 .(1.7)(1 − ) + При отсутствии распараллеливавния = 1. Очевидно, что в этом случае (, ) = 0 0 + (0 / + 1 )величина (1, ) имеет порядок 2 при → ∞.Если коэффициент распараллеливания = () пропорционален , то ((), ) = ().1.6Выбор оптимального типа памятиТакже может являться энергетически выгодной минимизация памяти состояний за счет перерасчёта промежуточных данных, в теории компиляторовназываемая рематериализацией, и уменьшение памяти кода за счет специализации блока под класс алгоритмов.Таблица 1.2: Относительный размер ячейки, включая накладные расходы.Тип памятиРазмерДинамическая eDRAM (1T) 1rw1Статическая 6T-SRAM 1rw3Регистровая 8T-SRAM 1r1w6Другая важная оптимизация - выбор энергоэффективного типа памяти взависимости от назначения.

Для небольших энергоэффективных устройствмогут использоваться только типы памяти, сформированные на кристалле спомощью того же технологического процесса. Библиотечные компоненты памяти организованы в прямоугольный массив ячеек. Другие виды организациипамяти, такие как очереди, при большом размере могут быть эффективно реализованы только на основе адресуемой памяти. Внешняя память не являетсяэнергоэффективной из-за потерь мощности на внешнем интерфейсе. Память36по типу может быть постоянной, перезаписываемой и оперативной.