4430
правок
Компоновка схемы: различия между версиями
Материал из WEGA
м
→Наборы данных
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Наборы данных) |
||
| (не показано 18 промежуточных версий этого же участника) | |||
| Строка 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 является кусочно-линейной, сепарабельной по | Пусть <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, выпуклой, но не строго выпуклой. Среди многих целевых функций, используемых для компоновки схемы, эта является самой простой и распространенной. | ||
| Строка 18: | Строка 18: | ||
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>. | 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} ( | 2. '''Неподвижные контуры'''. Каждая вершина <math>v_i \in V_h \;</math> должна быть размещена строго внутри обозначенной прямоугольной области, ограниченной координатами <math>x_{min} (y_{min}) \;</math> и <math>x_{max} (y_{max}) \;</math>, определяющими левую (нижнюю) и правую (верхнюю) границы обозначенной области. | ||
3. '''Дискретные порты'''. Имеется конечное число дискретных позиций, обычно представленных на решетке. Однако при проектировании топологии крупномасштабных схем ограничения на порты нередко игнорируются в процессе ''глобального размещения'' и накладываются только на этапе ''легализации'' и ''размещения деталей''. | 3. '''Дискретные порты'''. Имеется конечное число дискретных позиций, обычно представленных на решетке. Однако при проектировании топологии крупномасштабных схем ограничения на порты нередко игнорируются в процессе ''глобального размещения'' и накладываются только на этапе ''легализации'' и ''размещения деталей''. | ||
| Строка 47: | Строка 47: | ||
Техника ''компоновки с минимальным разрезом'' основана на сбалансированном разбиении гиперграфа с минимальным разрезом и уделяет больше внимания ограничениям плотности [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> времени, она способна обрабатывать гиперграфы с миллионами вершин за несколько часов. | Техника ''компоновки с минимальным разрезом'' основана на сбалансированном разбиении гиперграфа с минимальным разрезом и уделяет больше внимания ограничениям плотности [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> времени, она способна обрабатывать гиперграфы с миллионами вершин за несколько часов. | ||
| Строка 62: | Строка 62: | ||
Квадратичная компоновка (только по размерности x) задается формулой | Квадратичная компоновка (только по размерности x) задается формулой | ||
(1) <math>\Phi(x) = \sum_{i,j} w_{ij} [(x_i - x_j)^2] = \frac{1}{2} x^T | (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), вычисляя | Качество компоновки при помощи квадратичных алгоритмов может оказаться невысоким. Для аппроксимации линейной целевой функции можно итеративно решить уравнение (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)''' | ||
Функция HPWL может быть доказуемо аппроксимирована строго выпуклыми и дифференцируемыми функциями. Для 2-точечных гиперребер можно применять / | Функция 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]. | ||
| Строка 127: | Строка 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). | ||
== См. также == | == См. также == | ||
