Технологическое отображение ППВМ

Ключевые слова и синонимы

Отображение таблицы поиска; карта потока

Постановка задачи

Введение

Программируемая пользователем вентильная матрица (ППВМ, FPGA) представляет собой разновидность интегральной схемы (ИС, IC), которая может быть (пере)программирована для реализации пользовательских логических функций. Большинство ППВМ-устройств используют таблицу поиска (lookup-table, LUT) в качестве базового логического элемента, при этом таблица поиска с K логическими входами (K-LUT) может представлять любую булеву функцию, содержащую до K переменных. ППВМ также содержит и другие логические элементы, такие как регистры, программируемые компоненты межсоединений и компоненты ввода/вывода [5].

Программирование ППВМ включает преобразование логической схемы в форму, подходящую для реализации на целевом ППВМ-устройстве. Этот процесс обычно выполняется за несколько шагов. Для ППВМ на основе таблицы поиска технологическое отображение заключается в преобразовании булевой сети общего вида (полученной на основе спецификации проекта в результате предыдущего преобразования) в функционально эквивалентную сеть K-LUT, которая может быть реализована на целевом ППВМ-устройстве. Целью алгоритма технологического отображения является генерация, наряду с множеством возможных решений, оптимизированного решения согласно определенным критериям, которыми могут быть: оптимизация синхронизации, благодаря которой полученная реализация может работать с более высокой скоростью, минимизация площади, благодаря которой полученная реализация может быть сделана более компактной, и минимизация мощности, благодаря которой полученная реализация может потреблять меньше электрической мощности. Представленный здесь алгоритм под названием FlowMap [2] предназначен для оптимизации синхронизации; он стал первым доказуемо оптимальным алгоритмом технологического отображения с полиномиальным временем выполнения на булевых сетях общего вида, а реализованные в нем концепции и подход с тех пор нашли множество полезных приложений и следствий.

Представление данных и предварительные условия

В качестве входных данных для алгоритма технологического отображения для ППВМ на основе таблицы поиска является булева сеть общего вида, которая может моделироваться ориентированным ациклическим графом N = (V, E). Вершина v 2 V может представлять либо источник логического сигнала вне сети, в таком случае она не имеет входящего ребра и называется первичным входом (primary input, PI); либо логический вентиль, в таком случае она имеет одно или несколько входящих ребер от первичных входов и других вентилей, являющихся логическими входами. Если логический выход вентиля также используется вне сети, соответствующая вершина является первичным выходом (primary output, PO) и может не иметь исходящих ребер, если ее результат используется только вне сети.

Если [math]\displaystyle{ \langle u, v \rangle \in E }[/math], u называется разветвлением на входе (fanin) вершины v, а v – разветвлением на выходе (fanout) вершины u. Для вершины v обозначим за input(v) множество ее fanin; аналогичным образом для подграфа H обозначим за input(H) множество отдельных вершин вне H, являющихся fanin для вершин из H. Если существует прямой путь в N из вершины u в вершину v, u называется предком v, а v – потомком u. Входной сетью вершины v, обозначаемой [math]\displaystyle{ N_v \; }[/math], является подграф, содержащий вершину v и всех ее предков. Конусом не являющейся первичным входом вершины v, обозначаемым [math]\displaystyle{ C_v \; }[/math], является подграф [math]\displaystyle{ N_v \; }[/math], содержащий v и, возможно, некоторых из ее предков, не являющихся первичными входами, таких, что для любой вершины [math]\displaystyle{ u \in C_v \; }[/math] существует путь из u в v по [math]\displaystyle{ C_v \; }[/math]. Если [math]\displaystyle{ |input(C_v)| \le K \; }[/math], [math]\displaystyle{ C_v \; }[/math] называется K-допустимым конусом. Сеть N является K-ограниченной, если каждая вершина, не являющаяся первичным входом, имеет K-допустимый конус. Разрез по не являющейся первичным входом вершине v представляет собой биразбиение (X, X') вершин из [math]\displaystyle{ N_v \; }[/math], такое, что X' является конусом v; input(X') называется сечением (X, X'), а n(X, X') = |input(X')| – размером разреза. Если [math]\displaystyle{ n(X, X') \le K \; }[/math], то (X, X') является K-допустимым разрезом. Обозначим мощность разреза (X, X') как vol(X, X') = |X'|.

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

Формулировка задачи

K-покрытием некоторой булевой сети N является сеть [math]\displaystyle{ N_M = (V_M, E_M) \; }[/math], где [math]\displaystyle{ V_M \; }[/math] состоит из вершин N, являющихся первичными входами, и некоторых K-допустимых конусов вершин N, таких, что для каждой вершины v в N, являющейся первичным выходом, [math]\displaystyle{ V_M \; }[/math] содержит конус [math]\displaystyle{ C_v \; }[/math] вершины v; если [math]\displaystyle{ C_u \in V_M \; }[/math], то для каждой не являющейся первичным выходом вершины [math]\displaystyle{ v \in input(C_u) \; }[/math] множество [math]\displaystyle{ V_M \; }[/math] также содержит конус [math]\displaystyle{ C_v \; }[/math] вершины v. Ребро [math]\displaystyle{ \langle u, C_v \rangle }[/math] принадлежит [math]\displaystyle{ E_M \; }[/math] в том и только том случае, если являющаяся первичным входом вершина u принадлежит input([math]\displaystyle{ C_v \; }[/math]); ребро [math]\displaystyle{ \langle C_u, C_v \rangle }[/math] принадлежит [math]\displaystyle{ E_M \; }[/math] в том и только том случае, если не являющаяся первичным входом вершина u принадлежит input([math]\displaystyle{ C_v \; }[/math]). Поскольку каждый K-допустимый конус может быть реализован в виде таблицы поиска K-LUT, K-покрытие может быть реализовано в виде сети таблиц K-LUT. Таким образом, задача технологического отображения для ППВМ на основе K-LUT, заключающаяся в преобразовании N в сеть таблиц K-LUT, соответствует нахождению K-покрытия [math]\displaystyle{ N_M \; }[/math] множества N.

Глубина сети равна максимальному количеству ребер на самом длинном пути. Решение задачи технологического отображения [math]\displaystyle{ N_M \; }[/math] является оптимальным по глубине, если оно имеет минимальную длину среди всех возможных решений отображения для N. Если предполагается, что каждый уровень логики таблицы поиска K-LUT вносит константную логическую задержку (такая модель называется моделью с единичной задержкой), то минимальная глубина соответствует наименьшей логической задержке распространения по решению или, иными словами, самой быстрой реализации K-LUT на сети N. Задача, решенная алгоритмом FlowMap, представляет собой оптимальное по глубине технологическое отображение для ППВМ на основе таблиц K-LUT.