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

• для любого ребра (u0;v0) 2 Е',(ф(и'),ф(у')) 2 E,

• для любой вершины v0 2 V0 and edge (и,ф(у')) 2 E,

существует уникальный элемент u0 2 V0, такой, что ф(и') = u

апсЦк'У) €£'.

v0 2 V, такой, что ф{у') = v.

Пусть Г = (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.

 

► Преобразование технологий ППВМ