1294
правки
Кластеризация на основе эффективности: различия между версиями
Материал из WEGA
Кластеризация на основе эффективности (посмотреть исходный код)
Версия от 10:31, 26 ноября 2024
, 26 ноября 2024→Ключевые слова и синонимы
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Разбиение схем; кластеризация схем == Постановка задачи == …») |
KVN (обсуждение | вклад) |
||
| (не показано 20 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
'''Кластеризация на основе эффективности --- ''Performance-Driven Clustering''''' | |||
Разбиение схемы (''Circuit partitioning''); кластеризация схемы (''Circuit clustering'') | |||
== Постановка задачи == | == Постановка задачи == | ||
| Строка 8: | Строка 9: | ||
Комбинационная схема может быть представлена в виде ориентированного ациклического графа G = (V, E), где V – множество вершин, а E – множество ориентированных ребер. Каждая вершина представляет вентиль в сети, а каждое ребро (u, v) из множества E – | |||
Комбинационная схема (''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) | |||
[[Категория: Совместное определение связанных терминов]] | |||
