Компоновка схемы: различия между версиями

Техника ''компоновки с минимальным разрезом'' основана на сбалансированном разбиении гиперграфа с минимальным разрезом и уделяет больше внимания ограничениям плотности [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> времени, она способна обрабатывать гиперграфы с миллионами вершин за несколько часов.