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

Схема моделируется при помощи гиперграфа <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> для вершин, оптимизирующие целевую функцию гиперграфа на базе заданных ограничений (см. далее). Размещение задается в виде '''x'''<math> = (x_1, ..., x_n) \;</math> и '''y''' = <math>(y_1, ..., y_n) \;</math>.

1. Перекрытия не допускаются. Площади, занятые любыми двумя вершинами, не могут перекрываться; т.е. должно иметь место либо JXI — Xj\   1   2(wi + wj), либо \Уг~У)\> i(fei+fy),VVi,V,-€  Vh.

2. Неподвижные контуры. Каждая вершина vi 2 Vh должна быть размещена строго внутри обозначенной прямоугольной области, ограниченной координатами xmin (ymin) и xmax (ymax), определяющими левую (нижнюю) и правую (верхнюю) границы обозначенной области.

3. Дискретные порты. Имеется конечное число дискретных позиций, обычно представленных на решетке. Однако при проектировании топологии крупномасштабных схем в процессе глобального размещения ограничения на порты нередко игнорируются и накладываются только на этапе легализации и размещения деталей.

Также могут добавляться такие ограничения, как выравнивание, минимальное и максимальное расстояние и другие. Многие техники компоновки временно ослабляют ограничение на перекрытие, заменяя его ограничением плотности во избежание скопления вершин в областях малого размера. Регулярная структура B размера m x n контейнеров накладывается на неподвижный контур, площади вершин присваиваются контейнерам, расположенным в позициях вершин. Обозначим за Dij плотность контейнера Bij 2 B, определенную как общую плотность клеток, присвоенных контейнеру Bij, деленную на его емкость (пропускную способность?). Перекрытие вершин неявно ограничивается за счет D ij < K; 8Bij 2 B; для некоторого K < 1 (целевой показатель плотности).