автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Модели и алгоритмы верификации топологии печатного монтажа

г

На правах рукописи

¿!Г

Лузин Михаил Сергеевич

МОДЕЛИ И АЛГОРИТМЫ ВЕРИФИКАЦИИ ТОПОЛОГИИ ПЕЧАТНОГО МОНТАЖА

Специальность: 05.13.12 - Системы автоматизации проектирования (промышленность)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург -2005

Работа выполнена в Северо-Западном техническом университете.

Научный руководитель -доктор технических наук, профессор Сарвин A.A.

Официальные оппоненты: доктор технических наук, профессор Дмитревич Г.Д. кандидат технических наук, старший научный сотрудник Глинских A.A.

Ведущая организация - Федеральное государственное унитарное предприятие "НИИ "Вектор".

Защита диссертации состоится (Л^КЛ 2005 года в*? часов на заседании диссертационного совета Д 212.238.02 Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» им В.И. Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан " " ЛМХ-& 2005 года.

Учёный секретарь диссертационного совета

Юрков Ю.В.

Ласб-ч

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Сложность радиоэлектронной аппаратуры неуклонно повышается. Не только увеличивается количество элементов на печатной плате или кристалле БИС, но и сами элементы становятся всё более сложными: увеличивается количество внешних контактов микросхем при одновременном уменьшении расстояний между контактами. В результате задача синтеза топологии соединений становится всё более и более трудной.

При проектировании топологии печатных плат (ПП) и интегральных схем (ИС) могут возникнуть ошибки, связанные с потерей соединений, с прокладкой лишних соединений и самое худшее - с изменением соединений. Тогда возникает ситуация, когда общее число связей и элементов соответствует заданному, но схема не работает. Поэтому важно еще до начала этапа изготовления фотошаблонов убедиться, что проектируемое устройство будет выполнять требуемые функции, другими словами, удостовериться, что созданная топология соответствует реализуемой электрической схеме и заданным конструктивно-технологическим ограничениям (КТО).

Существующие подсистемы верификации топологии, входящие в состав представленных на рынке САПР, ориентированы в значительной степени на интерактивную верификацию принципиальной схемы и топологии, что ведет к неоправданно высоким временным затратам. Проверка соблюдения КТО в большинстве САПР осуществляется на ортогональной топологии без дуг окружностей, либо с квадрантными (четверть окружности) дугами. Все это не соответствует современным требованиям к качеству топологии печатного монтажа.

В современных САПР недостаточно используются возможности оптимизации топологии печатного монтажа, связанные с переназначением функционально эквивалентных контактов полузаказных БИС. Поскольку при решении указанной задачи изменяется принципиальная схема устройства, необходимо фиксировать эти изменения и учитывать при решении задачи верификации топологии.

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

- анализ применяемых моделей и алгоритмов верификации

принципиальных схем и топологии узлов РЭС на печатных платах, микросборках и СБИС;

- построение моделей электриче гмых узлов,

адекватных требованиям этапа ве

- разработка эффективного алгоритма определения изоморфности гиперграфов как теоретической основы решения задачи установления соответствия Описания топологии печатного узла его принципиальной схеме;

- разработка методов получения оценки числа пересечений ребер линейной и циклической реализаций двудольного графа;

- разработка методов переназначения функционально эквивалентных вентилей и контактов микросхем на различных этапах проектирования топологии печатного монтажа;

- разработка структур данных и алгоритмов контроля конструктивно-технологических нарушений в топологии печатного монтажа;

- создание и адаптация к промышленным условиям эксплуатации быстродействующих программных средств автоматической верификации топологии узлов РЭС на печатных платах, микросборках и СБИС с использованием функциональной эквивалентности вентилей и контактов компонентов.

Методы исследования. Для решения поставленных задач использовались аппараты теории графов, векторной алгебры и аналитической геометрии, методы оптимизации на графах, исследования операций и искусственного интеллекта.

Научная новизна диссертационной работы заключается:

- в анализе адекватности применяемых моделей и алгоритмов верификации принципиальных схем и топологии узлов РЭС действительным целям задачи верификации;

- в обосновании использования гиперграфовой модели электрической схемы устройства при решении задачи верификации печатных узлов РЭС;

- в разработке алгоритма определения изоморфности гиперграфов;

- в разработке методов оценки числа пересечений ребер линейной и циклической реализаций двудольного графа;

- в разработке методов переназначения функционально эквивалентных вентилей и контактов микросхем на различных этапах проектирования топологии печатного монтажа;

- в разработке эффективных структур данных и алгоритмов для контроля конструктивно-технологических нарушений в топологии печатного монтажа.

Практическая ценность работы состоит в создании прикладных программ, предназначенных для решения задачи верификации топологии печатного монтажа в автоматическом режиме, а также задачи оптимизации назначения функционально эквивалентных вентилей и контактов микросхем для упрощения топологии печатного монтажа. Применение разработанных программ обеспечивает улучшение качества и сокращение сроков проектирования СБИС и печатных узлов РЭС.

Реализация ^езУльтатев -работы. Результаты диссертационной работы в виде конкретных * лолмнелий, выводов, методов, алгоритмов, машинных

программ и расчетных данных внедрены в инженерную практику и используются на промышленных предприятиях Москвы, Санкт-Петербурга и Нижнего Новгорода, а также в учебном процессе СПбГУАП и СПбГЭТУ (ЛЭТИ). Акты, подтверждающие внедрение, приведены в приложении.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и были одобрены на следующих конференциях:

- III Международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 1999г;

- III научно-практической конференции "Современные информационные и электронные технологии", г. Одесса, 2002г.;

- VI международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 2002г.;

- 9-й международной конференции "Современные технологии обучения", С.-Петербург, 2003 г.;

- 4-й международной НПК "Современные информационные и электронные технологии", Одесса, 2003 г.;

- VII международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 2003г.;

- Международной научно-технической конференции MM(CALS)-2003 "Информационные технологии в управлении жизненным циклом изделий", С.-Петербург, 2003г.;

- Всероссийской научно-практической конференции "Информационные технологии в российской промышленности", С.-Петербург, 2004 г.;

- 5-й международной НПК "Современные информационные и электронные технологии", Одесса, 2004 г.;

- III международном симпозиуме "Аэрокосмические приборные технологии", С.-Петербург, 2004 г.;

- VII Международной научно-практической конференции "Фундаментальные и прикладные проблемы приборостроения", Сочи, 2004 г.;

- VIII международной научно-практической конференции "Системы и средства передачи и обработки информации", Одесса, 2004 г.;

- 6-й международной НПК "Современные информационные и электронные технологии", Одесса, 2005 г.

Публикации. По теме диссертации опубликована 21 работа, из них 4 статьи и 17 тезисов к докладам на международных научно-технических конференциях.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и приложения. Текстовый материал изложен на 111 страницах.

СОДЕРЖАНИЕ РАБОТЫ

Во введении кратко освещён предмет исследования, обоснована актуальность темы диссертационной работы. Сформулированы основные положения, выносимые на защиту, научная новизна и практическая ценность результатов. Кратко описано содержание диссертации по главам.

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

При решении задач схемотехнического и конструкторского проектирования электронной аппаратуры наибольшее распространение получила точечная модель принципиальной электрической схемы в виде графа (мультиграфа) С(Х,У). В ней множество вершин графа X = {х,, Х2,..., Хп }

соответствует множеству компонентов, а множество ребер К —(У,,'У2,...,Ут} электрическим связям компонентов.

При верификации принципиальной схемы и топологии, заданных их описанием в виде графа (мультиграфа), используются алгоритмы установления изоморфности графов. Задача установления изоморфности графов достаточно хорошо изучена. Для ряда классов графов (деревья, планарные графы, графы с ограниченными степенями вершин) получены эффективные алгоритмы установления изоморфности. Определенную проблему представляет установление изоморфности сильно регулярных графов, у которых совпадают инварианты не только для самих графов, но также и для подграфов, порожденных окрестностью каждой из вершин. Однако сильно регулярные графы представляют собой достаточно узкий класс. Трудно представить, что на практике возможны схемы, модель которых будет представлять собой не только сильно регулярный, но даже и просто регулярный граф.

Таким образом, на первый взгляд, при верификации принципиальной схемы и топологии можно было бы задать их описание в виде графа и воспользоваться богатым арсеналом алгоритмов установления изоморфности графов.

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

Полный п -вершинный граф имеет п(п—1)/2 ребер, в то время как построенное на вершинах этого же графа любое дерево, в виде которого реализуется цепь на этапе трассировки, содержит 72—1 ребер. Отсюда количество "лишних" ребер в мультиграфе, описывающем 772 цепей,

_ (

4Ё(",-'Хп,-2) . (О

2 1=1

где П1 - число элементов, связанных I -й цепью.

Из (1) видно, что количественная избыточность мультиграфа по сравнению с адекватной моделью тем выше, чем больше звеньев (П1) в каждой из цепей.

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

т

„ К""1) —= 2^-, («, >2), (2)

К X 1)

(=1

Из (2), в частности следует причем К— 1 (^=0) соответст-

вует случаю, когда все цепи в схеме однозвенные (соединяют два элемента) и мультиграф адекватно представляет электрическую схему.

Пусть П - среднее количество звеньев в цепи или иначе число звеньев в цепи усредненной длины

1 т

л=-2>,. (3)

1

Подставляя (3) в (2), имеем

(4)

^-тп

/=1

или К =-, (5)

П+-

п-1

1 т ~ 2

где Г) — —2,(к,~ П) можно определять как среднеквадратичный т,=1

разброс количества контактов в цепях.

Таким образом, степень избыточности мультиграфа, моделирующего электрическую схему, непосредственно определяется средним значением и среднеквадратичным разбросом числа звеньев в цепях и может быть без труда

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

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

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

Представим схему соединений в виде гиперграфа Н{Х, Е), где каждое ребро е^Е гиперграфа представляет собой некоторое подмножество вершин,

инцидентных этому ребру. Каждому ребру гиперграфа Н соответствует определенная электрическая цепь схемы соединений. При этом заранее не задается, как и в каком порядке будут соединены вершины, инцидентные данному ребру.

Два гиперграфа с идентичными матрицами инцидентности изоморфны. Для установления изоморфности гиперграфов с неидентичными матрицами инцидентности необходимо, как и в случае с графами, попытаться путем перестановки строк и столбцов либо привести одну матрицу к другой, либо привести обе к некоторому каноническому виду. Однако здесь возникает проблема компактного хранения больших объемов данных и обеспечения быстрого доступа к ним.

В работе предложен подход, основанный на использовании особых списковых структур данных, а так же виртуальной памяти, которые обеспечивают компактное хранение данных и более быстрый к ним доступ по сравнению с принятыми типами структур данных (стек, очередь, В-дерево, массивы, использующие динамическую память).

Схема в виде списка соединений может задаваться двумя способами: для каждого компонента задается список инцидентных ему цепей, или для каждой цепи задается список соединяемых ею компонентов.

Для того чтобы не потерять преимущества матричного представления, позволяющего, задав пару индексов, получить элемент без осуществления поиска, следует задавать оба описания.

Каждый из вариантов описания будем задавать парой массивов. Один массив содержит списки цепей (компонентов), а второй - указатели на первый элемент списка.

Первоначальное разбиение на классы получаем на основе определения мощности списков инцидентности элементов (цепей и компонентов).

Дальнейшее разбиение осуществляется на основе сравнения списков

инцидентности элементов внутри класса (поочередно цепей и компонентов), при этом в качестве элемента списка фигурирует не идентификатор цепи или компонента, а номер соответствующего ему класса. Разбиение на классы прекращается, если на очередном шаге не было очередного разбиения.

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

Третья глава посвящена разработке методов переназначения функционально эквивалентных вентилей и контактов микросхем на различных этапах проектирования топологии печатного монтажа.

Задача переназначения функционально эквивалентных контактов микросхем локальная, но не тривиальная уже потому, что должна решаться на разных этапах (компоновка, размещение, трассировка). Многое зависит от модели компонентов, поскольку необходим учет их геометрических особенностей: одно- или многорядная гребенка-разъем, микросхема с двухсторонним или четырехсторонним расположением контактов, возможно ли проведение трасс между контактами и т.д.

Использование функциональной эквивалентности элементов (контактов) микросхем позволяет в большинстве случаев существенно упростить задачу трассировки межсоединений на печатных платах.

Обычно назначение функционально эквивалентных контактов осуществляется после размещения компонентов (перед трассировкой соединений).

Принято считать, что до размещения компонентов полностью отсутствует информация, позволяющая оценить качество распределения контактов микросхем, поэтому на практике обычно осуществляется следующая последовательность работ:

- произвольное распределение внешних контактов;

- размещение компонентов;

- перераспределение внешних контактов с учетом полученного размещения.

Отметим, что результаты размещения компонентов могут существенно зависеть от назначения контактных площадок микросхем, поэтому традиционный подход ограничивает возможности получения качественных результатов как на этапе размещения компонентов, так и на последующих этапах.

Этап компоновки

Близость между парой вершин будем определять на основе информации об отдаленности (близости) их по отношению к другим вершинам графа: чем больше суммарная разность расстояний до одноименных вершин графа, тем более удалены вершины друг от друга.

На основании этого положения предлагается следующая функция для определения расстояний на графе:

и

где Ьу - "отдаленность" вершины х, от вершины х};

ги и элементы матрицы расстояний (кратчайших путей) /?.

Предлагается следующая последовательность шагов решения задачи назначения эквивалентных контактов:

- определить матрицу смежности графовой модели схемы;

- определить матрицу "отдаленностей" для графовой модели схемы;

- выделить подматрицу, соответствующая контактам микросхемы;

- определить псевдогамильтонов контур наименьшего веса, причем в качестве матрицы расстояний использовать выделенную на предыдущем этапе подматрицу;

- осуществить назначение контактов микросхемы без нарушения рассчитанного порядка (привязка к конструктиву).

Этап размещения

Обычно задача оптимального назначения функционально эквивалентных элементов (контактов) обычно формулируется как задача линейного назначения, при этом в качестве стоимости назначения элемента (контакта) в конкретную позицию берется суммарная длина его соединений.

Критерий самый простой, но далеко не единственный, более того -дискуссионный. Представляется, по крайней мере, не менее важным учет числа пересечений этих отрезков, минимизация хроматического числа графа пересечений. Кроме того, практика автоматизированного проектирования показывает, что для обеспечения качественной трассировки межсоединений обеспечение минимального числа взаимных пересечений трасс является не менее значимым требованием, чем минимизация их суммарной длины.

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

Линейная структура.

Пусть на двух параллельных прямых заданы по П точек, причем эти точки произвольным образом попарно соединены отрезками. Пронумеруем точки на одной из параллельных прямых в порядке возрастания слева направо. На другой прямой каждая точка получает номер противоположного конца отрезка.

i: 1 2 3 4 5 6

4 5 6 1 2 3 l-*,:(-3)(-3)(-3)(3)(3)(3) Нижняя оценка числа пересечений вычисляется по формуле

1=1

и достигается, если линии положительного и отрицательного наклона не пересекаются между собой. Верхняя оценка

Nu=0,5n(n-l)

достигается на так называемых скрученных последовательностях (twisted sequertses), когда каждый из отрезков пересекается со всеми остальными.

i: 12 3 4 5 6

к,: 6 5 4 3 2 1 /-*,:(- 5)(-3)(-1)(1)(3)(5)

Задача определения числа пересечений может быть сведена к задаче подсчета числа инверсий при сортировке в порядке возрастания элементов массива &(/).

Циклическая структура.

Пусть на двух концентрических окружностях заданы по П точек, причем в пространстве между окружностями эти точки произвольным образом попарно соединены линиями. Пронумеруем точки на внутренней окружности в порядке возрастания против часовой стрелки. На внешней окружности каждая точка получает номер противоположного конца линии, соединяющей ее с точкой на внутренней окружности. Тогда для каждого соединения имеем два числа, модуль разности которых дает нижнюю оценку числа пересечений данного соединения с другими. Число пересечений (и оценка) зависит от того, по- или против часовой стрелки проводится соединение, поэтому при подсчете выбирается минимальное из двух значений. Оценка суммарного числа пересечений равна полусумме каждого из соединений.

Пусть некоторый компонент, содержащий классы функционально эквивалентных контактов установлен на подложке и определены внешние точки подключения контактов (двухконтактные соединения).

Проведем полуось через геометрический центр микросхемы и первый ее контакт. Проведем также радиус-векторы от центра микросхемы к внешним контактам, с которыми необходимо соединить контакты микросхемы. Пронумеруем контакты микросхемы и внешние контакты в порядке, обеспечивающем возрастание угла между радиус-вектором и полуосью (рис.1).

Рис.1. Назначение функционально эквивалентных контактов

Начиная с функционально эквивалентных классов верхнего уровня, для каждого уровня составим пары матриц назначений: матрицу А, каждая строка которой содержит номера контактов компонента, принадлежащих одному из классов (элементов) данного уровня; матрицу В, каждая строка которой содержит номера контактов внешних подключений элементов данного уровня. Соответственно, сумма оценок соединений элемента составляет стоимость назначения элемента в данную позицию.

12: 1 2 9: 11 1

3: 10 11 4: 2 6

В =

9: 4 5 8: 3 4

6: 7 8 5: 7 10

с=

6 9 8 15

8 10 15 6

9 8 3 12 12 9 10 3

с„. = Хтт

п

где Су - стоимость назначения элемента / на позицию ]; ал - номер к -го контакта /-го элемента микросхемы; Ь]к - номер к -го внешнего контакта, подключенного к ] -му элементу микросхемы.

