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

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

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

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

Введение

Программируемая пользователем вентильная матрица (ППВМ, 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) и может не иметь исходящих ребер, если ее результат используется только вне сети.

Если hu; vi 2 E, u называется разветвлением на входе (fanin) вершины v, и v – разветвлением на выходе (fanout) вершины u. Для вершины v обозначим за input(v) множество ее fanin; аналогичным образом для подграфа H обозначим за input(H) множество отдельных вершин вне H, являющихся fanin для вершин из H. Если существует прямой путь в N из вершины u в вершину v, u называется предком v, а v – потомком u. Входной сетью вершины v, обозначаемой Nv, является подграф, содержащий вершину v и всех ее предков. Конусом не являющейся первичным входом вершины v, обозначаемым Cv, является подграф Nv, содержащий v и, возможно, некоторых из ее предков, не являющихся первичными входами, таких, что для любой вершины u 2 Cv существует путь из u в v по Cv. Если |input(Cv)| < K, Cv называется K-допустимым конусом. Сеть N является K-ограниченной, если каждая вершина, не являющаяся первичным входом, имеет K-допустимый конус. Разрез по не являющейся первичным входом вершине v представляет собой биразбиение (X, X0) вершин из Nv, такое, что X0 является конусом v; input(X0) называется сечением (X, X0), и n(X;X0) = |input(X0)| – размером разреза. Если n(X; X0) < K, то (X, X0) является K-допустимым разрезом. Обозначим мощность разреза (X, X0) как vol(X, X0) = |X0|.

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

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