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

Ключевые слова и синонимы

Интегрированные ресинхронизация и технологическое отображение; технологическое отображение с ресинхронизацией

Постановка задачи

Одним из ключевых этапов процесса проектирования СБИС является технологическое отображение, которое преобразует булеву сеть технологически инвариантных логических вентилей и D-триггеров, тактируемых перепадом напряжения (FF) в эквивалентную сеть, состоящую из ячеек из библиотеки логических элементов целевой технологии [1, , 5]. Технологическое отображение может быть сформулировано как задача покрытия, в которой осуществляется покрытие логических вентилей элементами технологической библиотеки. Для простоты изложения предположим, что библиотека содержит только один элемент – таблицу поиска с K логическими входами (K-LUT) с единичной задержкой. Таблица K-LUT может реализовать любую булеву функцию с не более чем K входами, как в случае с высокоэффективными программируемыми пользователем вентильными матрицами (ППВМ, FPGA).

Пример технологического отображения приведен на рис. 1. Для исходной сети на схеме (1) с тремя триггерами и четырьмя вентилями строится покрытие с тремя 3-входовыми конусами, как показано на рис. 1 (2). Соответствующее отображение с использованием таблиц 3-LUT показано на рис. 1 (3). Заметим, что вентиль i покрывается двумя конусами. У отображения на рис. 1 (3) продолжительность цикла (или период цикла) составляет две единицы, что представляет собой совокупную задержку на самом длинном пути между триггерами (FF), от первичных входов (PI) до триггеров и от триггеров до первичных выходов (PO).

Ресинхронизация представляет собой преобразование, которое перемещает триггервы по схеме, сохраняя ее функциональность [4]. Она может повлиять на технологическое отображение. На рис. 2 (1) представлена схема, полученная из схемы на рис. 1 (1) в результате ресинхронизации триггеров на выходах y и i к их входам. Эта схема может быть покрыта всего одним 3-входовым конусом, как показано на рис. 2 (1). Соответствующее отображение, представленное на рис. 2 (2), как с точки зрения синхронизации, так и с точки зрения площади, лучше функционально эквивалентного первого решения на рис. 1 (3), полученного без ресинхронизации.

Рисунок 1. Технологическое отображение: (1) исходная сеть, (2) покрытие, (3) отображение

Рисунок 2. Ресинхронизация и отображение: (1) ресинхронизация и отображение, (2) покрытие, (3) решение после ресинхронизации

K-ограниченной сетью называется сеть, в которой каждый вентиль имеет не более K входов. Задачу технологического отображения последовательной схемы можно определить следующим образом. Пусть даны K-ограниченная булева сеть N и целевая продолжительность цикла [math]\displaystyle{ \varphi }[/math]. Найти отображение с продолжительностью цикла [math]\displaystyle{ \varphi }[/math], предполагая, что допускается перемещение триггеров при помощи ресинхронизации.

Основные результаты

Первый алгоритм с полиномиальным временем выполнения для этой задачи был предложен в работах [8, 9]. Улучшенный алгоритм в работе [2] обеспечивал сокращение времени выполнения. Оба этих алгоритма были основаны на вычислении потока с минимальной стоимостью.

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

Перечисление разрезов

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

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

Пусть [math]\displaystyle{ (u_i, v) }[/math] – ребро в N с весом [math]\displaystyle{ d_i }[/math], а [math]\displaystyle{ C(u_i) }[/math] – множество K-разрезов для [math]\displaystyle{ d_i }[/math], i = 1, ..., t. Обозначим за [math]\displaystyle{ merge(C(u_1), ..., C(u_t)) }[/math] следующую операцию на множествах:

[math]\displaystyle{ \{ \{ v^0 \} \} \cup \{ c^{d_1}_1 \cup ... \cup c^{d_t}_t | c_1 \in C(u_1), ..., c_t \in C(u_t), | c^{d_1}_1 \cup ... \cup c^{d_t}_t | \le K \} }[/math],

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

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

На рис. 4 изображены итерации перечисления 3-разрезов для схемы на рис. 1 (1) при слиянии разрезов в порядке i, x, y, z, o. В начале работы каждая вершина имеет собственный тривиальный разрез, включающий ее саму. В ряду 1 представлены новые разрезы, обнаруженные на первой итерации. На второй итерации обнаруживаются еще два новых разреза (для x). После этого выполнение процедуры останавливается, так как последующие слияния не приводят к выявлению новых разрезов.

  FindAllCuts(N, K)
  foreach вершины v в N do [math]\displaystyle{ C(v) \Leftarrow \{ \{ v^0 \} \} }[/math]
  while (находятся новые разрезы) do
     foreach вершины v в N do [math]\displaystyle{ C(v) \Leftarrow merge(C(u_1), ..., C(u_t)) }[/math]

Рисунок 3. Процедура перечисления разрезов

Итер.	a	b	i	x	y	z	o
0	[math]\displaystyle{ \{ a^0 \} }[/math]	[math]\displaystyle{ \{ b^0 \} }[/math]	[math]\displaystyle{ \{ i^0 \} }[/math]	[math]\displaystyle{ \{ x^0 \} }[/math]	[math]\displaystyle{ \{ y^0 \} }[/math]	[math]\displaystyle{ \{ z^0 \} }[/math]	[math]\displaystyle{ \{ o^0 \} }[/math]
1			[math]\displaystyle{ \{ a^0 \} }[/math]	[math]\displaystyle{ \{ i^1, z^1 \} }[/math] [math]\displaystyle{ \{ a^1, z^1 \} }[/math]	[math]\displaystyle{ \{ i^0, b^0, z^0 \} }[/math] [math]\displaystyle{ \{ a^0, b^0, z^0 \} }[/math]	[math]\displaystyle{ \{ x^0, y^1 \} }[/math] [math]\displaystyle{ \{ i^1, z^1, b^1 \} }[/math] [math]\displaystyle{ \{ a^1, z^1, b^1 \} }[/math] [math]\displaystyle{ \{ i^1, z^1, y^1 \} }[/math] [math]\displaystyle{ \{ a^1, z^1, y^1 \} }[/math]	[math]\displaystyle{ \{ z^0 \} }[/math]
2				[math]\displaystyle{ \{ i^1, x^1, y^2 \} }[/math] [math]\displaystyle{ \{ a^1, x^1, y^2 \} }[/math]

Рисунок 4. Пример перечисления разрезов

Лемма 1. После не более чем Kn итераций процедура перечисления разрезов найдет K-разрезы для всех вершин в N.

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

Этап разметки