4430
правок
Технологическое отображение ППВМ: различия между версиями
Материал из WEGA
Технологическое отображение ППВМ (посмотреть исходный код)
Версия от 13:16, 1 апреля 2019
, 1 апреля 2019нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показаны 4 промежуточные версии этого же участника) | |||
| Строка 35: | Строка 35: | ||
На рис. 1 представлены булева сеть, ее ориентированный ациклический граф, покрытие 3-допустимыми конусами и полученная в результате сеть 3-LUT. Как можно заметить, конусы покрытия могут перекрываться; это допустимо и нередко оказывается полезным. (При реализации отображенной сети часть логики, попавшая в перекрытие, будет продублирована для каждой таблицы K-LUT, в которую она входит). | На рис. 1 представлены булева сеть, ее ориентированный ациклический граф, покрытие 3-допустимыми конусами и полученная в результате сеть 3-LUT. Как можно заметить, конусы покрытия могут перекрываться; это допустимо и нередко оказывается полезным. (При реализации отображенной сети часть логики, попавшая в перекрытие, будет продублирована для каждой таблицы K-LUT, в которую она входит). | ||
[[Файл:FPGA_1.png|720px]] | |||
Рисунок 1. Технологическое отображение ППВМ | Рисунок 1. Технологическое отображение ППВМ | ||
| Строка 91: | Строка 94: | ||
'''Лемма''' | '''Лемма 4'''. Вершина v содержит K-допустимый разрез высоты p в том и только том случае, если значение максимального потока в сети <math>F_v \;</math> не превышает K. | ||
| Строка 97: | Строка 100: | ||
Заметим, что как только величина потока превысит K, вычисление может остановиться, зная, что в этом случае нужного K-допустимого разреза найти не удастся. В этом случае можно модифицировать сеть потока, связав мостами все вершины в | Заметим, что как только величина потока превысит K, вычисление может остановиться, зная, что в этом случае нужного K-допустимого разреза найти не удастся. В этом случае можно модифицировать сеть потока, связав мостами все вершины в <math>N_v - \{ v \} \;</math>, что позволит включить вершины u с l(u) = p в вычисление разреза, и найти K-допустимый разрез с высотой p + 1 аналогичным образом. | ||
| Строка 103: | Строка 106: | ||
Теорема 2. В K-ограниченной булевой сети с n вершинами и m ребрами вычисление K-допустимого разреза минимальной высоты для каждой вершины может быть выполнено за время O(Kmn). | '''Теорема 2. В K-ограниченной булевой сети с n вершинами и m ребрами вычисление K-допустимого разреза минимальной высоты для каждой вершины может быть выполнено за время O(Kmn).''' | ||
| Строка 109: | Строка 112: | ||
Лемма 5. Разрез (X, | '''Лемма 5'''. Разрез (X, X'), вычисленный вышеописанным образом, представляет собой уникальный минимальный разрез максимального объема; более того, если (Y, Y') – еще один минимальный разрез, то <math>Y' \subseteq X'</math>. | ||
Интуитивно понятно, что разрез большего объема определяет конус большей величины, охватывающий больше логики, в силу чего разрез большего объема является более предпочтительным. Однако заметим, что лемма 5 говорит только о максимуме среди минимальных разрезов; если n(X | Интуитивно понятно, что разрез большего объема определяет конус большей величины, охватывающий больше логики, в силу чего разрез большего объема является более предпочтительным. Однако заметим, что лемма 5 говорит только о максимуме среди минимальных разрезов; если n(X, X') < K, то могут существовать другие разрезы, все еще являющиеся K-допустимыми, но имеющие большую величину и больший объем. Алгоритм постобработки, используемый FlowMap, пытается увеличить (X, X') за счет коллапсирования всех вершин из X', а также одной или нескольких вершин в сечении, в сток и последующего повторного вычисления потока; это приводит к получению разреза большего объема и оказывается выигрышным, если разрез по-прежнему остается K-допустимым. | ||
Построение K-покрытия | '''Построение K-покрытия''' | ||
После того как 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-покрытие, построенное вышеописанным образом, является оптимальным по глубине. | '''Лемма 6'''. K-покрытие, построенное вышеописанным образом, является оптимальным по глубине. | ||
Эта процедура линейна по времени, следовательно | Эта процедура линейна по времени, следовательно, | ||
Теорема 3. Задача оптимального по глубине технологического отображения для ППВМ на основе таблиц K-LUT на булеву сеть с n вершинами и m ребрами может быть решена за время O(Kmn). | '''Теорема 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) | |||
