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

Качество компоновки при помощи квадратичных алгоритмов может оказаться невысоким. Для аппроксимации линейной целевой функции можно итеративно решить уравнение (1), вычисляя <math>w_{ij} = \frac{1}{|x_i - x_j|} \;</math> на каждой итерации. Другим вариантом может быть решение единичной <math>\beta \;</math>-регуляризованной задачи оптимизации, заданной формулой <math>\Phi(\mathbf{x}) = min_x \sum_{i,j} w_{ij} \sqrt{(x_i - x_j)^2 + \beta} , \beta > 0 \;</math> - например, с использованием прямо-двойственного метода Ньютона с квадратичной сходимостью [1].

Функция HPWL может быть доказуемо аппроксимирована строго выпуклыми и дифференцируемыми функциями. Для 2-точечных гиперребер можно применять <math>\beta \;</math>-регуляризацию [1]. Для m-точечного гиперребра (при <math>m \ge 3 \;</math>) можно переформулировать HPWL в виде максимума (по норме <math>l_{\infty} \;</math>) среди всех m(m — 1)/2 попарных расстояний <math>|x_i - x_j| \;</math> и аппроксимировать <math>l_{\infty} \;</math>-норму <math>l_p \;</math>-нормой (p-м корнем из суммы p-х степеней). Это позволяет устранить недифференцируемость при всех значениях, кроме '''0''', что впоследствии убирается при помощи <math>\beta \;</math>-регуляризации. Полученная аппроксимация HPWL задается формулой

(2) <math>HPWL_{p - \beta - reg} (G_h) = \sum_{e_k \in E_h} \bigg( \sum_{i,j \in C_k} |x_i - x_j|^p + \beta \bigg)^{1/p} \;</math>.

которое оценивает сверху функцию HPWL с произвольно малой относительной ошибкой, так как <math>p \to \infty \;</math> и <math>\beta \to 0 \;</math> [7]. Кроме того, HPWL также можно аппроксимировать при помощи функции, задаваемой формулой

(3) <math>HPWL_{log-sum-exp}(G_h) = \alpha \sum_{e_k \in E_h} \bigg[ ln \bigg( \sum_{i \in C_k} exp \bigg( \frac{x_i}{ \alpha} \bigg)  \bigg) + ln \bigg( \sum_{v_i \in C_k} exp \bigg( \frac{- x_i}{ \alpha} \bigg)  \bigg) \bigg] \;</math>.

Базовая идея заключается в использовании постоянных по величине сил f, которые «отталкивают» вершины от перекрытий, и перевычислении сил на нескольких итерациях, отражая изменения в распределении вершин. Для квадратичной компоновки новые условия оптимальности выглядят следующим образом: <math>\mathbf{Q} \mathbf{x} + \mathbf{c} + \mathbf{f} = \mathbf{0} \;</math> [8]. Постоянная по величине сила может изменять компоновку различными способами, добиваясь удовлетворения целевых ограничений плотности. Сила '''f''' вычисляется при помощи дискретной версии уравнения Пуассона.

Целевые ограничения плотности могут удовлетворяться также при помощи штрафной функции. Площадь, присвоенная контейнеру <math>B_{ij} \;</math> вершиной <math>v_i \;</math>, представлена колоколообразной функцией <math>Potential(v_i, B_{ij}) \;</math>. Из-за использования кусочно-линейных квадратичных функций потенциальная функция оказывается невыпуклой, зато гладкой и дифференцируемой [6]. Штрафной член, задаваемый соотношением

В эталонный комплект входят пакеты ICCAD '04 (http://vlsicad. eecs.umich.edu/BK/ICCAD04bench/), ISPD '05 (http://www.sigda.org/ispd2005/contest.htm) и ISPD '06 (http://www.sigda.org/ispd2006/contest. htm). Экземпляры этих эталонных пакетов содержат от 10 тысяч до 2,5 миллионов размещаемых объектов. Также имеются и другие широко используемые пакеты, включая крупномасштабные экземпляры задач компоновки с известными оптимальными решениями (http://cadlab.cs.ucla.edu/~pubbench).