4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
(не показано 19 промежуточных версий этого же участника) | |||
Строка 26: | Строка 26: | ||
''K-покрытием'' некоторой булевой сети N является сеть <math>N_M = (V_M, E_M) \;</math>, где <math>V_M \;</math> состоит из вершин N, являющихся первичными входами, и некоторых K-допустимых конусов вершин N, таких, что для каждой вершины v в N, являющейся первичным выходом, <math>V_M \;</math> содержит конус <math>C_v \;</math> вершины v; если <math>C_u \in V_M \;</math>, то для каждой не являющейся первичным выходом вершины <math>v \in input(C_u) \;</math> множество <math>V_M \;</math> также содержит конус <math>C_v \;</math> вершины v. Ребро <math>\langle u, C_v \rangle</math> принадлежит <math>E_M \;</math> в том и только том случае, если являющаяся первичным входом вершина u принадлежит input(<math>C_v \;</math>); ребро <math>\langle C_u, C_v \rangle</math> принадлежит <math>E_M \;</math> в том и только том случае, если не являющаяся первичным входом вершина u принадлежит input(<math>C_v \;</math>). Поскольку каждый K-допустимый конус может быть реализован в виде таблицы поиска K-LUT, K-покрытие может быть реализовано в виде сети таблиц K-LUT. Таким образом, задача ''технологического отображения'' для ППВМ на основе K-LUT, заключающаяся в преобразовании N в сеть таблиц K-LUT, соответствует нахождению K-покрытия <math>N_M \;</math> множества N. | ''K-покрытием'' некоторой булевой сети N является сеть <math>N_M = (V_M, E_M) \;</math>, где <math>V_M \;</math> состоит из вершин N, являющихся первичными входами, и некоторых K-допустимых конусов вершин N, таких, что для каждой вершины v в N, являющейся первичным выходом, <math>V_M \;</math> содержит конус <math>C_v \;</math> вершины v; если <math>C_u \in V_M \;</math>, то для каждой не являющейся первичным выходом вершины <math>v \in input(C_u) \;</math> множество <math>V_M \;</math> также содержит конус <math>C_v \;</math> вершины v. Ребро <math>\langle u, C_v \rangle</math> принадлежит <math>E_M \;</math> в том и только том случае, если являющаяся первичным входом вершина u принадлежит input(<math>C_v \;</math>); ребро <math>\langle C_u, C_v \rangle</math> принадлежит <math>E_M \;</math> в том и только том случае, если не являющаяся первичным входом вершина u принадлежит input(<math>C_v \;</math>). Поскольку каждый K-допустимый конус может быть реализован в виде таблицы поиска K-LUT, K-покрытие может быть реализовано в виде сети таблиц K-LUT. Таким образом, задача ''технологического отображения'' для ППВМ на основе K-LUT, заключающаяся в преобразовании N в сеть таблиц K-LUT, соответствует нахождению K-покрытия <math>N_M \;</math> множества N. | ||
''Глубина сети'' равна максимальному количеству ребер на самом длинном пути. Решение задачи технологического отображения <math>N_M \;</math> является ''оптимальным по глубине'', если оно имеет минимальную длину среди всех возможных решений отображения для N. Если предполагается, что каждый уровень логики таблицы поиска K-LUT вносит константную логическую задержку (такая модель называется ''моделью с единичной задержкой''), то минимальная глубина соответствует наименьшей логической задержке распространения по решению или, иными словами, самой быстрой реализации K-LUT на сети N. Задача, решенная алгоритмом FlowMap, представляет собой ''оптимальное по глубине технологическое отображение'' для ППВМ на основе таблиц K-LUT. | |||
Булева сеть, не являющаяся K-ограниченной, может не иметь определенного выше отображения. Для того, чтобы сделать сеть K-ограниченной, можно использовать ''декомпозицию вентилей'', чтобы разбить крупные вентили на более мелкие. В качестве предварительной обработки FlowMap алгоритм под названием DMIG [3], который преобразует все вентили в вентили с двумя входами при помощи оптимального обхода в глубину, в результате делая сеть K-ограниченной для <math>К \ge 2 \;</math>. Различные схемы декомпозиции могут привести к получению разных K-ограниченных сетей и, следовательно, разных решений с отображением; оптимальность FlowMap имеет отношение к конкретной K-ограниченной сети. | |||
На рис. 1 представлены булева сеть, ее ориентированный ациклический граф, покрытие 3-допустимыми конусами и полученная в результате сеть 3-LUT. Как можно заметить, конусы покрытия могут перекрываться; это допустимо и нередко оказывается полезным. (При реализации отображенной сети часть логики, попавшая в перекрытие, будет продублирована для каждой таблицы K-LUT, в которую она входит). | |||
[[Файл:FPGA_1.png|720px]] | |||
Рисунок 1. Технологическое отображение ППВМ | |||
== Основные результаты == | |||
Алгоритм FlowMap работает в два этапа. На первом этапе он для каждой не являющейся первичным входом вершины определяет предпочтительный K-допустимый конус в качестве кандидата для покрытия; конусы вычисляются таким образом, что в случае их использования они дают оптимальное по глубине решение отображения. Это основной этап алгоритма. На втором этапе выбираются конусы, необходимые для формирования покрытия для получения решения отображения. | |||
'''Структура оптимальных по глубине K-покрытий''' | |||
Обозначим за M(v) K-покрытие (или эквивалентное решение отображения на K-LUT) исходной сети <math>N_v \;</math> вершины v. Если v является первичным входом, M(v) состоит только из самой вершины v. (Для простоты далее M(v) будет называться ''K-покрытием v''). Имеет место следующая лемма. | |||
'''Лемма 1'''. Если <math>C_v \;</math> является K-допустимым конусом вершины v в K-покрытии M(v), то <math>M(v) = \{ C_v \} + \bigcup \{ M(u): u \in input(C_v) \}</math>, где M(u) – определенное K-покрытие вершины u. Соответственно, если <math>C_v \;</math> является K-допустимым конусом вершины v и для каждой вершины <math>u \in input(C_v) \;</math> множество M(u) является K-покрытием u, то <math>M(v) = \{ C_v \} + \bigcup \{ M(u): u \in input(C_v) \}</math> является K-покрытием v. | |||
Иными словами, K-покрытие состоит из K-допустимого конуса и K-покрытия каждой входной точки конуса. Заметим, что для <math>u_1 \in input(C_v), u_2 \in input(C_v) \;</math> множества <math>M(u_1) \;</math> и <math>M(u_2) \;</math> могут перекрываться, и фрагмент, попавший в такое перекрытие, может быть покрыт таким же образом или не быть покрыт; вышеприведенное объединение включает все отдельные конусы на всех путях. Заметим также, что для заданного конуса <math>C_v \;</math> могут существовать различные K-покрытия v, содержащие <math>C_v \;</math>, в зависимости от выбора M(u) для каждой <math>u \in input(C_v) \;</math>. | |||
Обозначим за d(M(v)) глубину M(v). Тогда выполняется следующая лемма. | |||
'''Лемма 2'''. Для K-покрытия <math>M(v) = \{ C_v \} + \bigcup \{ M(u): u \in input(C_v) \}</math> имеет место <math>d(M(v)) = max \{d(M(u)): u \in input(C_v) \} + 1 \;</math>. | |||
В частности, обозначим за <math>M^*(u) \;</math> K-покрытие вершины u с минимальной глубиной. Тогда <math>d(M(v)) \ge max \{ d(M^*(u)): u \in input(C_v) \} + 1 \;</math>; равенство имеет место в случае, когда каждое покрытие M(u) в M(v) имеет минимальную глубину. | |||
Вспомним, что <math>C_v \;</math> определяет K-допустимый разрез (X, X'), где <math>X' = C_v, X = N_v - C_v \;</math>. Обозначим за H(X, X') ''высоту'' разреза (X, X'), определяемую как <math>H(X, X') = max \{ d(M^*(u)): u \in input(X') \} + 1 \;</math>. Очевидно, что H(X, X') обеспечивает минимальную глубину для любого K-покрытия вершины v, содержащего <math>C_v = X' \;</math>. Кроме того, за счет подходящего выбора разреза можно минимизировать высоту H(X, X'), что позволяет получить K-покрытие с минимальной глубиной: | |||
'''Теорема 1. Если K-допустимый разрез (X, X') по v имеет минимальную высоту среди всех K-допустимых разрезов по v, то K-покрытие <math>M^*(v) = \{ X' \} + \bigcup \{ M^*(u): u \in input(X') \}</math> имеет минимальную глубину среди всех K-покрытий v.''' | |||
Иначе говоря, K-допустимый разрез минимальной высоты определяет K-покрытие с минимальной глубиной. Таким образом, основной задачей оптимального по глубине технологического отображения становится вычисление K-допустимого разреза минимальной высоты для каждой вершины, являющейся первичным выходом. | |||
По определению, высота разреза зависит от (глубин) K-покрытий с минимальной глубиной вершин из множества <math>N_v - \{ v \} \;</math>. Для этого можно использовать процедуру ''динамического программирования'', следующую топологическому порядку, так что к моменту, когда необходимо определить K-покрытие v с минимальной глубиной, K-покрытие каждой вершины из <math>N_v - \{ v \} \;</math> с минимальной глубиной уже известно, и высоту разреза можно легко определить. Именно так работает первый этап алгоритма FlowMap. | |||
'''Вычисление K-допустимого разреза минимальной высоты''' | |||
Первый этап работы алгоритма FlowMap изначально был назван этапом [[разметка графа|разметки]], так как он включает вычисление метки для каждой вершины K-ограниченного графа. Метка не являющейся первичным входом вершины v, обозначаемая как l(v), определяется как минимальная высота любого разреза по v. Для удобства метки вершин, являющихся первичными входами, считаются равными 0. | |||
Определенные таким образом метки обладают важным свойством ''монотонности''. | |||
'''Лемма 3'''. Пусть <math>p = max \{ l(u): u \in input(v) \} \;</math>. Тогда <math>p \le l(v) \le p + 1 \;</math>. | |||
Заметим, что из этого также следует, что для любой вершины <math>u \in N_v - \{ v \} \;</math> верно <math>l(u) \le p \;</math>. Основываясь на этом наблюдении, для поиска K-допустимого разреза минимальной высоты достаточно проверить, существует ли разрез с высотой p; если нет, то любой K-допустимый разрез будет иметь минимальную высоту (p + 1), и один такой разрез всегда существует для K-ограниченного графа. | |||
Поиск K-допустимого разреза высоты (p > 0; случай p = 0 является тривиальным) в алгоритме FlowMap выполняется посредством преобразования <math>N_v \;</math> в ''транспортную сеть'' <math>F_v \;</math> и вычисления потока в этой сети [4] (отсюда и название). Преобразование выполняется следующим образом. Для каждой вершины <math>u \in N_v - \{ v \}, l(u) < p \;</math>, в <math>F_v \;</math> имеются две вершины <math>u_1 \;</math> и <math>u_2 \;</math>, связанные ''мостовым ребром'' <math>\langle u_1, u_2 \rangle</math>; <math>F_v \;</math> содержит единственную ''вершину-сток'' t для всех остальных вершин в <math>N_v \;</math> и единственную ''вершину-источник'' s. Для каждой вершины u из <math>N_v \;</math>, являющейся первичным входом, которая соответствует мостовому ребру <math>\langle u_1, u_2 \rangle</math> в <math>F_v \;</math>, <math>F_v \;</math> содержит ребро <math>\langle s, u_1 \rangle</math>; для каждого ребра <math>\langle u, w \rangle</math> и <math>N_v \;</math> в случае, если и u, и w имеют мостовые ребра в <math>F_v \;</math>, <math>F_v \;</math> содержит ребро <math>\langle u_2, w_1 \rangle</math>; если u имеет мостовое ребро, а w не имеет, <math>F_v \;</math> содержит ребро edge <math>\langle u_2, t \rangle</math>; в противном случае (если ни у одной вершины не имеется мостового ребра) <math>F_v \;</math> не содержит соответствующего ребра. Мостовые ребра имеют единичную пропускную способность; все прочие ребра имеют бесконечную пропускную способность. Если заметить, что каждое ребро в <math>F_v \;</math> с бесконечной (или единичной) пропускной способностью соответствует вершине <math>u \in N_v \;</math> с l(u) < p и наоборот, и вспомнить теорему о максимальном потоке и минимальном сечении [4], можно показать справедливость следующей леммы. | |||
'''Лемма 4'''. Вершина v содержит K-допустимый разрез высоты p в том и только том случае, если значение максимального потока в сети <math>F_v \;</math> не превышает K. | |||
Зная поток в сети <math>F_v \;</math>, можно вычислить максимальный поток при помощи алгоритма нахождения дополняющего пути [4]. После вычисления максимального потока ''оставшийся граф'' сети потока отключается, и соответствующий ''минимальный разрез'' (X, X') определяется следующим образом: <math>v \in X' \;</math> ; для <math>u \in N_v - \{ v \} \;</math>, если оно является мостовым множеством в <math>F_v \;</math> и <math>u_1 \;</math> может быть достигнуто при помощи поиска в глубину по оставшемуся графу из s, то <math>u \in X \;</math> ; в противном случае <math>u \in X' \;</math>. | |||
Заметим, что как только величина потока превысит K, вычисление может остановиться, зная, что в этом случае нужного K-допустимого разреза найти не удастся. В этом случае можно модифицировать сеть потока, связав мостами все вершины в <math>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>Y' \subseteq X'</math>. | |||
Интуитивно понятно, что разрез большего объема определяет конус большей величины, охватывающий больше логики, в силу чего разрез большего объема является более предпочтительным. Однако заметим, что лемма 5 говорит только о максимуме среди минимальных разрезов; если n(X, X') < K, то могут существовать другие разрезы, все еще являющиеся K-допустимыми, но имеющие большую величину и больший объем. Алгоритм постобработки, используемый FlowMap, пытается увеличить (X, X') за счет коллапсирования всех вершин из X', а также одной или нескольких вершин в сечении, в сток и последующего повторного вычисления потока; это приводит к получению разреза большего объема и оказывается выигрышным, если разрез по-прежнему остается K-допустимым. | |||
'''Построение K-покрытия''' | |||
После того как K-допустимые разрезы минимальной высоты были найдены для всех вершин, каждой вершине оказывается сопоставлен K-допустимый конус <math>C_v \;</math>, определяемый ее разрезом, имеющим минимальную глубину. После этого построение K-покрытия <math>N_M = (V_M, E_M) \;</math> является тривиальным. Во-первых, в <math>V_M \;</math> включаются все вершины, являющиеся первичными выходами. Затем для любого конуса <math>C_v \in V_M \;</math> конус <math>C_u \;</math> для каждой не являющейся первичным входом вершины <math>u \in input(v) \;</math> также включается в <math>V_M \;</math>, равно как и каждая являющаяся первичным входом вершина <math>u \in input(v) \;</math>. Точно так же <math>\langle C_u, C_v \rangle \in E_M</math> для каждой не являющейся первичным входом вершины <math>u \in input(C_v) \;</math>; <math>\langle u, C_v \rangle \in E_M</math> для каждой являющейся первичным входом вершины <math>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) |
правок