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

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

где e > 0, v – внешняя единичная нормаль, R представляет неподвижный контур, а D(x,y) – непрерывную функцию плотности. Граничные условия дф/dv = 0 диктуют, чтобы силы, направленные вовне неподвижного контура, были установлены равными нулю – этим данный подход отличается от метода Пуассона, в котором предполагается, что сила становится равной нулю на бесконечности. Значение ф^ в центре каждой ячейки Bij вычисляется посредством дискретизации уравнения (4) методом конечных разностей. Ограничения плотности заменяются требованием ф{^ = К, У Bij 2 B, где К – масштабированный представитель целевой функции плотности K. Задача минимизации длины проводов с учетом сглаженных ограничений плотности может быть решена при помощи алгоритма Узавы. В случае квадратичной функции длины провода этот алгоритм представляет собой обобщение метода распространения под действием силы.

Целевые ограничения плотности могут удовлетворяться также при помощи штрафной функции. Площадь, присвоенная ячейке Bij вершиной vi, представлена колоколообразной функцией Potential(vi ; Bij). Из-за использования кусочно-линейных квадратичных функций потенциальная функция оказывается невыпуклой, зато гладкой и дифференцируемой [6]. Штрафной член, задаваемый соотношением