Современные информационные технологии/1. Компьютерная  инженерия

 

М.н.с. А.В. Бовкун

НИИ многопроцессорных вычислительных систем имени академика

 А.В. Каляева Южного федерального университета, Таганрог, Россия

Канд. техн. наук А.К. Мельников,

ЗАО «ИнформИнвестГрупп», Москва, Россия

Канд. техн. наук Дордопуло А.И.

Южный научный центр Российской академии наук, Ростов-на-Дону, Россия

СТРУКТУРНАЯ ОПТИМИЗАЦИЯ СХЕМОТЕХНИЧЕСКИХ РЕШЕНИЙ ДЛЯ РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ*

 

1. Введение

В последнее время широкое распространение получили высокопроизводительные реконфигурируемые вычислительные системы (РВС) на основе программируемых логических интегральных схем (ПЛИС), характеризующиеся близким к линейному росту производительности при увеличении аппаратного ресурса ПЛИС [1]. Особенностью РВС является адаптация архитектуры вычислительной системы под структуру решаемой задачи, при которой последовательно выполняются следующие этапы:

- построение из коммутационных, логических и арифметических устройств функциональной схемы, которая осуществляет обработку данных (в соответствии с алгоритмом прикладной задачи);

- автоматизированное размещение разработанной функциональной схемы в кристаллах ПЛИС (Implement Design) и проверки с помощью временного моделирования необходимых параметров проекта, удовлетворяющих требованиям разработчика;

- автоматический синтез конфигурационного файла ПЛИС (Generate Programming File).

Для синтеза конфигурационных файлов используются специализированные программы (синтезаторы), входящие в состав систем автоматизированного проектирования (САПР). Основной задачей программы-синтезатора является отображение функциональной схемы на аппаратный ресурс ПЛИС, однако программа-синтезатор не осуществляет оптимизацию используемого аппаратного ресурса, структурную оптимизацию функциональной схемы и обеспечение заданной тактовой частоты работы функциональной схемы, необходимые для синтеза сложных проектов при их отображении на  аппаратный ресурс вычислительного поля ПЛИС.

Отсутствие автоматизированных средств оптимизации функциональной схемы вынуждает специалиста-схемотехника все преобразования выполнять вручную. Следует также отметить, что увеличение количества функциональных блоков (IP-ядер) в функциональной схеме приводит к увеличению вероятности возникновения ошибки из-за «человеческого фактора», т.к. с ростом количества элементов в схеме схемотехнику сложнее контролировать взаимодействие элементов в схеме.

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

В НИИ многопроцессорных вычислительных систем ЮФУ был разработан синтезатор структурных параллельных прикладных программ для многокристальных реконфигурируемых вычислителей Fire!Constructor [2]. Синтезатор Fire!Constructor обеспечивает декомпозицию информационного графа на подграфы, каждый из которых отображается на аппаратный ресурс отдельного кристалла ПЛИС, входящего в состав РВС. Одной из важных задач, решаемых синтезатором Fire!Constructor, является оптимизация размещаемого структурного решения: уже реализована автоматическая расстановка задержек в вычислительных структурах с обратными связями [3]. В настоящий момент идет реализация описываемых методов структурной оптимизации функциональной схемы разрабатываемого электронного устройства.

 

2. Методы структурной оптимизации функциональной схемы

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

 

2.1. Метод замены операционных вершин эквивалентными

потенциалами

Как правило, в синтезированном информационном графе параллельно-конвейерной программы имеется несколько операционных вершин, на которые приходят постоянные информационные потоки (потенциалы). При отображении таких операционных вершин на аппаратный ресурс ПЛИС используется аппаратный ресурс (в частности, на прокладку связей). Поскольку входные информационные потоки для таких операционных вершин неизменны, то и выходные информационные потоки будут неизменными. Следовательно, можно заменить данные операционные вершины эквивалентными информационными потоками, при этом полученный информационный граф будет информационно эквивалентным исходному информационному графу.

Применение данного метода позволяет сократить используемый аппаратный ресурс ПЛИС примерно на 1%.

 

2.2. Метод удаления тупиковых вершин

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

Применение данного метода позволяет сократить используемый аппаратный ресурс ПЛИС также примерно на 1%.

 

2.3. Методы сокращения аппаратных ресурсов, используемых для реализации подсистемы синхронизации

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

 

