4551
правка
Кластеризация на основе эффективности: различия между версиями
Перейти к навигации
Перейти к поиску
Кластеризация на основе эффективности (посмотреть исходный код)
Версия от 20:21, 1 апреля 2016
, 1 апреля 2016→Постановка задачи
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
Определение 1. Кластеризация сети G = (V, E) представляет собой тройку ( | '''Определение 1.''' Кластеризация сети G = (V, E) представляет собой тройку <math>(H, \phi,\Sigma) \;</math>, где | ||
• для любого ребра ( | 1. H = (V', E') – ориентированный ациклический граф; | ||
• для любой вершины | |||
существует уникальный элемент | 2. <math>\phi \;</math> – функция, отображающая V' на V, такая, что | ||
• Для любой вершины-первичного выхода v | • для любого ребра <math>(u', v') \in E' \;</math>,<math>(\phi (u'), \phi (v')) \in E \;</math>, | ||
3. | • для любой вершины <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'. | |||
| Строка 32: | Строка 34: | ||
Определение 2. Пусть дана комбинационная сеть G = (V, E) с весовой функцией w: V !>• R+, весовой емкостью M и функцией задержки 8: V !>■ R+. Мы говорим, что кластеризация Г = (Н,ф,Е) является допустимой, если для каждого кластера C 2 S значение W(C) не превышает M. Задача кластеризации схемы заключается в вычислении допустимой кластеризации Г сети G, такой, что задержка Г минимальна среди всех допустимых кластеризаций G. | Определение 2. Пусть дана комбинационная сеть G = (V, E) с весовой функцией w: V !>• R+, весовой емкостью M и функцией задержки 8: V !>■ R+. Мы говорим, что кластеризация Г = (Н,ф,Е) является допустимой, если для каждого кластера C 2 S значение W(C) не превышает M. Задача кластеризации схемы заключается в вычислении допустимой кластеризации Г сети G, такой, что задержка Г минимальна среди всех допустимых кластеризаций G. | ||
В одной из первых работ по этой теме Лоулер и коллеги [ ] предложили алгоритм с полиномиальным временем исполнения для задачи кластеризации схемы в специальном случае, когда все вентильные задержки равны нулю (т.е. S(v) = 0 для всех v). | В одной из первых работ по этой теме Лоулер и коллеги [ ] предложили алгоритм с полиномиальным временем исполнения для задачи кластеризации схемы в специальном случае, когда все вентильные задержки равны нулю (т.е. S(v) = 0 для всех v). | ||
== Основные результаты == | == Основные результаты == | ||