Для решения задачи линейного назначения предложена модификация "жадного" алгоритма, использующая нормирование матрицы стоимости С.

Матрица С нормируется таким образом, чтобы сумма ее элементов равнялась нулю:

Подобное нормирование уменьшает погрешность результата при использовании "жадных" алгоритмов.

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

Этап трассировки

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

Пусть на совмещенной топологии имеется пара пересекающихся проводников А и В, инцидентных эквивалентным контактам (рис.2). Точка

пересечения проводников делит каждый из них на две части: А1- А2; В1- В2, где:

А1 (В1) - часть проводника от эквивалентного контакта до пересечения;

А2 (В2) - часть проводника после пересечения.

Поскольку топологические маршруты проводников известны, то переключение эквивалентных контактов можно осуществить без перетрассировки переключением вторых частей проводников: А1-В2; В1-А2.

Рис.2. Переключение пересекающихся проводников, подключенных к эквивалентным контактам, после пробной трассировки.

Подобный подход к переназначению функционально эквивалентных улучшает условия для трассировки, поскольку, во-первых, основывается на результатах пробной трассировки, а во вторых, уменьшает число пересечений трасс, длину соединений и способствует уменьшению хроматического числа графа пересечений трасс.

В четвертой главе рассмотрены вопросы контроля конструктивно-технологических нарушений в топологии печатного монтажа.

