Персональный сайт магистра ИССЛЕДОВАНИЕ ТЕХНИЧЕСКОГО КАРТОГРАФИРОВАНИЯ FPGA, КАК СПОСОБА ДЕКОМПОЗИЦИИ Д.В. Томах Донецкий национальный технический университет
Благодаря популярности основанных на LUT ( Look Up Table ) архитектур FPGA , была разработана огромная база алгоритмов по управлению областью LUT . Проблема минимизации области является сложной задачей для LUT входного размера четыре и меньше. Поэтому эвристика необходима, чтобы решить проблему минимизации области при разумной затрате времени для вычисления. Реконфигурируемые интегральные схемы FPGA представляют собой программируемые логические блоки, окруженные конфигурируемыми межсоединениями. Самые современные устройства FPGA содержат программируемые логические блоки, основанные на K-input LUT ( K - LUT ), каждый K - LUT содержит 2^ K конфигурируемых бит, с помощью которых реализуется любая K - input функция [1]. Число LUT -ов, необходимое для реализации предоставленной схемы, определяет размер и стоимость FPGA реализации. Поэтому одними из главных этапов автоматизированного проектирования FPGA является картографирование, которое переносит описание логической схемы на множество LUT элементов архитектуры FPGA . [2] Цель технологии картографирования[], как способа декомпозиции - сократить используемое пространство, задержку, или комбинацию того и другого в сети программируемых логических блоков. В данной работе оцениваются современные технологии алгоритмов нанесения на карту с точки зрения оптимизации занимаемого пространства. Процесс картографирования неразрывно связан с задачей о покрытии. Например, рассмотрим процесс составления схемы в LUT (Рисунок 1). Рисунок 1 a иллюстрирует начальную сеть на вентильном уровне, рисунок 1 b иллюстрирует возможное покрытие начальной сети с использованием 4- LUTs , и рисунок 1 c иллюстрирует уже покрытую сеть LUT . В предоставленной схеме вентиль с меткой x покрывается обоими LUT , т.е. дублируется. Практика показывает, что дублирование вентилей часто необходимо для минимизации области сетей LUT .
Рис.1 – Пример покрытия сети LUT Фундаментальный вопрос, на который должны дать ответ исследования, таков: на сколько может быть уменьшена область для полученной сети LUT , созданной при помощи алгоритма технологического картографирования? Для маленькой подсхемы, возможно ответить на этот вопрос оптимальным способом. Рассмотрим произвольную функцию f ( i 0; i 1;… in ) с целью определения возможности уменьшения области при использовании трех или меньше двухвходовых LUT . Эта задача может быть решена при рассмотрении конфигурируемой виртуальной сети (Con fi gurable Virtual Network CVN) [3]. CVN состоит из входных линий соединенных с переменными i 0… in и три 2- LUT . Поперечная связь позволяет входам LUT выбрать любую из входных линий или выход от другого LUT . Каждый “переключатель” на перемычке - конфигурируется виртуальным битом конфигурации: «0» указывает что пересечение разъединено, «1» связь присутствует. Очевидно, что можно оперделить каждую возможную схемную конфигурацию, включающую в себя три 2- LUT , манипулируя виртуальными битами конфигурации для поперечной связи также, как и таблица истинности конфигураций битов каждого из 2- LUTs . Фактически, мы можем выразить выход fnet , как логическую формулу, включающую переменные i 0… in , виртуальные биты конфигурации V 1… Vm и конфигурационные биты таблицы истинности L 1… L 0. Получив эту формулу, необходимо определить: существуют ли значения V 1… Vm и L 1… L 0 такие, что функция fnet ( i 0; i 1; in ; V 1… Vm ; L 1… Lo ) будет идентична функции f ( i 0; i 1; in ) для всех значений i 0… in . Сложность разрешения этой задачи экспоненциально возрастает с повышением числа переменных n виртуальной сети. Множество известных алгоритмов основаны на разложении схем на набор деревьев, которые затем наносятся на карту области [4]. Проблема области минимизации для деревьев намного проще и может быть оптимально решена с использованием динамического программирования. Однако, реальные схемы редко структурированы как деревья и разложение на поиск деревьев препятствует оптимизации. Дальнейшие направления исследований связаны с реализацией устройств управления устройств управления на FPGA и дальнейшей оптимизацией логических схем по стоимостным характеристикам. Исследования направлены на подтверждение (или опровержение) теоретических предположений о том, что оптимальное преобразование подсхем позволяет использовать меньшее количество LUT , причем суммарная оптимизация занимаемого пространства может достигать 60%, что существенно влияет на уменьшение общей стоимости устройства.
Литература 1. Грушвицкий Р. И., Мурсаев А. Х., Угрюмов Е. П., "Проектирование систем на микросхемах программируемой логики", 2002г. - 608стр. 2. Максфилд К., «Проектирование на ПЛИС», 2007г. – 404стр. 3. Интернет: http://www.soccentral.com/results.asp?CatID=478&EntryID=15000 4. Зотов, «Проектирование встраиваемых приложений на основе ПЛИС фирмы Xilinx», 2006г. |
 |
