Рис. 2. Пример перехода от топологии и множества топологических ограниче-
ний к графу ограничений
СБИС;
U
1
=
{
u
11
, u
12
, . . . , u
1
m
1
}
— множество ребер в графе ограни-
чений (
|
U
1
|
=
m
1
)
.
Каждая вершина графа ограничений соответствует геометрическо-
му объекту в топологии СБИС. Ребро в граф ограничений добавля-
ется в том случае, если необходимо обеспечить выполнение условий
(1) и/или (2) для геометрических объектов
GeO
i
и
GeO
j
. При этом
вес ребра выбирается равным минимальному расстоянию между гео-
метрическими объектами
GeO
i
и
GeO
j
, удовлетворяющему всем за-
данным конструкторско-технологическим ограничениям при условии
выполнения ограничений по заданной схемотехнике.
На рис. 2 приведен пример перехода от топологии и множества
топологических ограничений к графу ограничений.
Построение графа ограничений требует больших вычислительных
ресурсов, так как алгоритм его построения в наихудшем случае имеет
временную сложность
O
(
n
2
)
[5].
Однако построение графа ограничений для всех геометрических
объектов, имеющихся в топологии СБИС, не представляется целесо-
образным, так как конструкторско-технологические ограничения при-
меняются только для близко расположенных геометрических объектов.
В настоящее время наиболее эффективными подходами к построению
Рис. 3. Пример приме-
нения метода сканирую-
щей линии
графа ограничений являются алгоритмы, ба-
зирующиеся на методе отбрасывания тени и
методе сканирующей линии.
Метод сканирующей линии [5] базируется
на построении линии по координате, для кото-
рой строится граф ограничений. На рис. 3 при-
веден пример построения сканирующей ли-
нии. Все геометрические объекты, которые пе-
ресекаются сканирующей линией, добавляют-
ся в список препятствий. Необходимо отме-
тить, что метод сканирующей линии приво-
дит к построению избыточных ребер в графе
ограничений.
82 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2011. № 1