Задача. Задан набор контактов и принадлежность их цепям и компонентам. Кроме того, задан набор проводящих и непроводящих деталей (сегментов), расположенных в трассировочных плоскостях. У цепей и компонентов могут быть атрибуты.

Неформальное описание задачи

Требуется проверить, что все контакты каждой цепи надёжно соединены проводящими сегментами (или другим способом), что между проводящими сегментами разных цепей имеется надёжный зазор, и что между проводящими

а2

в2

сегментами и барьерами или запретами имеется надёжный зазор. Требуется также сообщить о неразведённых цепях и о расположении ненадёжных соединений и ненадёжных зазоров.

Зазоры между непроводящими сегментами контролировать не требуется.

В постановку задачи не входят: проверка зазоров между сегментами на нетрассировочных плоскостях; проверка непопадания межслойных переходов в зоны запрета переходов; поиск циклов в соединениях; проверка соблюдения тепловых и электромагнитных требований.

Модель

Имеется набор контактов, заданных их координатами и слоем, на котором они находятся. Каждый контакт принадлежит некоторой цепи и некоторому компоненту.

Задан набор проводящих и непроводящих сегментов, расположенных в логических слоях, отображаемых на трассировочные плоскости.

Некоторым проводящим сегментам изначально приписана цепь. Цепь с именем «?» означает, что контакт не задействован в схеме. Соединение незадействованных контактов должно индентифицироваться как ошибка.

Кластером будем называть набор проводящих сегментов, имеющих надёжное соединение. Будем считать, что все непроводящие сегменты составляют один специальный кластер запретов. Таким образом, кластеры бывают 4 видов: принадлежащие цепи не «?», принадлежащие цепи «?», не принадлежащие никакой цепи и запреты.

Два проводящих сегмента считаются надёжно соединёнными, если выполняется хотя бы одно из условий:

имеется сегмент, с которым они оба надёжно соединены; сегменты принадлежат одному и тому же контакту; сегменты принадлежат одному и тому же переходу; сегменты принадлежат контактам одной цепи (не с именем «?»), принадлежащим компоненту с атрибутом «Мр» (перемычка);

сегменты, не принадлежащие разным цепям или цепи с именем «?», отображаются на один трассировочный слой и перекрытие между ними не меньше заданного.

Формальная постановка задачи на модели

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

В каждой цепи должен быть только один кластер (иначе цепь будет не разведена).

Между кластерами должен быть надёжный зазор.

Между сегментами разных контактов и переходов должен быть надёжный зазор.

Не должно быть кластеров, не принадлежащих никакой цепи.

Алгоритм

1. Получить сегменты. Инициализировать структуры данных.

2. Связать проводящие сегменты не из секции проводников с контактами и наоборот.

3. Проверить, что у каждого контакта есть контактная площадка.

4. Объединить сегменты в кластеры.

5. Найти все места с ненадёжным зазором или ненадёжным соединением (для неразведённых цепей).

6. Проверить площади кластеров, не принадлежащих никакой цепи.

7. Проверить площади кластеров незадействованных контактов.

Пятая глава посвящена вопросам организации программного обеспечения подсистемы автоматизированной верификации топологии печатного монтажа.

На основе выполненных исследований автором разработана программа автоматической верификации топологии печатного монтажа (DRC), входящая на правах подсистемы в САПР топологического проектирования топологии печатного монтажа "TopoR".

В таблице для каждого правила трассировки указывается минимально допустимые ширина проводников и зазор. При первом запуске DRC эти величины читаются из стиля разработки.

DRC позволяет задать необходимую величину зазора между проводниками И барьерами трассировки (Wke-bamer deatarv* )

