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

Схема моделируется при помощи гиперграфа <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>'''x''' = (x_1, ..., x_n) \;</math> и '''y''' = <math>(y_1, ..., y_n) \;</math>.