Кластеризация на основе эффективности
Ключевые слова и синонимы
Разбиение схем; кластеризация схем
Постановка задачи
Процесс разбиения схемы заключается в разделении схемы на фрагменты, каждый из которых может быть реализован как отдельный компонент (например, чип), удовлетворяющий конструктивным ограничениям. Раджамаран и Вонг [5] рассматривают задачу разделения схемы на компоненты в соответствии с ограничениями по площади – такими как минимизация максимальной задержки на выходе.
Комбинационная схема может быть представлена в виде ориентированного ациклического графа G = (V, E), где V – множество вершин, а E – множество ориентированных ребер. Каждая вершина представляет вентиль в сети, а каждое ребро (u, v) из множества E – взаимосвязь между вентилями u и v в сети. Обозначим за fanin («разветвление на входе») вершины количество инцидентных ей входящих дуг, а за fanout («разветвление на выходе») – количество инцидентных ей исходящих дуг. Первичным входом (primary input, PI) является вершина с fanin = 0, а первичным выходом (primary output, PO) – вершина с fanout = 0. С каждой вершиной ассоциированы вес и задержка.
Определение 1. Кластеризация сети G = (V, E) представляет собой тройку [math]\displaystyle{ (H, \phi,\Sigma) \; }[/math], где
1. H = (V', E') – ориентированный ациклический граф;
2. [math]\displaystyle{ \phi \; }[/math] – функция, отображающая V' на V, такая, что
• для любого ребра [math]\displaystyle{ (u', v') \in E' \; }[/math],[math]\displaystyle{ (\phi (u'), \phi (v')) \in E \; }[/math],
• для любой вершины [math]\displaystyle{ v' \in V' \; }[/math] и ребра [math]\displaystyle{ (u, \phi (v')) \in E \; }[/math] существует уникальный элемент [math]\displaystyle{ u' \in V' \; }[/math], такой, что [math]\displaystyle{ \phi (u') = u \; }[/math] и [math]\displaystyle{ (u', v') \in E' \; }[/math].
• Для любой вершины-первичного выхода [math]\displaystyle{ v \in V \; }[/math] существует уникальный элемент [math]\displaystyle{ v' \in V' \; }[/math], такой, что [math]\displaystyle{ \phi (v') = v \; }[/math].
3. [math]\displaystyle{ \Sigma \; }[/math] – разбиение V'.
Пусть [math]\displaystyle{ \Gamma = (H= (V', E'), \phi, \Sigma) \; }[/math] – кластеризация G. Для [math]\displaystyle{ v \in V, v' \in V' \; }[/math], в случае, если [math]\displaystyle{ \phi (v') = v \; }[/math], мы называем v' копией v. Множество V' состоит из всех копий вершин из V, встречающихся в кластеризации. Вершина v' является первичным входом (первичным выходом, соответственно) кластеризации [math]\displaystyle{ \Gamma \; }[/math], если [math]\displaystyle{ \phi (v') \; }[/math] является первичным входом (первичным выходом) сети G. Из определения [math]\displaystyle{ \phi \; }[/math] следует, что H логически эквивалентна G.
Веса и задержки отдельных вершин G позволяют определить веса и задержки вершин H' и задержку для кластеризации [math]\displaystyle{ \Gamma \; }[/math]. Вес (соответственно, задержка) вершины v' в V' равен весу (задержке) [math]\displaystyle{ \phi (v) \; }[/math]. Вес любого кластера [math]\displaystyle{ C \in \Sigma \; }[/math], обозначаемый W(C), равен сумме весов вершин C. Задержка кластеризации определяется согласно обобщенной модели задержки, предложенной Мургаи и коллегами [3]: задержка ребра [math]\displaystyle{ (u', v') \in E' \; }[/math] равна D (заданному параметру), если u' и v' принадлежат к разным элементам [math]\displaystyle{ \Sigma \; }[/math], и нулю в противном случае. Задержка по пути в H' равна сумме задержек ребер, составляющих путь. Наконец, задержка [math]\displaystyle{ \Gamma \; }[/math] равна задержке пути в H', имеющего максимальную задержку среди всех путей из PI в PO по H'.
Определение 2. Пусть дана комбинационная сеть G = (V, E) с весовой функцией [math]\displaystyle{ w: V \to R^+ \; }[/math], весовой емкостью M и функцией задержки [math]\displaystyle{ \delta: V \to R^+ \; }[/math]. Мы говорим, что кластеризация [math]\displaystyle{ \Gamma = (H, \phi, \Sigma ) \; }[/math] является допустимой, если для каждого кластера [math]\displaystyle{ C \in \Sigma \; }[/math] значение W(C) не превышает M. Задача кластеризации схемы заключается в вычислении допустимой кластеризации [math]\displaystyle{ \Gamma \; }[/math] сети G, такой, что задержка [math]\displaystyle{ \Gamma \; }[/math] минимальна среди всех допустимых кластеризаций G.
В одной из первых работ по этой теме Лоулер и коллеги [2] предложили алгоритм с полиномиальным временем выполнения для задачи кластеризации схемы в специальном случае, когда все вентильные задержки равны нулю (т.е. [math]\displaystyle{ \delta (v) = 0 \; }[/math] для всех v).
Основные результаты
Раджамаран и Вонг [5] предложили оптимальный алгоритм с полиномиальным временем выполнения для задачи кластеризации схемы с применением обобщенной модели задержки.
Теорема 1. Существует алгоритм, вычисляющий оптимальную кластеризацию для задачи кластеризации схемы за время [math]\displaystyle{ O(n^2 log \; n + nm) }[/math], где n и m – количество вершин и ребер заданной комбинационной сети, соответственно.
Данный результат может быть расширен для вычисления оптимальных кластеризаций с учетом любых монотонных ограничений кластеризации. Ограничение кластеризации является монотонным, если любое подключенное подмножество вершин допустимого кластера также является монотонным [2].
Теорема 2. Для задачи кластеризации схемы может быть найдено оптимальное решение с учетом любых монотонных ограничений кластеризации за время, полиномиальное относительно размера схемы.
Применение
Разбиение (кластеризация) схем является важным компонентом процесса проектирования сверхбольших интегральных схем. Одним из вариантов применения этой задачи может быть реализация схемы на нескольких чипах программируемых пользователем вентильных матриц. В работе Раджамарана и Вонга основное внимание было уделено кластеризации комбинационных схем с целью минимизации задержек с учетом ограничений по площади. В родственных работах рассматривались другие важные ограничения – например, ограничения по распиновке [1] и комбинация ограничений по площади и по распиновке [6]. Также рассматривалась кластеризация последовательных схем (а не только комбинационных) с целью минимизации длительности такта [4].
Экспериментальные результаты
Раджамаран и Вонг представили на Международном симпозиуме по схемам и системам результаты экспериментов на пяти схемах с количеством вершин от 196 до 913, а также показатели максимальных задержек кластеризации и времени выполнения алгоритма на рабочей станции Sun Sparc.
См. также
Литература
1. Cong, J., Ding, Y.: An optimal technology mapping algorithm for delay optimization in lookup-table based fpga design. In: Proceedings of IEEE International Conference on Computer-Aided Design, 1992, pp. 48-53
2. Lawler, E.L., Levitt, K.N., Turner, J.: Module clustering to minimize delay in digital networks. IEEE Trans. Comput. C-18, 47- 57(1966)
3. Murgai, R., Brayton, R.K., Sangiovanni-Vincentelli, A.: On clustering for minimum delay/area. In: Proceedings of IEEE International Conference on Computer-Aided Design, 1991, pp. 6-9
4. Pan, P., Karandikar, A.K., Liu, C.L.: Optimal clock period clustering for sequential circuits with retiming. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 17,489^98 (1998)
5. Rajaraman, R., Wong, D.F.: Optimum clustering for delay minimization. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 14, 1490-1495(1995)
6. Yang, H.H., Wong, D.F.: Circuit clustering for delay minimization under area and pinconstraints. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 16,976-986 (1997)