2.3.1. Метод эквивалентных перестановок. Данный метод последовательно перебирает все операционные вершины информационного графа (задержки не являются операционными вершинами). У каждой операционной вершины анализируются выходные информационные потоки. Если информационный поток операционной вершины связан с двумя и более операционными вершинами, то происходит анализ и модификация данных связей. Анализ связей заключается в определении минимальной задержки на всех рассматриваемых связях и «вынесении ее за скобки», после чего проводится перекоммутация связей. При этом связи с минимальными задержками убираются из рассмотрения, и проводится дальнейший анализ оставшихся связей до тех пор, пока не останется только одна связь (или ни одной связи).

Покажем на примере, как работает данный метод. На рисунке 1-а представлен фрагмент информационного графа, имеющий вершину-источник информационного потока (сигнала) и 3 вершины-приемника. Кружками обозначены операционные вершины графа, а прямоугольниками - регистры синхронизации потоков данных, m1, m2, m3 – количество регистров, необходимых для синхронизации данных. Предположим, что m3 > m2 > m1. Как видно из рисунка 1-а сумма задержек равна:

Аппаратные затраты необходимые для реализации задержек можно выразить так:

где x – аппаратные затраты задержки одного бита данных на 1 такт;

      R – разрядность шины данных.

На рисунке 1-б представлен тот же фрагмент после применения одной итерации редуцирования. Сумма задержек равна

где n – количество операционных вершин, участвующих в редукции.

На рисунке 1-в представлен тот же фрагмент информационного графа после двух итераций редуцирования. Сумма задержек при этом равна

           

Таким образом, сумма всех задержек равна максимальной задержке, на которую задерживался сигнал до редуцирования. Это утверждение справедливо для любой комбинации задержек.

 

                                 а)                                                            б)                                                            в)

Рис. 1. Метод эквивалентных перестановок (а - фрагмент исходного графа; б - фрагмент графа после одной итерации редуцирования; в - фрагмент графа после двух итераций редуцирования).

 

Применение данного метода позволяет сократить используемый аппаратный ресурс ПЛИС на 5-15% в зависимости от предметной области прикладной задачи.

 

2.3.2. Метод поглощения. При создании подсистемы синхронизации на кристалле ПЛИС используются как «простые» задержки, использующие в качестве аппаратного ресурса ПЛИС 1 триггер и задерживающие цифровой сигнал на 1 такт, так и более сложные - программируемые элементы, использующие в качестве аппаратного ресурса ПЛИС 1 LUT и способные задерживать цифровой сигнал на произвольную величину от 1-го до N тактов (16 или 32).

   

                                                             а)                                    б)

Рис. 2. Редукция подсистемы синхронизации методом поглощения (а - до поглощения; б - после поглощения).

 

В процессе оптимизации подсистемы синхронизации нередко возникает ситуация, когда можно осуществить «поглощение» регистров синхронизации. На рисунке 2-а представлена операционная вершина, входные информационные потоки которой задерживаются программируемым элементом задержки на n тактов (N – n = 4). Выходной информационный поток проходит через каскад элементарных задержек, задерживающие сигнал на 5 тактов. Поскольку программируемый элемент обеспечивает задержку на 4 такта меньше максимально возможной, то можно его перепрограммировать на максимальную величину (рисунок 2-б). При этом для сохранения синхронизации выходной информационный поток необходимо задержать на 1 такт. Таким образом, проведенная модификация позволила редуцировать функциональную схему на 4 регистра (при условии, что рассматривался однобитный информационный поток, в противном случае выигрыш будет кратен разрядности информационного потока), что соответствует уменьшению необходимого аппаратного ресурса ПЛИС на реализацию данных регистров синхронизации.

Применение метода поглощения не всегда приводит к сокращению аппаратного ресурса. Пример подобного поглощения приведен на рисунке 3. Как видно на рисунке 3-б, применение метода поглощения не привело к сокращению аппаратного ресурса.

                                                        а)                                         б)

Рис. 3. Поглощение, не приводящее к сокращению аппаратного ресурса (а - исходный фрагмент

 информационного графа; б - фрагмент графа после поглощения).

 

