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

Одним из ключевых этапов процесса проектирования СБИС является технологическое отображение, которое преобразует булеву сеть технологически инвариантных логических вентилей и 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).

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

В [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 могут быть найдены не более чем за пять итераций.

После получения всех K-разрезов алгоритм оценивает разрезы, основываясь на последовательном времени прихода (или l-значениях), представляющем собой расширение традиционного времени прихода, чтобы рассчитать эффект от ресинхронизации [6,8].

FindMinLabels(N)

foreach node v in N do l(v) <^ w w,-ф

while (имеются обновления меток) do

foreach node v in N do

l(v) ( minc2C(v)fmaxfl(u) – d ф + 1jud ec}}

if v является PO и l(v) > ф, return неуспешно

return успешно

Рисунок 5. Технологическое отображение последовательной схемы. Процедура разметки

0 \{а°} :0 fb0g : 0 {Р} :0 {х0} : -1 {У0}: О {z° } :- 1 fo0g :-1

1 \ {а0} : 1 z1g:0 0 (  0   0

< Q        Q z0g : 1 {о1 б1! :0 fz0g :0

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

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

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

Можно показать, что процедура разметки остановится после не более чем n(n - 1) итераций [ ]. Следующая лемма связывает метки и отображение:

Лемма 2. N имеет отображение с продолжительностью цикла ' в том и только том случае, если процедура разметки возвращает значение «успех».

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

Для получения отображения с целевой продолжительностью цикла ' таблица LUT для v может быть ресинхронизирована на \l{v)l<p~\ — 1. Для схемы на рис. 1 (1) окончательное отображение после ресинхронизации представлено на рис. 2 (3).