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

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

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

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

Введение

Программируемая пользователем вентильная матрица (ППВМ, 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 выполняется посредством преобразования [math]\displaystyle{ N_v \; }[/math] в транспортную сеть [math]\displaystyle{ F_v \; }[/math] и вычисления потока в этой сети [4] (отсюда и название). Преобразование выполняется следующим образом. Для каждой вершины [math]\displaystyle{ u \in N_v - \{ v \}, l(u) \lt p \; }[/math], в [math]\displaystyle{ F_v \; }[/math] имеются две вершины [math]\displaystyle{ u_1 \; }[/math] и [math]\displaystyle{ u_2 \; }[/math], связанные мостовым ребром [math]\displaystyle{ \langle u_1, u_2 \rangle }[/math]; [math]\displaystyle{ F_v \; }[/math] содержит единственную вершину-сток t для всех остальных вершин в [math]\displaystyle{ N_v \; }[/math] и единственную вершину-источник s. Для каждой вершины u из [math]\displaystyle{ N_v \; }[/math], являющейся первичным входом, которая соответствует мостовому ребру [math]\displaystyle{ \langle u_1, u_2 \rangle }[/math] в [math]\displaystyle{ F_v \; }[/math], [math]\displaystyle{ F_v \; }[/math] содержит ребро [math]\displaystyle{ \langle s, u_1 \rangle }[/math]; для каждого ребра [math]\displaystyle{ \langle u, w \rangle }[/math] и [math]\displaystyle{ N_v \; }[/math] в случае, если и u, и w имеют мостовые ребра в [math]\displaystyle{ F_v \; }[/math], [math]\displaystyle{ F_v \; }[/math] содержит ребро [math]\displaystyle{ \langle u_2, w_1 \rangle }[/math]; если u имеет мостовое ребро, а w не имеет, [math]\displaystyle{ F_v \; }[/math] содержит ребро edge [math]\displaystyle{ \langle u_2, t \rangle }[/math]; в противном случае (если ни у одной вершины не имеется мостового ребра) [math]\displaystyle{ F_v \; }[/math] не содержит соответствующего ребра. Мостовые ребра имеют единичную пропускную способность; все прочие ребра имеют бесконечную пропускную способность. Если заметить, что каждое ребро в [math]\displaystyle{ F_v \; }[/math] с бесконечной (или единичной) пропускной способностью соответствует вершине [math]\displaystyle{ u \in N_v \; }[/math] с l(u) < p и наоборот, и вспомнить теорему о максимальном потоке и минимальном сечении [4], можно показать справедливость следующей леммы.

Лемма 4. Вершина v содержит K-допустимый разрез высоты p в том и только том случае, если значение максимального потока в сети [math]\displaystyle{ F_v \; }[/math] не превышает K.

Зная поток в сети [math]\displaystyle{ F_v \; }[/math], можно вычислить максимальный поток при помощи алгоритма нахождения дополняющего пути [4]. После вычисления максимального потока оставшийся граф сети потока отключается, и соответствующий минимальный разрез (X, X') определяется следующим образом: [math]\displaystyle{ v \in X' \; }[/math] ; для [math]\displaystyle{ u \in N_v - \{ v \} \; }[/math], если оно является мостовым множеством в [math]\displaystyle{ F_v \; }[/math] и [math]\displaystyle{ u_1 \; }[/math] может быть достигнуто при помощи поиска в глубину по оставшемуся графу из s, то [math]\displaystyle{ u \in X \; }[/math] ; в противном случае [math]\displaystyle{ u \in X' \; }[/math].

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

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

Теорема 2. В K-ограниченной булевой сети с n вершинами и m ребрами вычисление K-допустимого разреза минимальной высоты для каждой вершины может быть выполнено за время O(Kmn).

Разрез, найденный алгоритмом, имеет другое свойство:

Лемма 5. Разрез (X, X'), вычисленный вышеописанным образом, представляет собой уникальный минимальный разрез максимального объема; более того, если (Y, Y') – еще один минимальный разрез, то [math]\displaystyle{ Y' \subseteq X' }[/math].

Интуитивно понятно, что разрез большего объема определяет конус большей величины, охватывающий больше логики, в силу чего разрез большего объема является более предпочтительным. Однако заметим, что лемма 5 говорит только о максимуме среди минимальных разрезов; если n(X, X') < K, то могут существовать другие разрезы, все еще являющиеся K-допустимыми, но имеющие большую величину и больший объем. Алгоритм постобработки, используемый FlowMap, пытается увеличить (X, X') за счет коллапсирования всех вершин из X', а также одной или нескольких вершин в сечении, в сток и последующего повторного вычисления потока; это приводит к получению разреза большего объема и оказывается выигрышным, если разрез по-прежнему остается K-допустимым.

Построение K-покрытия

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

Лемма 6. K-покрытие, построенное вышеописанным образом, является оптимальным по глубине.

Эта процедура линейна по времени, следовательно,

Теорема 3. Задача оптимального по глубине технологического отображения для ППВМ на основе таблиц K-LUT на булеву сеть с n вершинами и m ребрами может быть решена за время O(Kmn).

Применение

Алгоритм FlowMap использовался как центральный структурный компонент более сложных алгоритмов синтеза логики ППВМ и технологического отображения. Существует множество различных вариантов, подходящих для удовлетворения различных потребностей практических приложений. Некоторые из них вкратце описаны далее. Более детальное изложение вариантов и приложений можно найти в работах [1, 3].

Более сложные модели задержки

С минимальными изменениями алгоритм может быть применен для модели с неединичными задержками, в которой задержки вершин и/или ребер могут различаться, оставаясь статичными. Модели с динамическими задержками, в которых задержка сети определяется ее структурой после отображения, неприменимы к данному алгоритму. Оптимальное по задержке отображение с использованием динамической модели задержки на деле является NP-полным [3].

Более сложные архитектуры

Алгоритм может быть адаптирован к более сложным архитектурам ППВМ, нежели гомогенные массивы таблиц K-LUT. К примеру, отображение для ППВМ с двумя размерами таблиц LUT может быть выполнено посредством вычисления конуса для каждого размера и динамического выбора лучшего варианта.

Несколько целей оптимизации

Алгоритм ориентирован на минимизацию задержки, однако можно использовать его для минимизации площади (в терминах количества выбранных конусов) и других целей при помощи адаптации критерия выбора разреза. Исходный алгоритм решает задачу минимизации площади при помощи максимизации объема разрезов; значительно более сильная минимизация может быть достигнута за счет рассмотрения большего количества K-допустимых разрезов и осуществления рациональных выборов – например, допущения разрезов большей высоты вдоль некритических путей и т. п. Однако нахождение оптимальной площади является NP-полной задачей.

Интеграция с другими техниками оптимизации

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

См. также

Литература

Алгоритм FlowMap в более детальном виде и с экспериментальными результатами представлен в работе [2]. Общую информацию о ППВМ можно найти в [5]. Понятия и алгоритмы расчета сетевого потока адекватно изложены в [4]. Комплексный обзор подходов к автоматизации проектирования ППВМ, включающий множество вариаций и способов применения алгоритма FlowMap и других алгоритмов, можно найти в [1, 3].

1. Chen, D., Cong, J., Pan, P.: FPGA design automation: a survey. Foundations and Trends in Electronic Design Automation, vol 1, no 3. Now Publishers, Hanover, USA (2006)

2. Cong, J., Ding, Y.: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs, Proc. IEEE/ACM International Conference on Computer-Aided Design, pp. 48-53. San Jose, USA (1992)

3. Cong, J., Ding, Y.: Combinational logic synthesis for LUT based field programmable gate arrays. ACM Trans. Design Autom. Electron. Sys. 1(2): 145-204 (1996)

4. Tarjan, R.: Data Structures and Network Algorithms. SIAM. Philadelphia, USA (1983)

5. Trimberger, S.: Field-Programmable Gate Array Technology. Springer, Boston, USA (1994)