графа противоречий
χ
(
G
)
по формуле [9]
χ
(
G
) =
n
2
n
2
−
2
m
2
.
(7)
При выполнении условия двухцветности графа применяется алго-
ритм раскраски графов. В противном случае исходная топология не
может быть воспроизведена по технологии двойного фотошаблона.
Если граф двухцветен и задача раскраски графа завершена успеш-
но, применяется алгоритм обхода элементов топологии в целях фор-
мирования списка геометрических элементов, подлежащих модифи-
кации. В этот список включаются элементы, которым был присвоен
цвет 2 в ходе раскраски графов. На следующем этапе добавляется
новый слой. Затем список
GeOM
=
{
GeOM
1
, GeOM
2
, . . . , GeOM
k
}
проверяется попарно на выполнение ограничений (3) и (4). Если усло-
вие выполняется, то текущий элемент из списка назначается в от-
дельный слой. На последнем этапе выполняется проверка взаимно-
однозначного соответствия между элементами исходного множества
геометрических объектов и элементами полученных множеств геоме-
трических объектов. В случае корректности проверки на выходе топо-
логия модифицирована таким образом, что выполняются ограничения
(1)–(4).
Предложенный алгоритм применим для проектирования топологии
субмикронных СБИС, удовлетворяющих условиям воспроизведения
по технологии двойного фотошаблона. В частности, к этому классу
топологий относятся флэш-память на основе ячеек NAND, являющая-
ся наиболее подходящей основой для построения энергонезависимых
устройств для хранения больших объемов информации.
Заключение.
Рассмотрены возможные подходы к решению зада-
чи трансформации топологии субмикронных СБИС для технологии
двойного фотошаблона. Показано, что использование графовых моде-
лей позволяет упростить процедуру модификации топологии за счет
формирования и последующего использования графов ограничений и
противоречий. Предложены алгоритмы построения графа противоре-
чий и трансформации топологии СБИС. Указанные алгоритмы могут
быть легко реализованы на основе языков высокого уровня.
Работа выполнена при финансовой поддержке Федеральной целе-
вой программы “Научные и научно-педагогические кадры инновацион-
ной России” на 2009–2013 годы”
(
ГК № П2292
)
.
СПИСОК ЛИТЕРАТУРЫ
1. M o o r e G. Cramming more components onto integrated circuits gordon moore //
Electronics. – 1965. – № 8.
86 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2011. № 1
