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