4551
правка
Кластеризация на основе эффективности: различия между версиями
Перейти к навигации
Перейти к поиску
Кластеризация на основе эффективности (посмотреть исходный код)
Версия от 18:54, 1 апреля 2016
, 1 апреля 2016нет описания правки
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Разбиение схем; кластеризация схем == Постановка задачи == …») |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 9: | Строка 9: | ||
Комбинационная схема может быть представлена в виде ориентированного ациклического графа G = (V, E), где V – множество вершин, а E – множество ориентированных ребер. Каждая вершина представляет вентиль в сети, а каждое ребро (u, v) из множества E – взаимодействие между вентилями u и v в сети. Обозначим за fanin («разветвление на входе») вершины количество инцидентных ей входящих дуг, а за fanout («разветвление на выходе») – количество инцидентных ей исходящих дуг. Первичным входом (primary input, PI) является вершина с fanin = 0, а первичным выходом (primary output, PO) – вершина с fanout = 0. С каждой вершиной ассоциированы вес и задержка. | Комбинационная схема может быть представлена в виде ориентированного ациклического графа 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) представляет собой тройку (Я, ф,И), где | |||
1. H = (V0, E0) – ориентированный ациклический граф; | |||
2. ' – функция, отображающая V0 на V, такая, что | |||
• для любого ребра (u0;v0) 2 Е',(ф(и'),ф(у')) 2 E, | |||
• для любой вершины v0 2 V0 and edge (и,ф(у')) 2 E, | |||
существует уникальный элемент u0 2 V0, такой, что ф(и') = u | |||
апсЦк'У) €£'. | |||
• Для любой вершины-первичного выхода v 2 V существует уникальный элемент | |||
v0 2 V, такой, что ф{у') = v. | |||
3. £ – разбиение V0. | |||
Пусть Г = (H= (У,Е'),ф,Е) – кластеризация G. Для v 2 V, v0 2 V0, в случае, если ф{у') = v, мы называем v0 копией v. Множество V0 состоит из всех копий вершин из V, встречающихся в кластеризации. Вершина v0 является первичным входом (первичным выходом, соответственно) кластеризации Г, если ф{у') является первичным входом (первичным выходом) сети G. Из определения ' следует, что H логически эквивалентна G. | |||
Веса и задержки отдельных вершин G позволяют определить веса и задержки вершин H0 и задержку для кластеризации Г. Вес (соответственно, задержка) вершины v0 в V0 равен весу (задержке) ф(v). Вес любого кластера C 2 £, обозначаемый W(C), равен сумме весов вершин C. Задержка кластеризации определяется согласно обобщенной модели, предложенной Мургаи и коллегами [ ]: Задержка ребра (u0; v0) 2 E0 равна D (заданному параметру), если u0 и V принадлежат к разным элементам S, и нулю в противном случае. Задержка по пути в H0 равна сумме задержек ребер, составляющих путь. Наконец, задержка Г равна задержке пути в H0, имеющего максимальную задержку среди всех путей из PI в PO по H0. | |||
Определение 2. Пусть дана комбинационная сеть G = (V, E) с весовой функцией w: V !>• R+, весовой емкостью M и функцией задержки 8: V !>■ R+. Мы говорим, что кластеризация Г = (Н,ф,Е) является допустимой, если для каждого кластера C 2 S значение W(C) не превышает M. Задача кластеризации схемы заключается в вычислении допустимой кластеризации Г сети G, такой, что задержка Г минимальна среди всех допустимых кластеризаций G. | |||
В одной из первых работ по этой теме Лоулер и коллеги [ ] предложили алгоритм с полиномиальным временем исполнения для задачи кластеризации схемы в специальном случае, когда все вентильные задержки равны нулю (т.е. S(v) = 0 для всех v). | |||
== Основные результаты == | |||
Раджамаран и Вонг [ ] предложили оптимальный алгоритм с полиномиальным временем исполнения для задачи кластеризации схемы с применением обобщенной модели задержки. | |||
Теорема 1. Существует алгоритм, вычисляющий оптимальную кластеризацию для задачи кластеризации схемы за время O(n2 log n + nm), где n и m – количество вершин и ребер заданной комбинационной сети, соответственно. | |||
Результат может быть расширен для вычисления оптимальных кластеризаций с учетом любых монотонных ограничений кластеризации. Ограничение кластеризации является монотонным, если любое подключенное подмножество вершин допустимого кластера также является монотонным [2]. | |||
Теорема 2. Для задачи кластеризации схемы может быть найдено оптимальное решение с учетом любых монотонных ограничений кластеризации за время, полиномиальное относительно размера схемы. | |||
== Применение == | |||
Разбиение (кластеризация) схем является важным компонентом процесса проектирования сверхбольших интегральных схем. Одним из вариантов применения этой задачи может быть реализация схемы на нескольких чипах программируемых пользователем вентильных матриц. В работе Раджамарана и Вонга основное внимание было уделено кластеризации комбинационных схем с целью минимизации задержек с учетом ограничений по площади. В родственных работах рассматривались другие важные ограничения – например, ограничения по распиновке [ ] и комбинация ограничений по площади и по распиновке [ ]. Также рассматривалась кластеризация последовательных схем (а не только комбинационных) с целью минимизации длительности такта [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) | |||