4551
правка
Компоновка схемы: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 47: | Строка 47: | ||
Техника ''компоновки с минимальным разрезом'' основана на сбалансированном разбиении гиперграфа с минимальным разрезом и уделяет больше внимания ограничениям плотности [11. Вначале вершины исходного гиперграфа разбиваются на две группы примерно равного размера. Одна из них присваивается левой половине области размещения, вторая – правой. Разбиение производится при помощи многоуровневой эвристики Фидуччи-Мэтьюза (Multi-level Fiduccia-Mattheyses, MLFM) [9], обеспечивая минимизацию связей между двумя группами вершин (целевая функция сетевого разреза). После этого каждая половина также разбивается, учитывая связи с другой половиной [11]. При работе с крупномасштабными схемами требование равной величины компонентов биразбиения соответствует ограничению плотности, а минимизация разреза – минимизации HPWL. Когда области станут настолько малыми, что в них будет содержаться не более 10 вершин, можно будет найти оптимальные позиции относительно ограничений на дискретные порты при помощи алгоритма ветвления и границ [2]. Задача сбалансированного разбиения гиперграфа является NP-полной [4], однако эвристика MLFM требует <math>O((V + E)log V) | Техника ''компоновки с минимальным разрезом'' основана на сбалансированном разбиении гиперграфа с минимальным разрезом и уделяет больше внимания ограничениям плотности [11. Вначале вершины исходного гиперграфа разбиваются на две группы примерно равного размера. Одна из них присваивается левой половине области размещения, вторая – правой. Разбиение производится при помощи многоуровневой эвристики Фидуччи-Мэтьюза (Multi-level Fiduccia-Mattheyses, MLFM) [9], обеспечивая минимизацию связей между двумя группами вершин (целевая функция сетевого разреза). После этого каждая половина также разбивается, учитывая связи с другой половиной [11]. При работе с крупномасштабными схемами требование равной величины компонентов биразбиения соответствует ограничению плотности, а минимизация разреза – минимизации HPWL. Когда области станут настолько малыми, что в них будет содержаться не более 10 вершин, можно будет найти оптимальные позиции относительно ограничений на дискретные порты при помощи алгоритма ветвления и границ [2]. Задача сбалансированного разбиения гиперграфа является NP-полной [4], однако эвристика MLFM требует <math>O((V + E)log \; V)</math> времени, а полная процедура компоновки с минимальным разрезом – <math>O((V + E)(log \; V)^2)</math> времени, она способна обрабатывать гиперграфы с миллионами вершин за несколько часов. | ||
Особый интерес представляет случай одномерной компоновки. Если все вершины имеют одинаковую площадь и среди них нет фиксированных, он превращается в NP-полную задачу минимального линейного ранжирования (MINIMUM LINEAR ARRANGEMENT) [ ], которую можно аппроксимировать за полиномиальное время в пределах O(log V), а точно решить для деревьев за время O( | Особый интерес представляет случай одномерной компоновки. Если все вершины имеют одинаковую площадь и среди них нет фиксированных, он превращается в NP-полную задачу минимального линейного ранжирования (MINIMUM LINEAR ARRANGEMENT) [4], которую можно аппроксимировать за полиномиальное время в пределах O(log V), а точно решить для деревьев за время <math>O(V^3) \;</math>, что было показано Яннакакисом. Вышеописанная техника минимального разреза также хорошо работает для родственной NP-полной задачи линейного ранжирования с минимальным разрезом (MINIMUM-CUT LINEAR ARRANGEMENT) [4]. | ||
Нелинейная оптимизация | '''Нелинейная оптимизация''' | ||
Квадратичная и | Квадратичная оптимизация и нелинейная оптимизация в целом может работать быстрее линейного программирования и при этом аппроксимировать исходную формулировку с разумной точностью. Гиперграф в таком случае представлен взвешенным графом, в котором <math>w_{ij} \;</math> представляет вес 2-точечного ребра, соединяющего вершины <math>v_i \;</math> и <math>v_j \;</math> во взвешенном графе. Если ребра между вершинами нет, <math>w_{ij} = 0 \;</math>; в общем случае <math>w_{ii} = - \sum_{i \ne j} w_{ij} \;</math>. | ||
Квадратичная компоновка | '''Квадратичная компоновка''' | ||
Квадратичная компоновка (только по размерности x) задается формулой | Квадратичная компоновка (только по размерности x) задается формулой | ||
(1) <math>\Phi(x) = \sum_{i,j} w_{ij} [(x_i - x_j)^2] = \frac{1}{2} x^T Qx + c^T x + const</math> | |||