Для обнаружения участков металлизации, не подключенных к никакой цепи (поп connected), в целях предупреждения возможных паразитных явлений можно задать максимально допустимое значение площади таких участков, а также площади металлизации незадействованных КП (connected ю ае р»»).

DRC позволяет проверить:

• целостность цепей (" пе1г1,е»|)>);

• ширину сегментов цепей (Р netwidth);

• зазоры между проводниками, а также между проводником и барьером трассировки (J7 с|ег|гапс");

• отсутствие участков металлизации, не подключенных ни к какой цепи (Г поп connected «wate), площадь которых более заданной;

• отсутствие незадействованных КП (Г connectedtoidlepire square), ПЛОЩЭДЬ которых более заданной.

Проведенный сравнительный анализ продемонстрировал несомненное преимущество программы по сравнению с аналогами (Specctra, PCAD) в части быстродействия.

В заключении сформулированы основные научные и практические результаты работы.

В приложении даются сведения, подтверждающие использование полученных результатов в народном хозяйстве страны.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Проведен анализ применяемых моделей и алгоритмов верификации принципиальных схем и топологии узлов РЭС на печатных платах, микросборках и СБИС.

2. Показана неадекватность мультиграфовой модели принципиальной электрической схемы, традиционно используемой при решении задач верификации.

3. Обоснована необходимость использования модели принципиальной электрической схемы в виде гиперграфа.

4. Разработан алгоритм определения изоморфности гиперграфов как теоретической основы задачи установления соответствия описания топологии печатного узла и его принципиальной схемы.

5. Предложена новая функция для определения топологических расстояний на графе и алгоритм переназначения функционально эквивалентных контактов микросхем на этапе компоновки.

6. Разработаны методы получения оценки числа пересечений ребер линейной и циклической реализаций двудольного графа и алгоритм переназначения функционально эквивалентных вентилей и контактов микросхем, использующий оценки числа пересечений медсоединений.

7. Разработаны эффективный алгоритм переназначения функционально эквивалентных контактов микросхем на этапе пробной трассировки соединений.

8. Разработаны структуры данных и алгоритмы контроля конструктивно-технологических нарушений в топологии печатного монтажа.

9. Разработаны быстродействующие программные средства автоматической верификации принципиальных схем и топологии узлов РЭС на печатных платах, микросборках и СБИС.

По материалам диссертации опубликованы следующие работы:

1. Лузин М.С. Использование функциональной эквивалентности при проектировании печатных плат. / Лузин М.С., Зудин C.B., Лузин С.Ю. // Труды международной НТК "Системы и средства передачи и обработки информации". - Одесса. - 1999. - С.68.

2. Лузин М.С. Верификация топологии БИС и принципиальной схемы. // Труды третьей международной научно-практической конференции "Современные информационные и электронные технологии". - Одесса. - 2002. -С.172.

3. Лузин М.С. Изоморфизм гиперграфов и контроль топологии электронных схем. // Труды международной НТК "Системы и средства передачи и обработки информации". - Одесса. - 2002. - С. 148.

4. Лузин М.С. Учебная САПР тонкопленочных микросборок. / Лузин М.С., Дмитриев П.И., Зудин C.B., Петросян Г.В., Полубасов О.Б. // Труды 9-й

международной конференции "Современные технологии обучения", С.Петербург.-2003. - т. 1. -С.196-197.

5. Лузин М.С. К оценке числа пересечений ребер двудольного графа./ Лузин М.С., Соколов В.Е. // Труды четвертой международной научно-практической конференции "Современные информационные и электронные технологии". - Одесса. - 2003. - С. 211.

6. Лузин М.С. Сравнительный анализ алгоритмов решения задачи коммивояжера. / Лузин М.С., Соколов В.Е. // Проблемы машиноведения и машиностроения. Межвузовский сборник. Вып. 29. С.-Петербург. - 2003. -С.131-143.

7. Лузин М.С. Оценка числа пересечений ребер двудольного графа. / Лузин М.С., Соколов В.Е. // Проблемы машиноведения и машиностроения. Межвузовский сборник. Вып. 30. С.-Петербург. - 2003. - С. 59-62.

8. Лузин М.С. Система автоматизированного проектирования тонкопленочных микросборок "FreeStyle_TF". / Лузин М.С., Дмитриев П.И., Лузин С.Ю., Колосов А.Н., Полубасов О.Б., Шубарев В.А. // Технологии приборостроения. - 2003. - №3. - С. 42-49.

9. Лузин М.С. Повышение эффективности силового размещения компонентов. / Лузин М.С., Дмитриев П.И., Зудин C.B., Полубасов О.Б. // Технология и конструирование в электронной аппаратуре. - 2003. - С.7-9.

10. Лузин М.С. TopoR - система автоматизированной трассировки печатных плат. / Лузин М.С., Дмитриев П.И., Зудин C.B., Лузин С.Ю., Петросян Г.С., Полубасов О.Б. // Труды VII международной научно-практической конференции "Системы и средства передачи и обработки информации". - Одесса. - 2003. - С. 137.

11. Лузин М.С. Система топологической трассировки печатных плат. / Лузин М.С., Дмитриев П.И., Зудин C.B., Лузин С.Ю., Петросян Г.С., Полубасов О.Б. // Труды международной научно-технической конференции HTOi(CALS)-2003 "Информационные технологии в управлении жизненным циклом изделий". С.-Петербург. - 2003. - С.38.

12. Лузин М.С. Интегрированная САПР тонкопленочных гибридных интегральных схем "Авангард". / Лузин М.С., Дмитриев П.И., Зудин C.B., Лузин С.Ю., Петросян Г.С., Полубасов О.Б. // Труды международной научно-технической конференции HIIM(CALS)-2003 "Информационные технологии в управлении жизненным циклом изделий". С.-Петербург. - 2003. - С.39-40.

13. Лузин М.С. Автоматизация синтеза топологии печатного монтажа. / Лузин М.С., Дмитриев П.И., Зудин C.B., Лузин С.Ю., Петросян Г.С., Полубасов О.Б. // Труды 5-й международной НПК "Современные информационные и электронные технологии". - Одесса - 2004. - С. 166.

14. Лузин М.С. Преимущества неортогональной топологии печатного монтажа. / Лузин М.С., Дюдин М.В., Петросян Г.С., Полубасов О.Б. // Труды 5-й международной НПК "Современные информационные и электронные технологии". - Одесса. - 2004. - С. 167.

15. Лузин М.С. Обеспечение электромагнитной совместимости на этапе размещения компонентов. / Лузин М.С., Зудин C.B., Петросян Г.С.,

Полубасов О.Б., Соколов В.Е. // Труды 5-й международной НПК "Современные информационные и электронные технологии". - Одесса. - 2004. - С. 163.

16. Лузин М.С. Система автоматизации синтеза топологии печатного монтажа. / Лузин М.С., Дмитриев П.И., Зудин C.B., Лузин С.Ю., Петросян Г.С., Полубасов О.Б. // Труды Всероссийской научно-практической конференции "Информационные технологии в российской промышленности". - С.Петербург. - 2004. - С.91-92.

17. Лузин М.С., К оценке качества топологии печатного монтажа. / Лузин М.С., Воротынцев В.Ю., Петросян Г.С. // Труды III международного симпозиума "Аэрокосмические приборные технологии", - С.-Петербург. -2004.-С.175.

18. Лузин М.С. Пути повышении плотности печатного монтажа. / Лузин М.С., Воротынцев В.Ю., Петросян Г.С. // Труды VII Международной научно-практической конференции "Фундаментальные и прикладные проблемы приборостроения". - Сочи. - 2004. - С.29-30.

19. Лузин М.С. Обеспечение заданного качества топблогии печатного монтажа. / Лузин М.С., Дмитриев П.И., Зудин C.B., Лузин С.Ю., Петросян Г.С., Полубасов О.Б. // Труды VIII международной научно-практической конференции "Системы и средства передачи и обработки информации". -Одесса. - 2004. - С.123-124.

20. Лузин М.С. Способ повышения плотности печатного монтажа. / Лузин М.С., Дюдин М.В., Петросян Г.С., Полубасов О.Б. // Труды VIII международной научно-практической конференции "Системы и средства передачи и обработки информации". - Одесса. - 2004. с.119-120.

21. Лузин М.С. Контроль констуктивно-технологических нарушений в системе TopoR. / Лузин М.С., Дюдин М.В., Петросян Г.С., Полубасов О.Б. // Труды 6-й международной НПК "Современные информационные и электронные технологии". - Одесса. - 2005. - С. 126.

Подписано в печать 26.04.05. Формат 60*84 1/16. Бумага офсетная. Печать офсетная. Печ. л. 1,0. Тираж 100 экз. Заказ 32.

Отпечатано с готового оригинал-макета в типографии Издательства СПбГЭТУ "ЛЭТИ"

Издательство СПбГЭТУ "ЛЭТИ" 197376, С.-Петербург, ул. Проф. Попова, 5

-8 7 4 7

РНБ Русский фонд

2006-4 15774

ВВЕДЕНИЕ.

I. УСТАНОВЛЕНИЕ ИЗОМОРФНОСТИ РАЗЛИЧНЫХ

ОПИСАНИЙ

1.1. Изоморфность мультиграфов.

1.2. Избыточность мультиграфового представления принципиальной схемы.

1.3. Выводы

II. РАЗРАБОТКА АЛГОРИТМА ОПРЕДЕЛЕНИЯ ИЗОМОРФНОСТИ ОПИСАНИЙ ТОПОЛОГИИ

И ПРИНЦИПИАЛЬНОЙ СХЕМЫ.

2.1. Изоморфность гиперграфов.

2.2. Инварианты матрицы инцидентности гиперграфа

2.3. Компактное представление гиперграфа.

2.4. Алгоритм определения изоморфности гиперграфов

2.5. Выводы

III. ИСПОЛЬЗОВАНИЕ ФУНКЦИОНАЛЬНОЙ ЭКВИВАЛЕНТНОСТИ КОНТАКТОВ МИКРОСХЕМ

3.1. Методы и критерии.

3.2. Использование функциональной эквивалентности контактов микросхем на этапе компоновки.

3.2.1. Определение расстояний на графовой модели схемы.

3.2.2. Алгоритм решения задачи назначения эквивалентных контактов.

3.2.3. Выбор метода решения задачи коммивояжера

3.3. Использование функциональной эквивалентности контактов микросхем на этапе размещения.

3.3.1. Оценка числа пересечений ребер двудольного графа

3.4. Использование функциональной эквивалентности контактов микросхем на этапе трассировки.

3.5. Выводы

IV. КОНТРОЛЬ КОНСТРУКТИВНО-ТЕХНОЛОГИЧЕСКИХ НАРУШЕНИЙ

В ТОПОЛОГИИ ПЕЧАТНОГО МОНТАЖА.

4.1. Особенности контроля конструктивно-технологических ограничений в гибкой топологической трассировке

4.2. Алгоритм проверки конструктивно-технологических нарушений в топологии печатного монтажа.

4.3. Выводы

V. ПРОГРАММНЫЙ КОМПЛЕКС ТОПОЛОГИЧЕСКОЙ ТРАССИРОВКИ ПЕЧАТНЫХ ПЛАТ TopoR.

5.1. Основные сведения о системе TopoR

5.1.1. Требования системы к оборудованию.

5.1.2. Технические характеристики и ограничения

5.1.3. Режимы и функции

5.2. Программа проверки выполнения конструкторско-технологических ограничений (DRC).

5.3. Выводы

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

Сложность радиоэлектронной аппаратуры неуклонно повышается. Не только увеличивается количество элементов на печатной плате или кристалле БИС, но и сами элементы становятся всё более сложными: увеличивается количество внешних контактов микросхем при одновременном уменьшении расстояний между контактами. В результате задача синтеза топологии соединений становится всё более и более трудной.

Вероятность того, что разработанная топология сразу же будет корректной, очень мала, так как невозможно полностью исключить «человеческий фактор» ни в одном методе проектирования, сколь бы автоматизированным он ни был. А человеку, как известно, свойственно ошибаться.

При проектировании топологии печатных плат (ПП) и интегральных схем (ИС) могут возникнуть ошибки, связанные с потерей соединений, с прокладкой лишних соединений и самое худшее - с перестановкой соединений. Тогда возникает ситуация, когда общее число связей и элементов соответствует заданному, но схема не работает. Поэтому важно еще до начала этапа изготовления фотошаблонов убедиться, что проектируемое устройство будет выполнять требуемые функции. Другими словами, удостовериться, что созданная топология соответствует реализуемой электрической схеме и заданным конструктивно-технологическим ограничениям (КТО).

Следовательно, необходимость введения в маршрут проектирования этапа верификации топологии вполне очевидна.

Существующие подсистемы верификации топологии, входящие в состав представленных на рынке САПР ориентированы в значительной степени на интерактивную верификацию принципиальной схемы и топологии, что ведет к неоправданно высоким временным затратам. Проверка соблюдения КТО в большинстве САПР осуществляется на ортогональной топологии без дуг окружностей, либо с квадрантными (четверть окружности) дугами. Все это не соответствует современным требованиям к качеству топологии печатного монтажа.

В современных САПР недостаточно используются возможности оптимизации топологии печатного монтажа, связанные с переназначением функционально эквивалентных контактов полузаказных БИС. Поскольку при решении указанной задачи изменяется принципиальная схема устройства, ее результаты необходимо учитывать при решении задачи верификации топологии.

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

В соответствии с этим в работе ставились и решались следующие задачи:

- анализ применяемых моделей и алгоритмов верификации принципиальных схем и топологии узлов РЭС на печатных платах, микросборках и СБИС;

- построение адекватных требованиям топологического синтеза моделей электрических схем проектируемых узлов, используемых на этапе верификации;

- разработка эффективного алгоритма определения изоморфности гиперграфов как теоретической основы задачи установления соответствия описания топологии печатного узла его принципиальной схеме;

- разработка методов получения оценки числа пересечений ребер линейной и циклической реализаций двудольного графа;

- разработка эффективных методов назначения функционально эквивалентных контактов микросхем на различных этапах проектирования топологии печатного монтажа;

- разработка эффективных структур данных и алгоритмов контроля конструктивно-технологических нарушений в топологии печатного монтажа;

- создание и адаптация к промышленным условиям эксплуатации быстродействующих программных средств автоматической верификации топологии узлов РЭС на печатных платах, микросборках и СБИС.

Научная новизна диссертационной работы заключается:

- в обосновании использования гиперграфовой модели электрической схемы устройства при решении задачи верификации печатных узлов РЭС;

- в разработке алгоритма определения изоморфности гиперграфов;

- в разработке методов получения оценки числа пересечений ребер линейной и циклической реализаций двудольного графа;

- в разработке методов переназначения функционально эквивалентных вентилей и контактов микросхем на различных этапах синтеза топологии печатного монтажа;

- в разработке эффективных структур данных и алгоритмов контроля конструктивно-технологических нарушений в топологии печатного монтажа.

Практическая ценность работы состоит в создании прикладных программ, предназначенных для решения задачи верификации топологии печатного монтажа в автоматическом режиме. Применение разработанных программ обеспечивает улучшение качества и сокращение сроков проектирования СБИС и печатных узлов РЭС.

Результаты диссертационной работы в виде конкретных положений, выводов, методов, алгоритмов, машинных программ и расчетных данных внедрены и инженерную практику и используются на промышленных предприятиях в Москве, Санкт-Петербурге и Нижнем Новгороде, а также в учебном процессе СПбГУАП и СПбГЭТУ (ЛЭТИ). Акты, подтверждающие внедрение, приведены в приложении.

Основные положения и результаты диссертационной работы докладывались и были одобрены на следующих конференциях:

- III Международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 1999г;

- III научно-практической конференции "Современные информационные и электронные технологии", г. Одесса, 2002г.;

- VI международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 2002г.;

- 9-й международной конференции "Современные технологии обучения", С.-Петербург, 2003 г.;

- 4-й международной НПК "Современные информационные и электронные технологии", Одесса, 2003 г.;

- VII международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 2003 г.;

- Международной научно-технической конференции HnH(CALS)-2003 "Информационные технологии в управлении жизненным циклом изделий", С.-Петербург, 2003г.;

- Всероссийской научно-практической конференции "Информационные технологии в российской промышленности", С.Петербург, 2004 г.;

- 5-й международной НПК "Современные информационные и электронные технологии", Одесса, 2004 г.;

- III международном симпозиуме "Аэрокосмические приборные технологии", С.-Петербург, 2004 г.;

- Международной научно-практической конференции "Фундаментальные и прикладные проблемы приборостроения", Сочи, 2004 г.;

- VIII международной научно-практической конференции "Системы и средства передачи и обработки информации", Одесса, 2004 г.;

- 6-й международной НПК "Современные информационные и электронные технологии", Одесса, 2005 г.

По теме диссертации опубликована 21 работа, из них 4 статьи и 17 тезисов к докладам на международных научно-технических конференциях.

Диссертация состоит из введения, пяти глав, заключения и приложения. Текстовый материал изложен на 121 странице.

5.3. Выводы

1. Разработан программный комплекс топологической трассировки печатного монтажа TopoR (от Topological Router).

2. Разработана программа контроля конструктивно-технологических ограничений с учетом особенностей топологической трассировки печатного монтажа.

3. Разработаны программные средства автоматизированного переназначения функционально эквивалентных контактов микросхем.

ЗАКЛЮЧЕНИЕ

Основные теоретические и практические результаты диссертационной работы заключаются в следующем.

1. Проведен анализ применяемых моделей и алгоритмов верификации принципиальных схем и топологии узлов РЭС на печатных платах, микросборках и СБИС.

2. Показана неадекватность мультиграфовой модели принципиальной электрической схемы, традиционно используемой при решении задач верификации.

1. Обоснована необходимость использования модели принципиальной электрической схемы в виде гиперграфа.

2. Разработан алгоритм определения изоморфности гиперграфов как теоретической основы задачи установления соответствия описания топологии печатного узла и его принципиальной схемы.

3. Предложена новая функция для определения топологических расстояний на графе и алгоритм переназначения функционально эквивалентных контактов микросхем на этапе компоновки.

4. Разработаны методы оценки числа пересечений ребер линейной и циклической реализаций двудольного графа и алгоритм переназначения функционально эквивалентных вентилей и контактов микросхем, использующий оценки числа пересечений медсоединений.

5. Разработаны эффективный алгоритм переназначения функционально эквивалентных контактов микросхем на этапе пробной трассировки соединений.

6. Разработаны структуры данных и алгоритмы контроля конструктивно-технологических нарушений в топологии печатного монтажа.

7. Разработаны быстродействующие программные средства автоматической верификации принципиальных схем и топологии узлов РЭС на печатных платах, микросборках и СБИС.

1. Абрайтис Л.Б., Шнейкаускас Р.И., Жилявичус В.А. Автоматизация проектирования ЭВМ. - М.: Сов. радио, 1978, 272с.

2. Абрайтис Л.Б., Автоматизация проектирования топологии цифровых, интегральных микросхем. М.: Радио и связь, 1985, 197с.

3. Алгоритмические исследования в комбинаторике / Под ред. Фараджева И.А. -М.: Наука, 1978.

4. Арлазаров В.Л., Зуев И.В., Усков А.В., Фараджев И.А. Алгоритм приведения конечного неориентированного графа к каноническому виду. ЖВМ и МФ, 1974, 14, №3, с. 737-747.

5. Баранов С.И., Майоров С.А. Сахаров Э.П., Селютин В.А. Автоматизация проектирования цифровых устройств. Л.: Судостроение, 1979.-264с. . . .

6. Барышев А.И. Приложение гиперграфов к задаче трассировки. — В кн.: Автоматизация конструкторского проектирования радиоэлектронной и электронно-вычислительной аппаратуры. -Саратов: Изд-во Саратовского у-та, 1981, с.64-67.

7. Бахтин Б.И. Автоматизация в проектировании и производстве печатных плат радиоэлектронной аппаратуры. Л.: Энергия, 1979. -120с.

8. Батищев Д.И., Бершадский A.M., Щербань А.Б. Обобщенный критерий оценки качества разбиения графа на группы изоморфных подграфов. В кн.: Анализ и моделирование экономических процессов. - Горький: Изд-во Горьк. у-та, 1979, с. 3-9.

9. Бершадский A.M. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. Изд. Саратовского университета, 1983,- 120с.

10. Бершадский A.M., Щербань А.Б., Игошина JI.B. Использование метода выделения в графе изоморфных подграфов для повышения эффективности алгоритмов размещения разногабаритных элементов. -Изв. ЛЭТИ, 1979, вып. 235, с. 105-109.

11. Берштейн Л.С. Селянкин В.В. Линейное размещение гиперграфов. -Изв. АН СССР, Техн. кибернетика, 1973. № 3, с. 128 -135.

12. Бибило П.Н., Лицкевич, В.Г. Покрытие булевой сети библиотечными элементами. Управляющие системы и машины, 1999, №6, с 16-24.

13. Вичес С.А. Асимптотический оптимально алгоритм перечисления пересечений ребер двудольного графа. Авт. и телемеханика, вып. 12. 1984, с.133-137.

14. Воротынцев В.Ю., Лузин М.С., Петросян Г.С. К оценке качества топологии печатного монтажа. // Труды III международного симпозиума "Аэрокосмические приборные технологии", — С.Петербург. 2004. - С. 175.

15. Воротынцев В.Ю., Лузин М.С., Петросян Г.С. Пути повышении плотности печатного монтажа. // Труды Международной научно-практической конференции "Фундаментальные и прикладные проблемы приборостроения". Сочи. - 2004. - С.

16. Горбатов В.А. Частотная матрица отношений и ее применения. Труды МЭИ. Вычислительная техника, 1964, т.53, с. 5-30.

17. Горбатов В.А. и др. Автоматизация проектирования сложных логических структур. М., Энергия, 1978.

18. Горбатов В.А. Теория частично упорядоченных систем. М., Сов. радио, 1976,-248 с.

19. Горбатов В.А. Семантическая теория проектирования автоматов. М., Энергия, 1979, 264 с.

20. Горбатов В.А., Павлов П.Г., Четвериков В.Н. Логическое управление информационными процессами. М., Энергоатомиздат, 1984, - 304 с.

21. Горбатов В.А. Основы дискретной математики. М., Высшая школа, 1986, - 311 с.

22. Деньдобренко Е.Н., Малика А.С. Автоматизация проектирования радиоэлектронной аппаратуры. М.: Высшая школа, 1980. -384с.

23. Дмитриев П.И., Лузин М.С., Лузин С.Ю., Колосов А.Н., Полубасов О.Б., Шубарев В.А. Система автоматизированного проектирования тонкопленочных микросборок "FreeStyleTF". // Технологии приборостроения. 2003. - №3. - С. 42-49.

24. Дмитриев П.И., Зудин С.В., Лузин М.С., Полубасов О.Б. Повышение эффективности силового размещения компонентов. // Технология и конструирование в электронной аппаратуре. 2003. — С.7-9.

25. Дмитриев П.И., Зудин С.В., Лузин М.С., Петросян Г.В., Полубасов О.Б. Учебная САПР тонкопленочных микросборок. // Труды 9-й международной конференции "Современные технологии обучения", С.-Петербург, 2003, т. 1., с. 196-197.

26. Дмитриев П.И., Зудин С.В., Лузин С.Ю., Лузин М.С., Петросян Г.С., Полубасов О.Б. Автоматизация синтеза топологии печатного монтажа. // Труды 5-й международной НПК "Современные информационные и электронные технологии". Одесса. - 2004. -С. 166.

27. Дюдин М.В., Лузин М.С., Петросян Г.С., Полубасов О.Б. Способ повышения плотности печатного монтажа. // Труды VIII международной научно-практической конференции "Системы и средства передачи и обработки информации". Одесса, 2004, с. 123.

28. Дюдин М.В., Лузин М.С., Петросян Г.С., Полубасов О.Б. Преимущества неортогональной топологии печатного монтажа. // Труды 5-й международной НПК "Современные информационные и электронные технологии". Одесса. - 2004. - С. 167.

29. Жижко В.А. Метод построения гиперграфа на плоскости. -Электронная техника, сер. 3. Микроэлектроника, 1979, вы. 6 (84), с. 78-85.

30. Зайченко В.А., Иванов А.В., Розенфельд М.З., Фараджев И.А. Алгоритм проверки каноничности частично-заполненной матрицы смежности графа. В кн.: Алгоритмические исследования в комбинаторике. М.: Наука, 1978 с. 19-24.

31. Зыков А.А. Гиперграфы. Успехи мат. наук, 1974, т. XXIX, вып. 6 (180), с. 89-154.

32. Зыков А. А. Основы теории графов. М.: Наука, 1987. - 384 с.

33. Кохов В.А. Диаграммы, числа стабильности и цикловые индексы групп автоморфизмов транзитивных графов. В сб. Исследования по прикладной теории графов /под ред. А.С. Алексеева. - Новосибирск, Наука, 1986,- 168с.

34. Кохов В.А., Ульяновский И.И. Исследование транзитивных графов, порожденных диаграммами Кели. Тр. Моск. энерг. ин-та, 1981, вып. 556, с. 29-35.

35. Кохов В.А., Ульяновский И.И. Алгоритм конструктивного перечисления графов с определенной группой автоморфизмов. Тр. Моск. энерг. ин-та, 1981, вып. 556, с. 36-42.

36. Кристофидес Н. Теория графов. М.: Мир, 1978. - 423 с.

37. Лузин С.Ю., Лячек Ю.Т., Полубасов О.Б. Автоматизация проектирования печатных плат. Система топологической трассировки TopoR. // СПб, СПбГЭТУ "ЛЭТИ". 2005. - 163 с.

38. Лузин М.С. Верификация топологии БИС и принципиальной схемы. Труды третьей международной научно-практической конференции "Современные информационные и электронные технологии". -Одесса, 2002, с. 172.

39. Лузин М.С. Изоморфизм гиперграфов и контроль топологии электронных схем. // Труды международной НТК "Системы и средства передачи и обработки информации". Одесса, 2202, с. 148.

40. Мелихов A.M., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. - 304с.

41. Мелихов А.К., Берштейн Л.С., Селянкин В.В. Минимизация пересечений проводников в канале с помощью гиперграфов. АиВТ, 1977, № 4. С.77-82.

42. Петренко А.И., Тетельбаум А .Я. Формальное конструирование электронно-вычислительной аппаратуры. М.: Советское радио, 1979.-253с.

43. Селютин В.А. Машинное конструирование электронных устройств. -М.: Советское радио, 1977, 384с.

44. Соколов В.Е., Лузин М.С. К оценке числа пересечений ребер двудольного графа. // Труды четвертой международной научно-практической конференции "Современные информационные и электронные технологии". Одесса, 2003, с.211.

45. Соколов В.Е., Лузин М.С. Сравнительный анализ алгоритмов решения задачи коммивояжера. // Проблемы машиноведения и машиностроения. Межвузовский сборник. Вып. 29. С.-Петербург. -2003. С.131-143.

46. Соколов В.Е., Лузин М.С. Оценка числа пересечений ребер двудольного графа. // Проблемы машиноведения и машиностроения. Межвузовский сборник. Вып. 30. С.-Петербург. -2003. С.59-62.

47. Тетельбаум А.Я., Шрамченко Б.Л. Применение гиперграфов при исследовании планарности электронных схем. Изв. АН СССР, Техн. кибернетика, 1975. №5. С. 127-136.

48. Хопкрофт Дж.Е., Тарьян П.Е. Изоморфизм планарных графов. -Кибернетический сборник, вып. 12., 1975, с. 39-61.

49. A Library of TSP instances: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

50. Babai L., Kucera L. Canonical Labelling of Graphs in Linear Averageth

51. Time. Proc. 20 Symp. On Foundations of Сотр., Sci., Puerto Rico, 1979, pp.39-46.

52. Babai L. On the Complexity of Canonical Labelling of Strongly Regular Graphs. SIAM J. Сотр., 9,1980, pp.212-216.

53. Babai L. Automorphism group and category of cospectral graphs. Acta Math. Acad. Sci. Hung., 31, 1978, pp.295-306.

54. Babai L., Erdos P., Selkow S.M. Random Graph isomorphism. SIAM J. Сотр., 9 (1980), pp. 628-635.

55. Babai L., Grigoryev D., Y., Mount D.,M. Isomorphism of Graphs with Bounded Eigenvalue Multiplicity. - Proc. 14th Annual ACM Symp. On Theory of Computing, 1983, pp. 310-324.th

56. Babai L., Luks E.M. Canonical Labelling of Graphs. Proc. 15 Annual ACM Symp. On Theory of Computing, 1983, pp. 171-183.

57. Balahan A.T., Harary F. The Characteristic Polynomial Das Not Uniquely Determine the Topology of a Molecule. J. Of Chem. Doc., 11, 4 (1971), pp.258-259.

58. Bauersfeld G., Essman C., Lohle H. Ein Algorithmus zur Ferstellung der Isomorphie von Endlichen Graphen. Computing, 1, 2 (1979), 159-168.

59. Bermond J.c., Vergnas M. Regular Factors in Nearly Regular Graphs. -Dicrete Mathematics, 50 (1984), pp. 9-13.

60. Biggs N.L. Automorphism of imbedded Graphs. J. Comb. Theory, Bll (1971), pp.132-139.

61. Biggs N.L. Lloyd E.K., Wilson R.J. Graph Theory. Oxford, 1980, -239pp.

62. Bohm C., Santolini A. A quasi decision algorithm for the p- equivalence of two matrices. ICC Bull., 6, 1, 1964, 57-69.

63. Booth K.S. Isomorphism Testing for Graphs, Semigraphs and Finite Automatates are Polynomially. SIAM J. Сотр., 7, 9 (1978), pp. 213-279.

64. Borowiecki M. On Spectrum of Graphs. Publ. De Г Inst. Mathem. Nouvelle serie, t.39 (52), 1985, pp. 31-33.

65. Bose R.C., Shimamoto T. Classification and analysis of partially balanced incomplete block designes with two associated classes. J. Amer. Stat. Assoc., 47, 1952. Pp. 151-184.

66. Bose R.C. Strongly regular graphs partial geometries and partially balanced designs. J. Math., 1963, v.13, pp. 389-419.

67. Brown H., Hjelmeland L., Masinter L. Constructive Graph Labelling Using Double Cosets. Discrete Math., 7 (1974), pp.1-30.

68. Brualdi R.A., Solheid E.S. On the Specral Radins of Connected Graphs. -Publ. Inst. Math., Nouv. Serie, t.39 (53), 1986, pp.45-54.

69. Chandhary N.S., Sarda N.L., Phatak D.B. A note on the property of an adjoiner of the adjacency matrix of strongly regular graphs. Indian J. Pure and Appl. Math., 1986, 17, №7, pp. 871-874.

70. Christian R. An Isomorphism for Digital Imagies. J. Comb. Theory, 1985, A39,№2,pp. 132-159.

71. Corneil D.G., Goldberg M.K. On graph certificates. Proc. 13th Southeastern Conf. On Combinatorics, Graph Theory & Computing. Congr. Numer. 35 (1982), pp.181-189.

72. Corneil D.G., Goldberg M.K. A Non-factorial Algorithm for Canonical Numbering of a Graph. J. of Algorithms, 1984, Sept., v.5., No.3, pp.345362.

73. Corneil D.G., Gotlieb C.C. An efficient algorithm for graph isomorphism. -J. ACM, 17(1970), pp. 51-64.

74. Corneil D.G., Kirkpatrick D.G. A theoretical analysis of various heuristics for the graph isomorphism problem. SI AM J. on Comput., 9, 2 (1980), pp. 281-297.

75. Cosis O. A Formalism Relevant to a Classical Strategy for Graph Isomorphism Testing. Proc. 7th S.E. Conf. on Comb., Graph Theory and Computing. 1976, pp. 229-238.

76. Dewdney A.K. Tree Classes of Graph Invariants and their Powers. 9 S.E. Conf. on Comb., Graph Theory and Computing. 1978, pp. 243-264.

77. Dorigo M., L.M. Gambardella. Ant Colonies for the Traveling Salesman Problem. BioSystems, 43:73-81, 1997.

78. Droms С. Isomorphism graphs groups. Proc. of the Amer. Math. Soc., v.100., No.3, 1987, July, pp. 407-408.

79. Druppel L.E., Schmidt D.C., Simpson J.E. A Partitioning Isomorphism Algorithm for Directional Graphs using the F Matrix. Proc. 6th S.E. Conf. on Comb., Graph Theory and Computing, 1975.

80. Feigenbaum J., Schaffer A. Recognizing composite graphs is equivalent to testing graph isomorphism. SIAM J. Сотр., 1986, 15, №2, pp. 619627.

81. Gardner M.L. Hypergraphs and Whitney's theorem on edge-isomorphism of graphs. -Discr. Math., 1984, 51, №1, pp. 1-9.

82. Gati G. Further Annotated Bibliography on the Isomorphism Desease. J. Graph Theory, 3, 1979, pp. 95-109.

83. GATSS: Genetic Algorithm based solver of the Traveling Salesman problem, http://www.acc.umu.se/~top/travelinformation.html

84. GNU Scientific Library: http://sources.redhat.com/gsl/ref/gsl-ref toc.html

85. Harary F., Robinson R.W. Isomorphic Factorizations III: Bisectable Trees. Combinatorica, v.4, No. 2-3, 1984, pp. 169-179.

86. Hoffman C.M. Group theoretic algorithms and graph isomorphism. — Lecture Notes in Computer Science, v. 136, 1982, Berlin.

87. King C., Mowshowits A., Read R.C. Cospectral Graphs and Digraphs. -Bull. London Math., Soc., v.3, 1971, Nov., No.9, pp. 321-328.

88. Kureichic V., Bickart T. An Isomorphism Test for Homogenous Graphs. In Proc. Conf. On Information Science and Systems, USA, 1979.

89. Kureichic V., Tetelbaum A. Graph Isomorphism Algorithm for Regular VLSI Structure. Proc. 28th Annual Conf. on Information Science and Systems, Princeton, USA, March 1994, pp. 78-85.

90. Marcus Randall, David Abramson. An Empirical Study of State Encoding in Tabu Search. Technical Report 99-02, School of Information Technology, Bond University, 1999.

91. Martin, S.W. Otto, and E.W. Felten. Large-step Markov chains for the TSP incorporating local search heuristics. Oper. Res. Lett., 11:219—24, 1992.

92. Olivier C. Martin, Stewe W. Otto. Combining Simulated Annealing with Local Search Heuristics. Annals of Operations Research, vol. 63, pp. 57-75, 1996.

93. Worst Case Length of Nearest Neighbor Tours for the Euclidean Traveling Salesman Problem. SIAM Journal on Discrete Mathematics, volume 10, number 2, pp. 171-179.

94. S. Reiter and G. Sherman. Discrete optimizing. SIAM Journal on Applied Mathematics 13, 864-889, 1965.

95. R.L. Karg and G.L. Thompson. A heuristic approach to solving travelling salesman problems. Management Science 10, 225-248, 1964.

96. Nesetril J., Poljak S. On the Complexity of the Subgraph Problem. -Comment. Math. Univ. Carol., 1985, 26, №2, pp. 415-419.

97. Patil H.P. Isomorphisms of duplicate graphs with some graph valued functions. J. Comb. Inf. And Sys. Sci., 1985, 10, №1-2, pp. 36-40.

98. Read R.C., Corneil D.G. The Graph Isomorphism Desease. J. Graph Theory, 1, 1977, pp. 339-363.

99. Rempel Joachim A heuristic 0(n5)-algorithm for nonisomorphism testing of graphs. "Graphs and Hipergreaphs and Appl. Proc. Conf. Graph Theory, Eyba, Oct, lth-5th" Leipzig, 1985, pp. 130-136.

100. Rigby M.J., Mallion R.B., Waller D.A. On the Quest for on Isomorphism Invariant which Characterizes Finite Chemical Graphs. -Chem. Phys. Lett., 1978, 59, №2, pp. 316-320.

101. Syslo Maciej M. The subgraph isomorphism problem for outerplanar graphs. Theor. Comput. Sci., 1981, 17, №1, pp. 91-97.

102. Tinhofer G. Graph isomorphism and theorems of Birkhoff type. -Computing, 1986, 36, №4, pp.285-300.

103. Tinhofer G. Zur Bestimmung der Automorphismen eines Endlichen Graphen. Computing, 15, №2, 1975, 147-156.

104. TSPBIB Home Page: http://www.ing.unlp.edu.ar/cetad/mos/ TSPBIB home.html

105. Turner J. Generalized Matrix Functions and the Graph Isomorphism Problem. SIAM J. Appl. Math., 16, №3, 1968, pp. 520-526.

106. Watanabe M. On the Characteristic Polynomial of a Multigraph. -Math. Rep. Toyama Univ., 1979, 2, pp. 87-94.

107. Weisfeiler B. On Construction and Identification of Graphs. Lecture Notes in Math., 1976.

108. Zemlyachenko V.N., Babai L. Moderately Exponential Bound for Graph Isomorphism. Proc. Conf. on Fundamentals of Computation Theory, 1982.