Технологическое отображение последовательной схемы: различия между версиями

В [7] был представлен другой алгоритм, который использовал преимущество знания того факта, что на практике K является небольшим целым числом, обычно от 3 до 6. Алгоритм выполняет перечисление всех K-входовых конусов для каждого вентиля. Он может учитывать другие целевые показатели оптимизации (например, площадь и мощность) и может применяться к стандартным библиотекам логических элементов.

Булева сеть может быть представлена в виде ориентированного графа со взвешенными ребрами, вершинами которого являются логические вентили, первичные входы и первичные выходы. Существует ориентированное ребро (u, v) с весом d, если u, после прохода через d триггеров, воздействует на v.

Логический конус для вершины может быть представлен в виде разреза, состоящего из входов конуса. Элемент разреза для v состоит из задающей вершины u и суммарного веса d на путях из u в v, обозначаемого <math>u^d</math>. Если u достигает v по нескольким путям с разным числом вентилей, u будет входить в разрез несколько раз с разными значениями d. К примеру, для конуса для z на рис 2 (2) соответствующий разрез будет иметь вид <math>\{ z^1, a^1, b^1 \}</math>. Разрез размера K называется K-разрезом.

где <math>c^{d_i}_i = \{ u^{d + d_i} | u^d \in c_i \}</math> для i = 1.. t. Очевидно, что <math>merge(C(u_1), ..., C(u_t))</math> является множеством K-разрезов для v.

Если в сети N не имеется циклов, K—разрезы для всех вершин можно определить при помощи операции слияния merge в топологическом порядке, начиная с первичных входов. Для сетей общего вида на рис. 3 представлена процедура итеративного вычисления разрезов, предложенная в работе [7].

В работе [7] были предложены некоторые техники для ускорения работы процедуры. С их помощью все 4-разрезы для каждой из эталонных схем ISCAS89 могут быть найдены не более чем за пять итераций.

Процедура разметки стремится найти метку для каждой вершины, как схематически показано на рис. 5, где <math>w_v</math> обозначает вес кратчайших пар из первичных входов к вершине v.

После того успешного вычисления меток для всех вершин можно построить отображение, начиная с первичных выходов. В каждой вершине v процедура выбирает разрез, реализующий метку вершины, а затем переходит к выбору разреза для u, если <math>u^d</math> входит в состав разреза, выбранного для v. На ребре, идущем из таблицы LUT для u к LUT для v, добавляется d триггеров. Для схемы на рис. 1 (1) сгенерированное отображение, основанное на метках, найденных на рис. 6, представляет собой сеть на рис. 2 (2).

Для получения отображения с целевой продолжительностью цикла <math>\varphi</math> таблица LUT для v может быть ресинхронизирована на <math>| l(v) / \phi |</math>. Для схемы на рис. 1 (1) окончательное отображение после ресинхронизации представлено на рис. 2 (3).