График ограничений (макет)

В некоторых задачах интегральных схем топологии возникает необходимость оптимизации размещения непересекающихся объектов в плоскости. В общем, эта проблема чрезвычайно сложна, и для ее решения с помощью компьютерных алгоритмов делаются определенные предположения о допустимых размещениях и об операциях, разрешенных при модификации размещений. Графики ограничений фиксируют ограничения относительного движения объектов, помещенных в плоскость. Эти графики, хотя и имеют общую идею, имеют разное определение в зависимости от конкретной задачи проектирования или ее модели.

Планировка этажа

В планировании помещения модель плана этажа интегральной схемы представляет собой набор изотетических прямоугольников , называемых «блоками», внутри большего прямоугольника, называемого «границей» (например, « граница микросхемы », « граница ячейки »).

Возможное определение графов ограничений следующее. Граф ограничений для данного плана этажа представляет собой ориентированный граф , набор вершин которого представляет собой набор блоков плана этажа, и существует ребро от блока b1 до b2 (называемое горизонтальным ограничением), если b1 полностью левее b2 и существует ребро. из блока b1 в b2 (так называемое вертикальное ограничение), если b1 полностью ниже b2.

Если учитывать только горизонтальные ограничения, получается граф горизонтальных ограничений . Если учитывать только вертикальные ограничения, получается граф вертикальных ограничений .

Согласно этому определению, граф ограничений может иметь столько, сколько $O(n^{2})$ ребра, где n — количество блоков. Поэтому рассматриваются другие, менее плотные графы ограничений. Граф горизонтальной видимости — это граф горизонтальных ограничений, в котором горизонтальное ограничение между двумя блоками существует только в том случае, если существует горизонтальный сегмент линии, который соединяет два блока и не пересекает другие блоки. Другими словами, один блок является потенциальным «непосредственным препятствием» для перемещения другого по горизонтали. График вертикальной видимости определяется аналогичным образом.

Маршрутизация каналов

Пример маршрутизации канала

Маршрутизация каналов — это задача маршрутизации набора сетей N , имеющих фиксированные терминалы на двух противоположных сторонах прямоугольника («канала»). В этом контексте граф горизонтальных ограничений представляет собой неориентированный граф с множеством вершин N и двумя сетями, соединенными ребром тогда и только тогда, когда горизонтальные сегменты маршрутизации должны перекрываться. В данном примере только сети 5 и 6 не имеют горизонтального ограничения между собой. Граф вертикальных ограничений — это ориентированный граф с множеством вершин N и двумя сетями, соединенными ребром тогда и только тогда, когда на одной вертикальной линии находятся два вывода из разных сетей и ребро направлено от сети с выводом на верхнем ребре. канала. Это направление означает, что эта сеть должна быть проложена по горизонтальной дорожке над горизонтальными дорожками второй сети. В данном примере только сети 1 и 3 имеют ограничение по вертикали.