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

Задача заключается в эффективном определении ограниченных положений объектов при минимизации меры взаимодействия между ними, как при физическом монтаже интегральных схем, и обычно выполняется в двух измерениях. Хотя большинство формулировок являются 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> – связи между модулями. Каждая пара вершин и инцидентное им гиперребро связаны при помощи выводов, в сумме в гиперграфе имеется 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, выпуклой, но не строго выпуклой. Среди многих целевых функций, используемых для компоновки схемы, эта является самой простой и распространенной.

2. '''Неподвижные контуры'''. Каждая вершина <math>v_i \in V_h \;</math> должна быть размещена строго внутри обозначенной прямоугольной области, ограниченной координатами <math>x_{min} (_{ymin}) \;</math> и <math>x_{max} (_{ymax}) \;</math>, определяющими левую (нижнюю) и правую (верхнюю) границы обозначенной области.