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

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

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

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

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

Пример технологического отображения приведен на рис. 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 могут быть найдены не более чем за пять итераций.

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

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

  FindMinLabels(N)	
     foreach вершины v в N do [math]\displaystyle{ l(v) \Leftarrow -w_v \cdot \phi }[/math]
     while (имеются обновления меток) do	
        foreach вершины v в N do	
        [math]\displaystyle{ l(v) \Leftarrow min_{c \in C} \{ max \{ l(u) - d \cdot \phi + 1 | u^d \in c \} \}  }[/math]
        if v является первичным выходом и [math]\displaystyle{ l(v) \gt  \phi }[/math], return «Неуспешно»
     return «Успешно»

Рисунок 5. Процедура разметки

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

Рисунок 6. Пример разметки

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

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

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

Лемма 2. N имеет отображение с продолжительностью цикла [math]\displaystyle{ \varphi }[/math] в том и только том случае, если процедура разметки возвращает значение «Успешно».

Этап отображения

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

Для получения отображения с целевой продолжительностью цикла [math]\displaystyle{ \varphi }[/math] таблица LUT для v может быть ресинхронизирована на [math]\displaystyle{ \lceil l(v) / \phi \rceil - 1 }[/math]. Для схемы на рис. 1 (1) окончательное отображение после ресинхронизации представлено на рис. 2 (3).

Применение

Данный алгоритм может применяться для отображения технологически независимой булевой сети на сеть, состоящую из ячеек из библиотеки логических элементов целевой технологии. Концепция и структура являются достаточно общими для того, чтобы их можно было адаптировать для изучения других оптимизаций схем, таких как кластеризация и реструктуризация последовательных схем.

См. также

• Ресинхронизация схемы
• Технологическое отображение ППВМ
• Технологическое отображение

Литература

1. Cong, J., Ding, Y.: FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs. IEEE Trans. on Comput. Aided Des. of Integr. Circuits and Syst., 13(1), 1-12(1994)

2. Cong, J., Wu, C.: FPGA Synthesis with Retiming and Pipelining for Clock Period Minimization of Sequential Circuits. ACM/IEEE Design Automation Conference (1997)

3. Keutzer, K.: DAGON: Technology Binding and Local Optimization by DAG Matching. ACM/IEEE Design Automation Conference (1987)

4. Leiserson, C.E., Saxe, J.B.: Retiming Synchronous Circuitry. Algorithmica6,5-35(1991)

5. Mishchenko, A., Chatterjee, S., Brayton, R., Ciesielski, M.: An integrated technology mapping environment. International Workshop on Logic Synthesis (2005)

6. Pan, P.: Continuous Retiming: Algorithms and Applications. IEEE International Conference on Computer Design, pp. 116-121. (1997)

7. Pan, P., Lin, C.C.: A New Retiming-based Technology Mapping Algorithm for LUT-based FPGAs. ACM International Symposium on Field-Programmable Gate Arrays (1998)

8. Pan, P., Liu, C.L.: Optimal Clock Period FPGA Technology Mapping for Sequential Circuits. ACM/IEEE Design Automation Conference, June (1996)

9. Pan, P., Liu, C.L.: Optimal Clock Period FPGA Technology Mapping for Sequential Circuits. ACM Trans. on Des. Autom. of Electron. Syst., 3(3), 437-462 (1998)