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

Комбинаторные техники минимизации длины проводов

Ограничения, запрещающие перекрытие, являются невыпуклыми и не могут быть напрямую включены в линейную программу для минимизации HPWL. Такая программа решается либо напрямую, либо при помощи двойственной задачи нахождения максимального потока с минимальной стоимостью [12]. Вершины нередко скапливаются в небольших областях с высокой плотностью. Можно ограничить снизу расстояние между близко расположенными вершинами при помощи одного линейного ограничения, зависящего от относительного расположения этих вершин [ ]. Полученная задача оптимизации решается инкрементно, процесс повторяется до тех пор, пока не будет достигнута желаемая плотность.

Техника компоновки с минимальным разрезом основана на сбалансированном разбиении гиперграфа с минимальным разрезом и уделяет больше внимания ограничениям плотности [ ]. Вначале вершины исходного гиперграфа разбиваются на две группы примерно равного размера. Одна из них присваивается левой половине области размещения, вторая – правой. Разбиение производится при помощи многоуровневой эвристики Фидуччи-Мэтьюза (Multi-level Fiduccia-Mattheyses, MLFM) [ ], обеспечивая минимизацию связей между двумя группами вершин (целевая функция сетевого разреза). После этого каждая половина также разбивается, учитывая связи с другой половиной [11]. При работе с крупномасштабными схемами требование равной величины компонентов биразбиения соответствует ограничению плотности, а минимизация разреза – минимизации HPWL. Когда области станут настолько малыми, что в них будет содержаться не более 10 вершин, можно будет найти оптимальные позиции относительно ограничений на дискретные порты при помощи алгоритма ветвления и границ [ ]. Задача сбалансированного разбиения гиперграфа является NP-полной [ ], однако эвристика MLFM требует O((V + E)log V) времени, а полная процедура компоновки с минимальным разрезом – O((V + E)(log V)2) времени, она способна обрабатывать гиперграфы с миллионами вершин за несколько часов.