4551
правка
Технологическое отображение последовательной схемы: различия между версиями
Перейти к навигации
Перейти к поиску
Технологическое отображение последовательной схемы (посмотреть исходный код)
Версия от 13:53, 1 апреля 2019
, 1 апреля 2019→Основные результаты
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Интегрированные ресинхронизация и технологическое отобра…») |
Irina (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
== Основные результаты == | == Основные результаты == | ||
Первый алгоритм с полиномиальным временем выполнения для этой задачи был предложен в работах [8, 9]. Улучшенный алгоритм в работе [2] обеспечивал сокращение времени выполнения. Оба этих алгоритма были основаны на вычислении потока с минимальной стоимостью. | |||
В [7] был представлен другой алгоритм, который использовал преимущество знания того факта, что на практике K является небольшим целым числом, обычно от 3 до 6. Алгоритм выполняет перечисление всех K-входовых конусов для каждого вентиля. Он может учитывать другие целевые показатели оптимизации (например, площадь и мощность) и может применяться к стандартным библиотекам логических элементов. | |||
'''Перечисление разрезов''' | |||
Булева сеть может быть представлена в виде ориентированного графа со взвешенными ребрами, вершинами которого являются логические вентили, первичные входы и первичные выходы. Существует ориентированное ребро (u, v) с весом d, если u, после прохода через d триггеров, воздействует на v. | |||
Логический конус для вершины может быть представлен в виде разреза, состоящего из входов конуса. Элемент разреза для v состоит из задающей вершины u и суммарного веса d на путях из u в v, обозначаемого ud. Если u достигает v по нескольким путям с разным числом вентилей, u будет входить в разрез несколько раз с разными значениями d. К примеру, для конуса для z на рис 2 (2) соответствующий разрез будет иметь вид {z1, a1, b1}. Разрез размера K называется K-разрезом. | |||
Пусть (UI, V) – ребро в N с весом di, а C(UI) – множество K-разрезов для ui, for i = 1..: ; t. Обозначим за merge(C(u1)..: ; C(ut)) следующую операцию на множествах: }} U € U ... U dl U...Ucd>\ <K} | |||
где cdii = fud+di jud 2 cig для i = 1.. t. Очевидно, что merge(C(u1).. C(ut)) является множеством K-разрезов для v. | |||
Если в сети N не имеется циклов, K—разрезы для всех вершин можно определить при помощи операции слияния merge в топологическом порядке, начиная с первичных входов. Для сетей общего вида на рис. 3 представлена процедура итеративного вычисления разрезов, предложенная в работе [7]. | |||
На рис. 4 изображены итерации перечисления 3-разрезов для схемы на рис. 1 (1) при слиянии разрезов в порядке i, x, y, z, o. В начале работы каждая вершина имеет собственный тривиальный разрез, включающий ее саму. В ряду 1 представлены новые разрезы, обнаруженные на первой итерации. На второй итерации обнаруживаются еще два новых разреза (для x). После этого выполнение процедуры останавливается, так как последующие слияния не приводят к выявлению новых разрезов. | |||
FindAllCuts(N, K) | FindAllCuts(N, K) | ||
| Строка 39: | Строка 59: | ||
2 {i\x\y2} | 2 {i\x\y2} | ||
Рисунок 4. Пример перечисления разрезов | Рисунок 4. Пример перечисления разрезов | ||
Лемма 1. После не более чем Kn итераций процедура перечисления разрезов найдет K-разрезы для всех вершин в N. | |||
В работе [7] были предложены некоторые техники для ускорения работы процедуры. С их помощью все 4-разрезы для каждой из эталонных схем ISCAS89 могут быть найдены не более чем за пять итераций. | |||
'''Этап разметки''' | |||