Компоновка схемы
Ключевые слова и синонимы
EDA (автоматизация проектирования); таблица соединений; расположение; компоновка с минимальным разрезом; максимальный поток с минимальной стоимостью; аналитическая компоновка; математическое программирование
Постановка задачи
Задача заключается в эффективном определении ограниченных положений объектов при минимизации меры взаимодействия между ними, как при физическом монтаже интегральных схем, и обычно выполняется в двух измерениях. Хотя большинство ее формулировок являются NP-полными, современные схемы настолько велики, что практичные алгоритмы компоновки должны демонстрировать почти линейные время выполнения и потребность в памяти, но их решения не обязательно являются оптимальными. Ранние приложения для компоновки схем были основаны на имитации отжига, однако последующие исследования привели к разработке более масштабируемых техник, используемых в настоящее время в отрасли автоматизации проектирования электронных приборов и устройств.
Схема моделируется при помощи гиперграфа [math]\displaystyle{ G_h(V_h, E_h) \; }[/math], в котором вершины [math]\displaystyle{ V_h = \{ v_1, ..., v_n \} \; }[/math] представляют логические вентили, стандартные ячейки, более крупные модули или стационарные контактные площадки ввода-вывода, а гиперребра [math]\displaystyle{ E_h = \{ e_1, ..., e_m \} \; }[/math] – связи между модулями. Каждая пара вершин и инцидентное им гиперребро связаны при помощи выводов (pin); в сумме в гиперграфе имеется P выводов. Каждая вершина [math]\displaystyle{ v_i \in V_h \; }[/math] имеет ширину [math]\displaystyle{ w_i \; }[/math], высоту [math]\displaystyle{ h_i \; }[/math] и площадь [math]\displaystyle{ A_i \; }[/math]. Гиперребра также могут быть взвешенными. Пусть дан гиперграф [math]\displaystyle{ G_h \; }[/math]. Алгоритм компоновки схемы ищет центральные позиции [math]\displaystyle{ (x_i, y_i) \; }[/math] для вершин, оптимизирующие целевую функцию гиперграфа на базе заданных ограничений (см. далее). Размещение задается в виде [math]\displaystyle{ \mathbf{x} = (x_1, ..., x_n) \; }[/math] и [math]\displaystyle{ \mathbf{y} = (y_1, ..., y_n) \; }[/math].
Целевая функция
Пусть [math]\displaystyle{ C_k \; }[/math] – набор индексов вершин гиперграфа, инцидентных гиперребру [math]\displaystyle{ e_k \; }[/math]. Полная длина проводов полупериметра (half-perimeter wirelength, HPWL) схемы гиперграфа задается формулой [math]\displaystyle{ HPWL(G_h) = \sum_{e_k \in E_h} HPWL(e_k) = \sum_{e_k \in E_h} [max_{i, j \in C_k} |x_i - x_j| + max_{i, j \in C_k} |y_i - y_j|] \; }[/math]. Функция HPWL является кусочно-линейной, сепарабельной по размерностям x и y, выпуклой, но не строго выпуклой. Среди многих целевых функций, используемых для компоновки схемы, эта является самой простой и распространенной.
Ограничения
1. Перекрытия не допускаются. Площади, занятые любыми двумя вершинами, не могут перекрываться; т.е. [math]\displaystyle{ \forall v_i, v_j \in V_h \; }[/math]должно иметь место либо [math]\displaystyle{ |x_i - x_j| \ge \ \frac{1}{2}(w_i + w_j) \; }[/math], либо [math]\displaystyle{ |y_i - y_j| \ge \ \frac{1}{2}(h_i + h_j) \; }[/math].
2. Неподвижные контуры. Каждая вершина [math]\displaystyle{ v_i \in V_h \; }[/math] должна быть размещена строго внутри обозначенной прямоугольной области, ограниченной координатами [math]\displaystyle{ x_{min} (y_{min}) \; }[/math] и [math]\displaystyle{ x_{max} (y_{max}) \; }[/math], определяющими левую (нижнюю) и правую (верхнюю) границы обозначенной области.
3. Дискретные порты. Имеется конечное число дискретных позиций, обычно представленных на решетке. Однако при проектировании топологии крупномасштабных схем ограничения на порты нередко игнорируются в процессе глобального размещения и накладываются только на этапе легализации и размещения деталей.
Также могут добавляться такие ограничения, как выравнивание, минимальное и максимальное расстояние и другие. Многие техники компоновки временно ослабляют ограничение на перекрытие, заменяя его ограничением плотности во избежание скопления вершин в областях малого размера. Регулярная структура B размера [math]\displaystyle{ m \times n \; }[/math] контейнеров накладывается на неподвижный контур, площади вершин присваиваются контейнерам, расположенным в позициях вершин. Обозначим за [math]\displaystyle{ D_{ij} \; }[/math] плотность контейнера [math]\displaystyle{ B_{ij} \in B \; }[/math], определяемую как общая плотность клеток, присвоенных контейнеру [math]\displaystyle{ B_{ij} \; }[/math], деленная на его емкость. Перекрытие вершин неявно ограничивается условием [math]\displaystyle{ D_{ij} \le K, \forall B_{ij} \in B \; }[/math], для некоторого [math]\displaystyle{ K \le 1 \; }[/math] (целевой показатель плотности).
Задача 1 (компоновка схемы)
Дано: гиперграф схемы [math]\displaystyle{ G_h(V_h, E_h) \; }[/math] и неподвижный контур области размещения.
Требуется: найти положение каждой вершины [math]\displaystyle{ v_i \in V_h \; }[/math], такое, что:
(1) длина проводов минимальна;
(2) ограничения на плотность [math]\displaystyle{ D_{ij} \le K \; }[/math] удовлетворяются для всех [math]\displaystyle{ B_{ij} \in B \; }[/math].
Основные результаты
Неограниченное оптимальное положение единичной размещаемой вершины, связанной с фиксированными вершинами, может быть найдено за линейное время как медиана смежных позиций [8]. Минимизация неограниченной функции HPWL для нескольких размещаемых вершин может быть сформулирована в виде линейной программы [7, 10]. Для каждого [math]\displaystyle{ e_k \in E_h \; }[/math] добавляются переменные [math]\displaystyle{ U_k \; }[/math] и [math]\displaystyle{ L_k \; }[/math] для обозначения верхней и нижней границ. Стоимость [math]\displaystyle{ e_k \; }[/math] (только по размерности x) равна разности между [math]\displaystyle{ U_k \; }[/math] и [math]\displaystyle{ L_k \; }[/math]. Для каждого [math]\displaystyle{ U_k(L_k) \; }[/math] имеется [math]\displaystyle{ p_k \; }[/math] ограничений в виде неравенств, требующих, чтобы его значение не было больше (меньше) позиции каждой вершины [math]\displaystyle{ i \in C_k \; }[/math]. Гиперграф с n вершинами и m гиперребрами представлен линейной программой с n + 2m переменными и 2P ограничениями.
Линейное программирование не отличается высокой масштабируемостью, а интеграция отслеживания ограничений в процесс оптимизации весьма сложна. Также применяются такие подходы, как нелинейная оптимизация и методы на основе разбиения.
Комбинаторные техники минимизации длины проводов
Ограничения, запрещающие перекрытие, являются невыпуклыми и не могут быть напрямую включены в линейную программу для минимизации HPWL. Такая программа решается либо напрямую, либо при помощи двойственной задачи нахождения максимального потока с минимальной стоимостью [12]. Вершины нередко скапливаются в небольших областях с высокой плотностью. Можно ограничить снизу расстояние между близко расположенными вершинами при помощи одного линейного ограничения, зависящего от относительного расположения этих вершин [10]. Полученная задача оптимизации решается инкрементно, процесс повторяется до тех пор, пока не будет достигнута желаемая плотность.
Техника компоновки с минимальным разрезом основана на сбалансированном разбиении гиперграфа с минимальным разрезом и уделяет больше внимания ограничениям плотности [11]. Вначале вершины исходного гиперграфа разбиваются на две группы примерно равного размера. Одна из них присваивается левой половине области размещения, вторая – правой. Разбиение производится при помощи многоуровневой эвристики Фидуччи-Мэтьюза (Multi-level Fiduccia-Mattheyses, MLFM) [9], обеспечивая минимизацию связей между двумя группами вершин (целевая функция сетевого разреза). После этого каждая половина также разбивается, учитывая связи с другой половиной [11]. При работе с крупномасштабными схемами требование равной величины компонентов биразбиения соответствует ограничению плотности, а минимизация разреза – минимизации HPWL. Когда области станут настолько малыми, что в них будет содержаться не более 10 вершин, можно будет найти оптимальные позиции относительно ограничений на дискретные порты при помощи алгоритма ветвления и границ [2]. Задача сбалансированного разбиения гиперграфа является NP-полной [4], однако эвристика MLFM требует [math]\displaystyle{ O((V + E)log \; V) }[/math] времени, а полная процедура компоновки с минимальным разрезом – [math]\displaystyle{ O((V + E)(log \; V)^2) }[/math] времени, она способна обрабатывать гиперграфы с миллионами вершин за несколько часов.
Особый интерес представляет случай одномерной компоновки. Если все вершины имеют одинаковую площадь и среди них нет фиксированных, он превращается в NP-полную задачу минимального линейного ранжирования (MINIMUM LINEAR ARRANGEMENT) [4], которую можно аппроксимировать за полиномиальное время в пределах O(log V), а точно решить для деревьев за время [math]\displaystyle{ O(V^3) \; }[/math], что было показано Яннакакисом. Вышеописанная техника минимального разреза также хорошо работает для родственной NP-полной задачи линейного ранжирования с минимальным разрезом (MINIMUM-CUT LINEAR ARRANGEMENT) [4].
Нелинейная оптимизация
Квадратичная оптимизация и нелинейная оптимизация в целом может работать быстрее линейного программирования и при этом аппроксимировать исходную формулировку с разумной точностью. Гиперграф в таком случае представлен взвешенным графом, в котором [math]\displaystyle{ w_{ij} \; }[/math] представляет вес 2-точечного ребра, соединяющего вершины [math]\displaystyle{ v_i \; }[/math] и [math]\displaystyle{ v_j \; }[/math] во взвешенном графе. Если ребра между вершинами нет, [math]\displaystyle{ w_{ij} = 0 \; }[/math]; в общем случае [math]\displaystyle{ w_{ii} = - \sum_{i \ne j} w_{ij} \; }[/math].
Квадратичная компоновка
Квадратичная компоновка (только по размерности x) задается формулой
(1) [math]\displaystyle{ \Phi(x) = \sum_{i,j} w_{ij} [(x_i - x_j)^2] = \frac{1}{2} \mathbf{x}^T \mathbf{Q}\mathbf{x} + \mathbf{c}^T \mathbf{x} + const }[/math].
Глобальный минимум [math]\displaystyle{ \Phi (x) \; }[/math] можно найти, решив разреженную систему линейных уравнений с симметричной положительно определенной матрицей [math]\displaystyle{ \mathbf{Q} \mathbf{x} + \mathbf{c} = \mathbf{0} \; }[/math] (предполагая, что имеется более одной фиксированной вершины), которая поддается эффективному решению с достаточной точностью при помощи любого числа итеративных алгоритмов решения. Квадратичная компоновка может иметь различные оптимумы в зависимости от модели (клика либо звезда), используемой для представления гиперребер. Однако для k-точечного гиперребра имеет место следующий факт: если вес 2-точечных ребер задается равным [math]\displaystyle{ W_c \; }[/math] в модели с кликой и [math]\displaystyle{ kW_c \; }[/math] в модели со звездой, то для случая квадратичной компоновки эти модели эквивалентны [7].
Линеаризованная квадратичная компоновка
Качество компоновки при помощи квадратичных алгоритмов может оказаться невысоким. Для аппроксимации линейной целевой функции можно итеративно решить уравнение (1), вычисляя [math]\displaystyle{ w_{ij} = \frac{1}{|x_i - x_j|} \; }[/math] на каждой итерации. Другим вариантом может быть решение единичной [math]\displaystyle{ \beta \; }[/math]-регуляризованной задачи оптимизации, заданной формулой [math]\displaystyle{ \Phi^{\beta} (\mathbf{x}) = min_x \sum_{i,j} w_{ij} \sqrt{(x_i - x_j)^2 + \beta} , \beta \gt 0 \; }[/math] - например, с использованием прямо-двойственного метода Ньютона с квадратичной сходимостью [1].
Компоновка с учетом полной длины проводов полупериметра (HPWL)
Функция HPWL может быть доказуемо аппроксимирована строго выпуклыми и дифференцируемыми функциями. Для 2-точечных гиперребер можно применять [math]\displaystyle{ \beta \; }[/math]-регуляризацию [1]. Для m-точечного гиперребра (при [math]\displaystyle{ m \ge 3 \; }[/math]) можно переформулировать HPWL в виде максимума (по норме [math]\displaystyle{ l_{\infty} \; }[/math]) среди всех m(m - 1)/2 попарных расстояний [math]\displaystyle{ |x_i - x_j| \; }[/math] и аппроксимировать [math]\displaystyle{ l_{\infty} \; }[/math]-норму [math]\displaystyle{ l_p \; }[/math]-нормой (p-м корнем из суммы p-х степеней). Это позволяет устранить недифференцируемость при всех значениях, кроме 0, что впоследствии убирается при помощи [math]\displaystyle{ \beta \; }[/math]-регуляризации. Полученная аппроксимация HPWL задается формулой
(2) [math]\displaystyle{ 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]\displaystyle{ p \to \infty \; }[/math] и [math]\displaystyle{ \beta \to 0 \; }[/math] [7]. Кроме того, HPWL также можно аппроксимировать при помощи функции, задаваемой формулой
(3) [math]\displaystyle{ 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],
где [math]\displaystyle{ \alpha \gt 0 \; }[/math] – параметр сглаживания [6]. Обе аппроксимации можно оптимизировать с использованием метода сопряженных градиентов.
Аналитические техники для целевых ограничений плотности
Целевые ограничения плотности являются недифференцируемыми и обычно требуют применения аппроксимации.
Распространение под действием силы
Базовая идея заключается в добавлении постоянных по величине сил f, которые «отталкивают» вершины от перекрытий, и перевычислении сил на нескольких итерациях, отражая изменения в распределении вершин. Для квадратичной компоновки новые условия оптимальности выглядят следующим образом: [math]\displaystyle{ \mathbf{Q} \mathbf{x} + \mathbf{c} + \mathbf{f} = \mathbf{0} \; }[/math] [8]. Постоянная по величине сила может изменять компоновку различными способами, добиваясь удовлетворения целевых ограничений плотности. Сила f вычисляется при помощи дискретной версии уравнения Пуассона.
Распространение с неподвижной точкой
Неподвижная точка f представляет собой псевдовершину с нулевой площадью, зафиксированную в точке [math]\displaystyle{ (x_f, y_f) \; }[/math] и связанную с одной вершиной H(f) в гиперграфе при помощи псевдоребра весом [math]\displaystyle{ w_{f, H(f)} \; }[/math]. Квадратичная компоновка с неподвижной точкой задается формулой [math]\displaystyle{ \Phi(x) = \sum_{i, j} w_{i, j} \; (x_i - x_j)^2 + \sum_f w_{f, H(f)} \; (x_{H(f)} - x_f)^2 }[/math]. Каждая неподвижная точка f вводит квадратичный член [math]\displaystyle{ w_{f, H(f)} \; (x_{H(f)} - x_f)^2 }[/math]. Манипулируя положениями неподвижных точек, можно добиться того, что компоновка будет удовлетворять целевым ограничениям плотности. По сравнению с постоянно действующими силами неподвижные точки повышают контролируемость и стабильность итераций алгоритма компоновки [5].
Обобщенное распространение под действием силы
Уравнение Гельмгольца моделирует процесс диффузии и идеально подходит для распространения вершин [3]. Уравнение Гельмгольца задается выражением
(4) [math]\displaystyle{ \frac{\partial ^2 \phi(x, y)}{\partial x^2} + \frac{\partial ^2 \phi(x, y)}{\partial y^2} - \epsilon \phi(x, y) = D(x, y), (x, y) \in R \frac{\partial \phi}{\partial v} = 0, (x, y) }[/math] на границе R,
где [math]\displaystyle{ \epsilon \gt 0 \; }[/math], v – внешняя единичная нормаль, R представляет неподвижный контур, а D(x,y) – непрерывную функцию плотности. Граничные условия [math]\displaystyle{ \frac{\partial \phi}{\partial v} = 0 \; }[/math] диктуют, чтобы силы, направленные вовне неподвижного контура, были установлены равными нулю – этим данный подход отличается от метода Пуассона, в котором предполагается, что сила становится равной нулю на бесконечности. Значение [math]\displaystyle{ \phi_{i, j} \; }[/math] в центре каждого контейнера [math]\displaystyle{ B_{ij} \; }[/math] вычисляется посредством дискретизации уравнения (4) методом конечных разностей. Ограничения плотности заменяются требованием [math]\displaystyle{ \phi_{ij} = \hat{K}, \; \forall B_{ij} \in B }[/math], где [math]\displaystyle{ \hat{K} \; }[/math] – масштабированный представитель целевой функции плотности K. Задача минимизации длины проводов с учетом сглаженных ограничений плотности может быть решена при помощи алгоритма Узавы. В случае квадратичной функции длины провода этот алгоритм представляет собой обобщение метода распространения под действием силы.
Распространение на основе потенциальной функции
Целевые ограничения плотности могут удовлетворяться также при помощи штрафной функции. Площадь, присвоенная контейнеру [math]\displaystyle{ B_{ij} \; }[/math] вершиной [math]\displaystyle{ v_i \; }[/math], представлена колоколообразной функцией [math]\displaystyle{ Potential(v_i, B_{ij}) \; }[/math]. Из-за использования кусочно-линейных квадратичных функций потенциальная функция оказывается невыпуклой, но гладкой и дифференцируемой [6]. Штрафной член, задаваемый соотношением
(5) [math]\displaystyle{ Penalty = \sum_{B_{ij} \in B} \bigg( \sum_{v_i \in V_h} Potential(v_i, B_{ij}) - K \bigg)^2 \; }[/math]
может сочетаться с аппроксимацией длины проводов, в результате чего получаем неограниченную задачу оптимизации, которая решается при помощи эффективного метода сопряженных градиентов [6].
Применение
Практические варианты применения включают более сложные целевые функции взаимосвязей, такие как задержка схемы, перегруженность маршрутов, рассеяние энергии, плотность мощности и максимальный температурный градиент. Вышеописанные техники адаптированы для решения задач оптимизации с несколькими целевыми функциями. Многие подобные расширения основываются на эвристических распределениях весов сетей, способствующих сокращению некоторых (например, важнейших с точки зрения синхронизации и часто используемых) соединений за счет других. Для уменьшения перегруженности маршрутов используются прогностические карты перегрузок, позволяющие уменьшить ограничение максимальной плотности для компоновки перегруженных областей. Еще одной областью применения является физический синтез, в котором инкрементная компоновка используется для оценки изменений топологии схемы.
Экспериментальные результаты
Компоновка схемы активно изучалась в последние 30 лет, и в этой области было опубликовано множество экспериментальных результатов. Исследования 2003 года продемонстрировали, что инструменты компоновки могут улучшить оптимальные расчеты длины проводов в среднем в 1,41-2,09 раз (в ходе исследований алгоритмы были дополнительно оптимизированы). Во время конкурса по компоновке в 2005 году было достигнуто улучшение расчетов длины проводов в среднем в 1,84 раза при помощи комплекта инструментов компоновки. Конкурс по компоновке 2006 года привел к улучшению расчетов при помощи комплекта инструментов компоновки в среднем в 1,39 раз, при этом использовалась целевая функция, одновременно учитывавшая минимизацию длины проводов, трассируемость и время выполнения. Продолжительность компоновки варьировалась от нескольких минут для небольших экземпляров задачи до нескольких часов – для более масштабных, включавших несколько миллионов переменных.
Наборы данных
В эталонный комплект входят пакеты 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).
См. также
Литература
1. Alpert, C.J., Chan, T., Kahng, A.B., Markov, I.L., Mulet, P.: Faster minimization of linear wirelength for global placement. IEEE Trans. CAD 17(1), 3-13 (1998)
2. Caldwell, A.E., Kahng, A.B., Markov, I.L.: Optimal partitioners and end-case placers for standard-cell layout. IEEE Trans. CAD 19(11),1304-1314(2000)
3. Chan,T., Cong, J., Sze, K.: Multilevel generalized force-directed method for circuit placement. Proc. Intl. Symp. Physical Design. ACM Press, San Francisco, 3-5 Apr 2005. pp. 185-192 (2005)
4. Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial optimization problems and their approximability properties. Springer (1998)
5. Hu, B., Marek-Sadowska, M.: Multilevel fixed-point-addition-based VLSI placement. IEEE Trans. CAD 24(8), 1188-1203 (2005)
6. Kahng, A. B., Wang, Q.: Implementation and extensibility of an analytic placer. IEEE Trans. CAD 24(5), 734-747 (2005)
7. Kennings, A., Markov, I.L.: Smoothing max-terms and analytical minimization of half-perimeter wirelength. VLSI Design 14(3), 229-237 (2002)
8. Kennings, A., Vorwerk, K.: Force-directed methods for generic placement. IEEE Trans. CAD 25(10), 2076-2087 (2006)
9. Papa, D.A., Markov, I.L.: Hypergraph partitioning and clustering. In: Gonzalez, T. (ed.) Handbook of algorithms. Taylor & Francis Group, Boca Raton, CRC Press, pp. 61 -1 (2007)
10. Reda, S., Chowdhary, A.: Effective linear programming based placement methods. In: ACM Press, San Jose, 9-12 Apr 2006
11. Roy, J.A., Adya, S.N., Papa, D.A., Markov, I.L.:Min-cut floorplacement. IEEE Trans. CAD 25(7), 1313-1326 (2006)
12. Tang, X., Tian, R., Wong, M.D.F.: Optimal redistribution of white space for wirelength minimization. In: Tang, T.-A. (ed.) Proc. Asia South Pac. Design Autom. Conf., ACM Press, 18-21 Jan 2005, Shanghai. pp. 412-417 (2005)