4551
правка
Технологическое отображение ППВМ: различия между версиями
Перейти к навигации
Перейти к поиску
Технологическое отображение ППВМ (посмотреть исходный код)
Версия от 10:59, 28 августа 2018
, 28 августа 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 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. | ''Глубина сети'' равна максимальному количеству ребер на самом длинном пути. Решение задачи технологического отображения <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, в которую она входит). | |||
Рисунок 1. Технологическое отображение ППВМ | |||
== Основные результаты == | |||