Просмотр кода страницы Кластеризация на основе эффективности

== Ключевые слова и синонимы ==
'''Кластеризация на основе эффективности --- ''Performance-Driven Clustering'''''

Разбиение схемы (''Circuit partitioning''); кластеризация схемы (''Circuit clustering'')

== Постановка задачи ==
Процесс разбиения схемы заключается в разделении схемы на фрагменты, каждый из которых может быть реализован как отдельный компонент (например, чип), удовлетворяющий конструктивным ограничениям.
Раджамаран и Вонг [5] рассматривают задачу разделения схемы на компоненты в соответствии с ограничениями по площади – такими как минимизация максимальной задержки на выходе.



Комбинационная схема (''combinational circuit'') может быть представлена в виде ориентированного ациклического графа 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>(H, \phi,\Sigma) \;</math>, где

1.	H = (V', E') – ориентированный ациклический граф;

2.	<math>\phi \;</math> – функция, отображающая V' на V, такая, что

•	для любого ребра <math>(u', v') \in E' \;</math>,<math>(\phi (u'), \phi (v')) \in E \;</math>,

•	для любой вершины <math>v' \in V' \;</math> и ребра <math>(u, \phi (v')) \in E \;</math> существует уникальный элемент <math>u' \in V' \;</math>, такой, что <math>\phi (u') = u \;</math> и <math>(u', v') \in E' \;</math>.

•	Для любой вершины-первичного выхода <math>v \in V \;</math> существует уникальный элемент <math>v' \in V' \;</math>, такой, что <math>\phi (v') = v \;</math>.

3.	<math>\Sigma \;</math> – разбиение V'.


Пусть <math>\Gamma = (H= (V', E'), \phi, \Sigma) \;</math> – кластеризация G. Для <math>v \in V, v' \in V' \;</math>, в случае, если <math>\phi (v') = v \;</math>, мы называем v' ''копией'' v. Множество V' состоит из всех копий вершин из V, встречающихся в кластеризации. Вершина v' является первичным входом (первичным выходом, соответственно) кластеризации <math>\Gamma \;</math>, если <math>\phi (v') \;</math> является первичным входом (первичным выходом) сети G. Из определения <math>\phi \;</math> следует, что H логически эквивалентна G.


Веса и задержки отдельных вершин G позволяют определить веса и задержки вершин H' и задержку для кластеризации <math>\Gamma \;</math>. Вес (соответственно, задержка) вершины v' в V' равен весу (задержке) <math>\phi (v) \;</math>. Вес любого кластера <math>C \in \Sigma \;</math>, обозначаемый W(C), равен сумме весов вершин C. Задержка кластеризации определяется согласно обобщенной модели задержки, предложенной Мургаи и коллегами [3]: задержка ребра <math>(u', v') \in E' \;</math> равна D (заданному параметру), если u' и v' принадлежат к разным элементам <math>\Sigma \;</math>, и нулю в противном случае. Задержка по пути в H' равна сумме задержек ребер, составляющих путь. Наконец, задержка <math>\Gamma \;</math> равна задержке пути в H', имеющего максимальную задержку среди всех путей из PI в PO по H'.


'''Определение''' 2. Пусть дана комбинационная сеть G = (V, E) с весовой функцией <math>w: V \to R^+ \;</math>, весовой емкостью M и функцией задержки <math>\delta: V \to R^+ \;</math>. Мы говорим, что кластеризация <math>\Gamma = (H, \phi, \Sigma ) \;</math> является '''допустимой''' (''feasible''), если для каждого кластера <math>C \in \Sigma \;</math> значение W(C) не превышает M. '''Задача кластеризации схемы''' (''circuit clustering problem'')заключается в вычислении допустимой кластеризации <math>\Gamma \;</math> сети G, такой, что задержка <math>\Gamma \;</math> минимальна среди всех допустимых кластеризаций G.


В одной из первых работ по этой теме Лоулер и коллеги [2] предложили алгоритм с полиномиальным временем выполнения для задачи кластеризации схемы в специальном случае, когда все вентильные задержки равны нулю (т.е. <math>\delta (v) = 0 \;</math> для всех v).

== Основные результаты ==
Раджамаран и Вонг [5] предложили оптимальный алгоритм с полиномиальным временем выполнения для задачи кластеризации схемы с применением обобщенной модели задержки.


'''Теорема 1. Существует алгоритм, вычисляющий оптимальную кластеризацию для задачи кластеризации схемы за время <math>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)

[[Категория: Совместное определение связанных терминов]]