График ограничений (макет) - Constraint graph (layout)
В некоторых задачах проектирования топологии интегральных схем возникает необходимость оптимизировать размещение неперекрывающихся объектов на плоскости. В общем, эта проблема чрезвычайно сложна, и для ее решения с помощью компьютерных алгоритмов делаются определенные предположения о допустимых размещениях и операциях, разрешенных при модификации размещения. Графики ограничений фиксируют ограничения относительных перемещений объектов, размещенных на плоскости. Эти графики, разделяя общую идею, имеют разное определение в зависимости от конкретной проектной задачи или ее модели.
Планировка этажей
При планировании этажа модель схемы этажа интегральной схемы представляет собой набор изотетических прямоугольников, называемых «блоками», внутри большего прямоугольника, называемого «границей» (например, « граница микросхемы », « граница ячейки »).
Возможное определение графов ограничений следующее. Граф ограничений для данного плана этажа - это ориентированный граф с набором вершин, являющимся набором блоков плана этажа, и есть ребро от блока b1 до b2 (называемое горизонтальным ограничением), если b1 полностью слева от b2 и есть ребро из блока b1 в b2 (называемое вертикальным ограничением), если b1 полностью ниже b2.
Если рассматриваются только горизонтальные ограничения, получается график горизонтальных ограничений . Если рассматриваются только вертикальные ограничения, получается граф вертикальных ограничений .
Согласно этому определению, граф ограничений может иметь столько же ребер, где n - количество блоков. Поэтому рассматриваются другие, менее плотные графы ограничений. Горизонтальная видимость график представляет собой горизонтальное ограничение графы , в котором горизонтальная ограничение между двумя блоками существует только , если есть сегмент горизонтальной линии , которая соединяет два блока и не пересекаются с другими блоками. Другими словами, один блок является потенциальным «непосредственным препятствием» для перемещения другого по горизонтали. Вертикальная видимость график , определяется таким же образом.
Маршрутизация каналов
Маршрутизация каналов - это задача маршрутизации набора сетей N, которые имеют фиксированные терминалы на двух противоположных сторонах прямоугольника («канала»). В этом контексте горизонтальный граф ограничений - это неориентированный граф с набором вершин N, и две сети соединены ребром тогда и только тогда, когда горизонтальные сегменты трассировки должны перекрываться. В данном примере только цепи 5 и 6 не имеют горизонтального ограничения между собой. Вертикальное ограничение графика является ориентированный граф с множеством вершин N и две сети соединены ребром тогда и только тогда , когда есть два контакта из разных сетей на одной и той же вертикальной линии , и край направлен от сети со штырем на верхней кромке канала. Это направление означает, что эта сеть должна быть проложена по горизонтальной дорожке над горизонтальными дорожками второй сети. В данном примере только цепи 1 и 3 имеют вертикальное ограничение.