Учитывая, что элементарные и программируемые синхронизирующие элементы используют разные аппаратные ресурсы ПЛИС (Flip-Flop и LUT соответственно), в ряде случаев можно воспользоваться эвристическим методом и заменить программируемый элемент, задерживающий выходной поток, тремя регистрами, если это необходимо. Замена программируемого элемента регистрами осуществляется по указанию разработчика при настройке параметров эвристического метода (указывается максимальное значение задержки, при котором программируемый элемент заменяется каскадом регистров).

Применение данного метода позволяет сократить используемый аппаратный ресурс ПЛИС примерно на 1-2%.

 

2.4. Выбор типа аппаратного ресурса, используемого для размещения

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

Данный механизм можно автоматизировать, указав программе-синтезатору формальные признаки, по которым должен осуществляться выбор схемотехнических элементов. Это позволяет более рационально использовать доступные аппаратные ресурсы ПЛИС и сократить использование критического (наиболее востребованного) аппаратного ресурса примерно на 1%.

 

2.5. Метод оптимизации структуры доступа к памяти

Для хранения промежуточных данных в цифровых устройствах используются блоки внутренней памяти (bram) ПЛИС, образующие массивы данных. Для хранения массива 32-разрядных данных размерностью 2n в современных ПЛИС фирмы Xilinx, семейств Virtex6 и Virtex7, используется схема, представленная на рисунке 4-а. При этом блок памяти RAM1 состоит из нескольких блоков меньшего размера. Увеличение тактовой частоты работы функциональной схемы оказывает большое влияние на работоспособность схемы. Это связано с тем, что при повышении тактовой частоты нагрузка на связи возрастает, вследствие чего на этапе размещения и трассировки (place and route) появляются ошибки при попытке трассировки длинных связей. Для их устранения необходимо модифицировать функциональную схему (рисунок 4-б). Подобная модификация подразумевает увеличение используемого аппаратного ресурса ПЛИС на реализацию дополнительных связей и одного мультиплексора. При этом нагрузка на связи уменьшится и, вероятность успешного синтеза проекта (без ошибок) возрастает. Если же в процессе синтеза возникли ошибки, то приведенную выше итерацию необходимо повторить еще раз (рисунок 4-в).

а)                                                   б)                                                                            в)

Рис. 4. Варианты схем доступа к памяти (а – исходная схема для хранения массива 32-разрядных данных размерностью 2n, б – одноитерационная модификация схемы, в – двухитерационная модификация схемы).

 

Применение данного метода позволяет сократить количество ошибок при синтезе конфигурационных файлов на этапе размещения и трассировки (place and route).

 

3. Заключение

Применение разработанных методов позволяет:

- сократить время разработки электронных устройств на основе ПЛИС за счет автоматического выполнения ряда структурных оптимизаций функциональной схемы (данные оптимизации приходится выполнять вручную специалисту-схемотехнику);

- сократить количество ошибок на этапе укладки и трассировки (place and route) за счет использования автоматизированных методов оптимизации, позволяющих синтезировать конфигурационные файлы функциональной схемы, работающих на заданной тактовой частоте;

- сократить используемый аппаратный ресурс ПЛИС без потери производительности разрабатываемого электронного устройства (повышение удельной производительности).

Согласно оценкам, применение описанных методов может суммарно сократить используемый аппаратный ресурс ПЛИС на 20%.

 

Литература

1.        Воеводин В.В., Воеводин Вл.В. Параллельные вычисления / В.В. Воеводин,; под ред. В.В. Воеводина. - С-Петербург: БХВ-Петербург, 2002. - 599 с.

2.        Гуленок А.А. Среда разработки масштабируемых структурных компонентов для реконфигурируемых вычислительных систем Тезисы Материалы Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы – 2007». – Таганрог: Изд-во ТТИ ЮФУ, 2007. – Т.1. – С. 289-292.

3.        Гуленок А.А., Бовкун А.В., Гудков В.А. Методы и алгоритмы автоматической расстановки задержек в вычислительных структурах с обратными связями. Вестник УГАТУ, Уфа, 2013. – 125-130 с.

 

______________________________________

*Работа выполнена при финансовой поддержке Министерства образования и науки РФ по Соглашению о предоставлении субсидии №14.578.21.0006 от 05.06.2014, уникальный идентификатор RFMEFI57814X0006, гранту Южного федерального университета №213.01-2014/014 и НИР №2257 базовой части государственного задания №2014/174.