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

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

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

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

Введение

Программируемая пользователем вентильная матрица (ППВМ, 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.

Булева сеть, не являющаяся K-ограниченной, может не иметь определенного выше отображения. Для того, чтобы сделать сеть K-ограниченной, можно использовать декомпозицию вентилей, чтобы разбить крупные вентили на более мелкие. В качестве предварительной обработки FlowMap алгоритм под названием DMIG [3], который преобразует все вентили в вентили с двумя входами при помощи оптимального обхода в глубину, в результате делая сеть K-ограниченной для [math]\displaystyle{ К \ge 2 \; }[/math]. Различные схемы декомпозиции могут привести к получению разных K-ограниченных сетей и, следовательно, разных решений с отображением; оптимальность FlowMap имеет отношение к конкретной K-ограниченной сети.

На рис. 1 представлены булева сеть, ее ориентированный ациклический граф, покрытие 3-допустимыми конусами и полученная в результате сеть 3-LUT. Как можно заметить, конусы покрытия могут перекрываться; это допустимо и нередко оказывается полезным. (При реализации отображенной сети часть логики, попавшая в перекрытие, будет продублирована для каждой таблицы K-LUT, в которую она входит).

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

Основные результаты

Алгоритм FlowMap работает в два этапа. На первом этапе он для каждой не являющейся первичным входом вершины определяет предпочтительный K-допустимый конус в качестве кандидата для покрытия; конусы вычисляются таким образом, что в случае их использования они дают оптимальное по глубине решение отображения. Это основной этап алгоритма. На втором этапе выбираются конусы, необходимые для формирования покрытия для получения решения отображения.

Структура оптимальных по глубине K-покрытий

Обозначим за M(v) K-покрытие (или эквивалентное решение отображения на K-LUT) исходной сети [math]\displaystyle{ N_v \; }[/math] вершины v. Если v является первичным входом, M(v) состоит только из самой вершины v. (Для простоты далее M(v) будет называться K-покрытием v). Имеет место следующая лемма.

Лемма 1. Если [math]\displaystyle{ C_v \; }[/math] является K-допустимым конусом вершины v в K-покрытии M(v), то [math]\displaystyle{ M(v) = \{ C_v \} + \bigcup \{ M(u): u \in input(C_v) \} }[/math], где M(u) – определенное K-покрытие вершины u. Соответственно, если [math]\displaystyle{ C_v \; }[/math] является K-допустимым конусом вершины v и для каждой вершины [math]\displaystyle{ u \in input(C_v) \; }[/math] множество M(u) является K-покрытием u, то [math]\displaystyle{ M(v) = \{ C_v \} + \bigcup \{ M(u): u \in input(C_v) \} }[/math] является K-покрытием v.

Иными словами, K-покрытие состоит из K-допустимого конуса и K-покрытия каждой входной точки конуса. Заметим, что для [math]\displaystyle{ u_1 \in input(C_v), u_2 \in input(C_v) \; }[/math] множества [math]\displaystyle{ M(u_1) \; }[/math] и [math]\displaystyle{ M(u_2) \; }[/math] могут перекрываться, и фрагмент, попавший в такое перекрытие, может быть покрыт таким же образом или не быть покрыт; вышеприведенное объединение включает все отдельные конусы на всех путях. Заметим также, что для заданного конуса [math]\displaystyle{ C_v \; }[/math] могут существовать различные K-покрытия v, содержащие [math]\displaystyle{ C_v \; }[/math], в зависимости от выбора M(u) для каждой [math]\displaystyle{ u \in input(C_v) \; }[/math].

Обозначим за d(M(v)) глубину M(v). Тогда выполняется следующая лемма.

Лемма 2. Для K-покрытия [math]\displaystyle{ M(v) = \{ C_v \} + \bigcup \{ M(u): u \in input(C_v) \} }[/math] имеет место [math]\displaystyle{ d(M(v)) = max \{d(M(u)): u \in input(C_v) \} + 1 \; }[/math].

В частности, обозначим за [math]\displaystyle{ M^*(u) \; }[/math] K-покрытие вершины u с минимальной глубиной. Тогда [math]\displaystyle{ d(M(v)) \ge max \{ d(M^*(u)): u \in input(C_v) \} + 1 \; }[/math]; равенство имеет место в случае, когда каждое покрытие M(u) в M(v) имеет минимальную глубину.

Вспомним, что [math]\displaystyle{ C_v \; }[/math] определяет K-допустимый разрез (X, X'), где [math]\displaystyle{ X' = C_v, X = N_v - C_v \; }[/math]. Обозначим за H(X, X') высоту разреза (X, X'), определяемую как [math]\displaystyle{ H(X, X') = max \{ d(M^*(u)): u \in input(X') \} + 1 \; }[/math]. Очевидно, что H(X, X') обеспечивает минимальную глубину для любого K-покрытия вершины v, содержащего [math]\displaystyle{ C_v = X' \; }[/math]. Кроме того, за счет подходящего выбора разреза можно минимизировать высоту H(X, X'), что позволяет получить K-покрытие с минимальной глубиной:

Теорема 1. Если K-допустимый разрез (X, X') по v имеет минимальную высоту среди всех K-допустимых разрезов по v, то K-покрытие [math]\displaystyle{ M^*(v) = \{ X' \} + \bigcup \{ M^*(u): u \in input(X') \} }[/math] имеет минимальную глубину среди всех K-покрытий v.

Иначе говоря, K-допустимый разрез минимальной высоты определяет K-покрытие с минимальной глубиной. Таким образом, основной задачей оптимального по глубине технологического отображения становится вычисление K-допустимого разреза минимальной высоты для каждой вершины, являющейся первичным выходом.

По определению, высота разреза зависит от (глубин) K-покрытий с минимальной глубиной вершин из множества [math]\displaystyle{ N_v - \{ v \} \; }[/math]. Для этого можно использовать процедуру динамического программирования, следующую топологическому порядку, так что к моменту, когда необходимо определить K-покрытие v с минимальной глубиной, K-покрытие каждой вершины из [math]\displaystyle{ N_v - \{ v \} \; }[/math] с минимальной глубиной уже известно, и высоту разреза можно легко определить. Именно так работает первый этап алгоритма FlowMap.

Вычисление K-допустимого разреза минимальной высоты

Первый этап работы алгоритма FlowMap изначально был назван этапом разметки, так как он включает вычисление метки для каждой вершины K-ограниченного графа. Метка не являющейся первичным входом вершины v, обозначаемая как l(v), определяется как минимальная высота любого разреза по v. Для удобства метки вершин, являющихся первичными входами, считаются равными 0.

Определенные таким образом метки обладают важным свойством монотонности.

Лемма 3. Пусть [math]\displaystyle{ p = max \{ l(u): u \in input(v) \} \; }[/math]. Тогда [math]\displaystyle{ p \le l(v) \le p + 1 \; }[/math].

Заметим, что из этого также следует, что для любой вершины [math]\displaystyle{ u \in N_v - \{ v \} \; }[/math] верно [math]\displaystyle{ l(u) \le p \; }[/math]. Основываясь на этом наблюдении, для поиска K-допустимого разреза минимальной высоты достаточно проверить, существует ли разрез с высотой p; если нет, то любой K-допустимый разрез будет иметь минимальную высоту (p + 1), и один такой разрез всегда существует для K-ограниченного графа.

Поиск K-допустимого разреза высоты (p > 0; случай p = 0 является тривиальным) в алгоритме FlowMap выполняется посредством преобразования Nv в транспортную сеть Fv и вычисления потока в этой сети [4] (отсюда и название). Преобразование выполняется следующим образом. Для каждой вершины u 2 Nv - {v}, l(u) < p, в Fv имеются две вершины u1 и u2, связанные мостовым ребром hu1;u2i; Fv содержит единственную вершину-сток t для всех остальных вершин в Nv и единственную вершину-источник s. Для каждой вершины u из Nv, являющейся первичным входом, которая соответствует мостовому ребру («ь мг) в Fv, Fv содержит ребро hs;u1i; для каждого ребра hu; wi и Nv в случае, если и u, и w имеют мостовые ребра в Fv, Fv содержит ребро hu 2 ;w1 i; если u имеет мостовое ребро, а w не имеет, Fv содержит ребро edge hu2 ; ti; в противном случае (если ни у одной вершины не имеется мостового ребра) Fv не содержит соответствующего ребра. Мостовое ребро имеет единичную пропускную способность; все прочие ребра имеют бесконечную пропускную способность. Если заметить, что каждое ребро в Fv с бесконечной (или единичной) пропускной способностью соответствует вершине u 2 Nv с l(u) < p и наоборот, и вспомнить теорему о максимальном потоке и минимальном сечении [4], можно показать справедливость следующей леммы.

Лемма 4. Вершина v содержит K-допустимый разрез высоты p в том и только том случае, если значение максимального потока в сети Fv не превышает K.