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

Для проверки этой статьи нужны дополнительные цитаты . Помогите улучшить эту статью , добавив ссылки на надежные источники . Неподтвержденный материал может быть оспорен и удален. Найти источники:  Макет "Constraint graph" – новости  · газеты  · книги  · ученый  · JSTOR ( апрель 2011 г. ) ( Узнайте, как и когда удалять это сообщение )

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

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

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

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

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

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