Кластеризация на основе эффективности: различия между версиями

 

Комбинационная схема (''combinational circuit'') может быть представлена в виде ориентированного ациклического графа G = (V, E), где V – множество вершин, а E – множество ориентированных ребер. Каждая вершина представляет вентиль в сети, а каждое ребро (u, v) из множества E – взаимосвязь между вентилями u и v в сети. Обозначим за fanin («разветвление на входе») вершины количество инцидентных ей входящих дуг, а за fanout («разветвление на выходе») – количество инцидентных ей исходящих дуг. Первичным входом (primary input, PI) является вершина с fanin = 0, а первичным выходом (primary output, PO) – вершина с fanout = 0. С каждой вершиной ассоциированы [[вес вершины|вес]] и [[задержка]].

Веса и задержки отдельных вершин 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] и комбинация ограничений по площади и по распиновке [6]. Также рассматривалась кластеризация последовательных схем (а не только комбинационных) с целью минимизации длительности такта [4].

Раджамаран и Вонг представили на Международном симпозиуме по схемам и системам результаты экспериментов на пяти схемах с количеством вершин от 196 до 913, а также показатели максимальных задержек кластеризации и времени выполнения алгоритма на рабочей станции Sun Sparc.

''[[Технологическое отображение ППВМ]]''