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

 

Комбинационная схема (''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] предложили оптимальный алгоритм с полиномиальным временем выполнения для задачи кластеризации схемы с применением обобщенной модели задержки.

Данный результат может быть расширен для вычисления оптимальных кластеризаций с учетом любых монотонных ограничений кластеризации. Ограничение кластеризации является монотонным, если любое подключенное подмножество вершин допустимого кластера также является монотонным [2].

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

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