4430
правок
Компоновка схемы: различия между версиями
Материал из WEGA
м
→Наборы данных
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Наборы данных) |
||
| (не показано 27 промежуточных версий этого же участника) | |||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача заключается в эффективном определении ограниченных положений объектов при минимизации меры взаимодействия между ними, как при физическом монтаже интегральных схем, и обычно выполняется в двух измерениях. Хотя большинство формулировок являются NP-полными, современные схемы настолько велики, что практичные алгоритмы компоновки должны демонстрировать почти линейные время выполнения и потребность в памяти, но их решения не обязательно являются оптимальными. Ранние приложения для компоновки схем были основаны на имитации отжига, однако последующие исследования привели к разработке более масштабируемых техник, используемых в настоящее время в отрасли автоматизации проектирования электронных приборов и устройств. | Задача заключается в эффективном определении ограниченных положений объектов при минимизации меры взаимодействия между ними, как при физическом монтаже интегральных схем, и обычно выполняется в двух измерениях. Хотя большинство ее формулировок являются NP-полными, современные схемы настолько велики, что практичные алгоритмы компоновки должны демонстрировать почти линейные время выполнения и потребность в памяти, но их решения не обязательно являются оптимальными. Ранние приложения для компоновки схем были основаны на имитации отжига, однако последующие исследования привели к разработке более масштабируемых техник, используемых в настоящее время в отрасли автоматизации проектирования электронных приборов и устройств. | ||
Схема моделируется при помощи гиперграфа <math>G_h(V_h, E_h) \;</math>, в котором вершины <math>V_h = \{ v_1, ..., v_n \} \;</math> представляют логические вентили, стандартные ячейки, более крупные модули или стационарные контактные площадки ввода-вывода, а [[гиперребро|гиперребра]] <math>E_h = \{ e_1, ..., e_m \} \;</math> – связи между модулями. Каждая пара вершин и инцидентное им гиперребро связаны при помощи выводов | Схема моделируется при помощи гиперграфа <math>G_h(V_h, E_h) \;</math>, в котором вершины <math>V_h = \{ v_1, ..., v_n \} \;</math> представляют логические вентили, стандартные ячейки, более крупные модули или стационарные контактные площадки ввода-вывода, а [[гиперребро|гиперребра]] <math>E_h = \{ e_1, ..., e_m \} \;</math> – связи между модулями. Каждая пара вершин и инцидентное им гиперребро связаны при помощи ''выводов'' (pin); в сумме в гиперграфе имеется P выводов. Каждая вершина <math>v_i \in V_h \;</math> имеет ширину <math>w_i \;</math>, высоту <math>h_i \;</math> и площадь <math>A_i \;</math>. Гиперребра также могут быть взвешенными. Пусть дан гиперграф <math>G_h \;</math>. Алгоритм компоновки схемы ищет центральные позиции <math>(x_i, y_i) \;</math> для вершин, оптимизирующие целевую функцию гиперграфа на базе заданных ограничений (см. далее). Размещение задается в виде <math>\mathbf{x} = (x_1, ..., x_n) \;</math> и <math>\mathbf{y} = (y_1, ..., y_n) \;</math>. | ||
Целевая функция | '''Целевая функция''' | ||
Пусть <math>C_k \;</math> – набор индексов вершин гиперграфа, инцидентных гиперребру <math>e_k \;</math>. ''Полная длина проводов полупериметра'' (half-perimeter wirelength, HPWL) схемы гиперграфа задается формулой <math>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>\forall v_i, v_j \in V_h \;</math>должно иметь место либо <math>|x_i - x_j| \ge \ \frac{1}{2}(w_i + w_j) \;</math>, либо <math>|y_i - y_j| \ge \ \frac{1}{2}(h_i + h_j) \; </math>. | |||
2. '''Неподвижные контуры'''. Каждая вершина <math>v_i \in V_h \;</math> должна быть размещена строго внутри обозначенной прямоугольной области, ограниченной координатами <math>x_{min} (y_{min}) \;</math> и <math>x_{max} (y_{max}) \;</math>, определяющими левую (нижнюю) и правую (верхнюю) границы обозначенной области. | |||
3. '''Дискретные порты'''. Имеется конечное число дискретных позиций, обычно представленных на решетке. Однако при проектировании топологии крупномасштабных схем ограничения на порты нередко игнорируются в процессе ''глобального размещения'' и накладываются только на этапе ''легализации'' и ''размещения деталей''. | |||
Также могут добавляться такие ограничения, как выравнивание, минимальное и максимальное расстояние и другие. Многие техники компоновки временно ослабляют ограничение на перекрытие, заменяя его ограничением плотности во избежание скопления вершин в областях малого размера. Регулярная структура B размера <math>m \times n \;</math> контейнеров накладывается на неподвижный контур, площади вершин присваиваются контейнерам, расположенным в позициях вершин. Обозначим за <math>D_{ij} \;</math> плотность контейнера <math>B_{ij} \in B \;</math>, определяемую как общая плотность клеток, присвоенных контейнеру <math>B_{ij} \;</math>, деленная на его емкость. Перекрытие вершин неявно ограничивается условием <math>D_{ij} \le K, \forall B_{ij} \in B \;</math>, для некоторого <math>K \le 1 \;</math> (целевой показатель плотности). | |||
'''Задача 1 (компоновка схемы)''' | |||
Требуется: найти положение каждой вершины | Дано: гиперграф схемы <math>G_h(V_h, E_h) \;</math> и неподвижный контур области размещения. | ||
Требуется: найти положение каждой вершины <math>v_i \in V_h \;</math>, такое, что: | |||
(1) длина проводов минимальна; | |||
(2) ограничения на плотность <math>D_{ij} \le K \;</math> удовлетворяются для всех <math>B_{ij} \in B \;</math>. | |||
== Основные результаты == | == Основные результаты == | ||
Неограниченное оптимальное положение единичной размещаемой вершины, связанной с фиксированными вершинами, может быть найдено за линейное время как медиана смежных позиций [8]. Минимизация неограниченной функции HPWL для нескольких размещаемых вершин может быть сформулирована в виде линейной программы [7, 10]. Для каждого | Неограниченное оптимальное положение единичной размещаемой вершины, связанной с фиксированными вершинами, может быть найдено за линейное время как медиана смежных позиций [8]. Минимизация неограниченной функции HPWL для нескольких размещаемых вершин может быть сформулирована в виде линейной программы [7, 10]. Для каждого <math>e_k \in E_h \;</math> добавляются переменные <math>U_k \;</math> и <math>L_k \;</math> для обозначения верхней и нижней границ. Стоимость <math>e_k \;</math> (только по размерности x) равна разности между <math>U_k \;</math> и <math>L_k \;</math>. Для каждого <math>U_k(L_k) \;</math> имеется <math>p_k \;</math> ограничений в виде неравенств, требующих, чтобы его значение не было больше (меньше) позиции каждой вершины <math>i \in C_k \;</math>. Гиперграф с n вершинами и m гиперребрами представлен линейной программой с n + 2m переменными и 2P ограничениями. | ||
Линейное программирование не отличается высокой масштабируемостью, а интеграция отслеживания ограничений в процесс оптимизации весьма сложна. Также применяются такие подходы, как нелинейная оптимизация и методы на основе разбиения. | Линейное программирование не отличается высокой масштабируемостью, а интеграция отслеживания ограничений в процесс оптимизации весьма сложна. Также применяются такие подходы, как нелинейная оптимизация и методы на основе разбиения. | ||
Комбинаторные техники минимизации длины проводов | '''Комбинаторные техники минимизации длины проводов''' | ||
Ограничения, запрещающие перекрытие, являются невыпуклыми и не могут быть напрямую включены в линейную программу для минимизации HPWL. Такая программа решается либо напрямую, либо при помощи двойственной задачи нахождения максимального потока с минимальной стоимостью [12]. Вершины нередко скапливаются в небольших областях с высокой плотностью. Можно ограничить снизу расстояние между близко расположенными вершинами при помощи одного линейного ограничения, зависящего от относительного расположения этих вершин [ ]. Полученная задача оптимизации решается инкрементно, процесс повторяется до тех пор, пока не будет достигнута желаемая плотность. | Ограничения, запрещающие перекрытие, являются невыпуклыми и не могут быть напрямую включены в линейную программу для минимизации HPWL. Такая программа решается либо напрямую, либо при помощи двойственной задачи нахождения максимального потока с минимальной стоимостью [12]. Вершины нередко скапливаются в небольших областях с высокой плотностью. Можно ограничить снизу расстояние между близко расположенными вершинами при помощи одного линейного ограничения, зависящего от относительного расположения этих вершин [10]. Полученная задача оптимизации решается инкрементно, процесс повторяется до тех пор, пока не будет достигнута желаемая плотность. | ||
Техника компоновки с минимальным разрезом основана на сбалансированном разбиении гиперграфа с минимальным разрезом и уделяет больше внимания ограничениям плотности [ ]. Вначале вершины исходного гиперграфа разбиваются на две группы примерно равного размера. Одна из них присваивается левой половине области размещения, вторая – правой. Разбиение производится при помощи многоуровневой эвристики Фидуччи-Мэтьюза (Multi-level Fiduccia-Mattheyses, MLFM) [ ], обеспечивая минимизацию связей между двумя группами вершин (целевая функция сетевого разреза). После этого каждая половина также разбивается, учитывая связи с другой половиной [11]. При работе с крупномасштабными схемами требование равной величины компонентов биразбиения соответствует ограничению плотности, а минимизация разреза – минимизации HPWL. Когда области станут настолько малыми, что в них будет содержаться не более 10 вершин, можно будет найти оптимальные позиции относительно | Техника ''компоновки с минимальным разрезом'' основана на сбалансированном разбиении гиперграфа с минимальным разрезом и уделяет больше внимания ограничениям плотности [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> времени, она способна обрабатывать гиперграфы с миллионами вершин за несколько часов. | ||
Особый интерес представляет случай одномерной компоновки. Если все вершины имеют одинаковую площадь и среди них нет фиксированных, он превращается в NP-полную задачу минимального линейного ранжирования (MINIMUM LINEAR ARRANGEMENT) [ ], которую можно аппроксимировать за полиномиальное время в пределах O(log V), а точно решить для деревьев за время O( | Особый интерес представляет случай одномерной компоновки. Если все вершины имеют одинаковую площадь и среди них нет фиксированных, он превращается в NP-полную задачу минимального линейного ранжирования (MINIMUM LINEAR ARRANGEMENT) [4], которую можно аппроксимировать за полиномиальное время в пределах O(log V), а точно решить для деревьев за время <math>O(V^3) \;</math>, что было показано Яннакакисом. Вышеописанная техника минимального разреза также хорошо работает для родственной NP-полной задачи линейного ранжирования с минимальным разрезом (MINIMUM-CUT LINEAR ARRANGEMENT) [4]. | ||
Нелинейная оптимизация | '''Нелинейная оптимизация''' | ||
Квадратичная и | Квадратичная оптимизация и нелинейная оптимизация в целом может работать быстрее линейного программирования и при этом аппроксимировать исходную формулировку с разумной точностью. Гиперграф в таком случае представлен взвешенным графом, в котором <math>w_{ij} \;</math> представляет вес 2-точечного ребра, соединяющего вершины <math>v_i \;</math> и <math>v_j \;</math> во взвешенном графе. Если ребра между вершинами нет, <math>w_{ij} = 0 \;</math>; в общем случае <math>w_{ii} = - \sum_{i \ne j} w_{ij} \;</math>. | ||
Квадратичная компоновка | '''Квадратичная компоновка''' | ||
Квадратичная компоновка (только по размерности x) задается формулой | Квадратичная компоновка (только по размерности x) задается формулой | ||
(1) <math>\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>\Phi (x) \;</math> можно найти, решив разреженную систему линейных уравнений с симметричной положительно определенной матрицей <math>\mathbf{Q} \mathbf{x} + \mathbf{c} = \mathbf{0} \;</math> (предполагая, что имеется более одной фиксированной вершины), которая поддается эффективному решению с достаточной точностью при помощи любого числа итеративных алгоритмов решения. Квадратичная компоновка может иметь различные оптимумы в зависимости от модели (клика либо звезда), используемой для представления гиперребер. Однако для k-точечного гиперребра имеет место следующий факт: если вес 2-точечных ребер задается равным <math>W_c \;</math> в модели с кликой и <math>kW_c \;</math> в модели со звездой, то для случая квадратичной компоновки эти модели эквивалентны [7]. | |||
'''Линеаризованная квадратичная компоновка''' | |||
Качество компоновки при помощи квадратичных алгоритмов может оказаться невысоким. Для аппроксимации линейной целевой функции можно итеративно решить уравнение (1), вычисляя <math>w_{ij} = \frac{1}{|x_i - x_j|} \;</math> на каждой итерации. Другим вариантом может быть решение единичной <math>\beta \;</math>-регуляризованной задачи оптимизации, заданной формулой <math>\Phi^{\beta} (\mathbf{x}) = min_x \sum_{i,j} w_{ij} \sqrt{(x_i - x_j)^2 + \beta} , \beta > 0 \;</math> - например, с использованием прямо-двойственного метода Ньютона с квадратичной сходимостью [1]. | |||
'''Компоновка с учетом полной длины проводов полупериметра (HPWL)''' | |||
Функция 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>, | |||
где <math>\alpha > 0 \;</math> – параметр сглаживания [6]. Обе аппроксимации можно оптимизировать с использованием метода сопряженных градиентов. | |||
'''Аналитические техники для целевых ограничений плотности''' | |||
Целевые ограничения плотности являются недифференцируемыми и обычно требуют применения аппроксимации. | |||
'''Распространение под действием силы''' | |||
Базовая идея заключается в добавлении постоянных по величине сил '''f''', которые «отталкивают» вершины от перекрытий, и перевычислении сил на нескольких итерациях, отражая изменения в распределении вершин. Для квадратичной компоновки новые условия оптимальности выглядят следующим образом: <math>\mathbf{Q} \mathbf{x} + \mathbf{c} + \mathbf{f} = \mathbf{0} \;</math> [8]. Постоянная по величине сила может изменять компоновку различными способами, добиваясь удовлетворения целевых ограничений плотности. Сила '''f''' вычисляется при помощи дискретной версии уравнения Пуассона. | |||
'''Распространение с неподвижной точкой''' | |||
Неподвижная точка f представляет собой псевдовершину с нулевой площадью, зафиксированную в точке <math>(x_f, y_f) \;</math> и связанную с одной вершиной H(f) в гиперграфе при помощи псевдоребра весом <math>w_{f, H(f)} \;</math>. Квадратичная компоновка с неподвижной точкой задается формулой <math>\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>w_{f, H(f)} \; (x_{H(f)} - x_f)^2</math>. Манипулируя положениями неподвижных точек, можно добиться того, что компоновка будет удовлетворять целевым ограничениям плотности. По сравнению с постоянно действующими силами неподвижные точки повышают контролируемость и стабильность итераций алгоритма компоновки [5]. | |||
'''Обобщенное распространение под действием силы''' | |||
Уравнение Гельмгольца моделирует процесс диффузии и идеально подходит для распространения вершин [3]. Уравнение Гельмгольца задается выражением | |||
(4) <math>\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>\epsilon > 0 \;</math>, v – внешняя единичная нормаль, R представляет неподвижный контур, а D(x,y) – непрерывную функцию плотности. Граничные условия <math>\frac{\partial \phi}{\partial v} = 0 \;</math> диктуют, чтобы силы, направленные вовне неподвижного контура, были установлены равными нулю – этим данный подход отличается от метода Пуассона, в котором предполагается, что сила становится равной нулю на бесконечности. Значение <math>\phi_{i, j} \;</math> в центре каждого контейнера <math>B_{ij} \;</math> вычисляется посредством дискретизации уравнения (4) методом конечных разностей. Ограничения плотности заменяются требованием <math>\phi_{ij} = \hat{K}, \; \forall B_{ij} \in B</math>, где <math>\hat{K} \;</math> – масштабированный представитель целевой функции плотности K. Задача минимизации длины проводов с учетом сглаженных ограничений плотности может быть решена при помощи алгоритма Узавы. В случае квадратичной функции длины провода этот алгоритм представляет собой обобщение метода распространения под действием силы. | |||
'''Распространение на основе потенциальной функции''' | |||
Целевые ограничения плотности могут удовлетворяться также при помощи штрафной функции. Площадь, присвоенная контейнеру <math>B_{ij} \;</math> вершиной <math>v_i \;</math>, представлена колоколообразной функцией <math>Potential(v_i, B_{ij}) \;</math>. Из-за использования кусочно-линейных квадратичных функций потенциальная функция оказывается невыпуклой, но гладкой и дифференцируемой [6]. Штрафной член, задаваемый соотношением | |||
(5) <math>Penalty = \sum_{B_{ij} \in B} \bigg( \sum_{v_i \in V_h} Potential(v_i, B_{ij}) - K \bigg)^2 \;</math> | |||
(5) | |||
Penalty = | |||
может сочетаться с аппроксимацией длины проводов, в результате чего получаем неограниченную задачу оптимизации, которая решается при помощи эффективного метода сопряженных градиентов [6]. | может сочетаться с аппроксимацией длины проводов, в результате чего получаем неограниченную задачу оптимизации, которая решается при помощи эффективного метода сопряженных градиентов [6]. | ||
| Строка 119: | Строка 125: | ||
== Наборы данных == | == Наборы данных == | ||
В эталонный комплект входят пакеты 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). | В эталонный комплект входят пакеты 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). | ||
== См. также == | == См. также == | ||
