Содержание к диссертации
Введение
I. Установление изоморфности различных описаний II
1.1. Изоморфность мультиграфов 12
1.2. Избыточность мультиграфового представления принципиальной схемы 24
1.3. Выводы
II. Разработка алгоритма определения изоморфности описаний топологии и принципиальной схемы 29
2.L Изоморфность гиперграфов 29
2.2. Инварианты матрицы инцидентности гиперграфа 33
2.3. Компактное представление гиперграфа 36
2.4. Алгоритм определения изоморфности гиперграфов 39
2.5. Выводы 42
III. Использование функциональной эквивалентности контактов микросхем 43
3.1. Методы и критерии 44
3.2. Использование функциональной эквивалентности контактов микросхем на этапе компоновки 46
3.2.1. Определение расстояний на графовой модели схемы 47
3.2.2. Алгоритм решения задачи назначения эквивалентных контактов 51
3.2.3. Выбор метода решения задачи коммивояжера 52
3.3. Использование функциональной эквивалентности контактов микросхем на этапе размещения 66
3.3.1. Оценка числа пересечений ребер двудольного графа 66
3.4. Использование функциональной эквивалентности контактов микросхем на этапе трассировки 76
3.5. Выводы 81
IV. Контроль конструктивно- технологических нарушений в топологии печатного монтажа 82
4.1. Особенности контроля конструктивно-технологических ограничений в гибкой топологической трассировке 82
4.2. Алгоритм проверки конструктивно-технологических нарушений в топологии печатного монтажа 87
4.3. Выводы 94
V. Программный комплекс топологической трассировки печатных плат TopoR 95
5.1. Основные сведения о системе TopoR 95
5.1.1. Требования системы к оборудованию 96
5.1.2. Технические характеристики и ограничения . 96
5.1.3. Режимы и функции 97
5.2. Программа проверки выполнения конструкторско-технологических ограничений (DRC) 101
5.3. Выводы 105
Заключение 106
Список литературы
- Избыточность мультиграфового представления принципиальной схемы
- Компактное представление гиперграфа
- Использование функциональной эквивалентности контактов микросхем на этапе компоновки
- Особенности контроля конструктивно-технологических ограничений в гибкой топологической трассировке
Введение к работе
Техническое проектирование является важнейшим этапом разработки радиоэлектронных средств (РЭС) различного назначения. На этом этапе определяется конструктивная реализация проектных идей и решений, формируются основные производственно-экономические и эксплуатационные характеристики будущих изделий. В результате технического проектирования описание (модель) разрабатываемого объекта достигает наиболее полного и детального уровня, необходимого для непосредственного материального воплощения проекта. Многообразие требований, ограничений и компонентов получают здесь конкретное единство.
Сложность радиоэлектронной аппаратуры неуклонно повышается. Не только увеличивается количество элементов на печатной плате или кристалле БИС, но и сами элементы становятся всё более сложными: увеличивается количество внешних контактов микросхем при одновременном уменьшении расстояний между контактами. В результате задача синтеза топологии соединений становится всё более и более трудной.
Вероятность того, что разработанная топология сразу же будет корректной, очень мала, так как невозможно полностью исключить «человеческий фактор» ни в одном методе проектирования, сколь бы автоматизированным он ни был. А человеку, как известно, свойственно ошибаться.
При проектировании топологии печатных плат (ГШ) и интегральных схем (ИС) могут возникнуть ошибки, связанные с потерей соединений, с прокладкой лишних соединений и самое худшее - с перестановкой
5 соединений. Тогда возникает ситуация, когда общее число связей и элементов соответствует заданному, но схема не работает. Поэтому важно еще до начала этапа изготовления фотошаблонов убедиться, что проектируемое устройство будет выполнять требуемые функции. Другими словами, удостовериться, что созданная топология соответствует реализуемой электрической схеме и заданным конструктивно-технологическим ограничениям (КТО).
Следовательно, необходимость введения в маршрут проектирования этапа верификации топологии вполне очевидна.
Существующие подсистемы верификации топологии, входящие в состав представленных на рынке САПР ориентированы в значительной степени на интерактивную верификацию принципиальной схемы и топологии, что ведет к неоправданно высоким временным затратам. Проверка соблюдения КТО в большинстве САПР осуществляется на ортогональной топологии без дуг окружностей, либо с квадрантными (четверть окружности) дугами. Все это не соответствует современным требованиям к качеству топологии печатного монтажа.
В современных САПР недостаточно используются возможности оптимизации топологии печатного монтажа, связанные с переназначением функционально эквивалентных контактов полузаказных БИС. Поскольку при решении указанной задачи изменяется принципиальная схема устройства, ее результаты необходимо учитывать при решении задачи верификации топологии.
Целью диссертационной работы является исследование и разработка моделей, алгоритмов и программных средств верификации топологии узлов РЭС, выполненных на основе изделий микроэлектроники с применением печатного монтажа или гибридно-интегральной технологии, а также расширение возможностей оптимизации топологических решений за счет переназначения функционально эквивалентных контактов микросхем.
В соответствии с этим в работе ставились и решались следующие задачи: анализ применяемых моделей и алгоритмов верификации принципиальных схем и топологии узлов РЭС на печатных платах, микросборках и СБИС; построение адекватных требованиям топологического синтеза моделей электрических схем проектируемых узлов, используемых на этапе верификации; разработка эффективного алгоритма определения изоморфности гиперграфов как теоретической основы задачи установления соответствия описания топологии печатного узла его принципиальной схеме; разработка методов получения оценки числа пересечений ребер линейной и циклической реализаций двудольного графа; разработка эффективных методов назначения функционально эквивалентных контактов микросхем на различных этапах проектирования топологии печатного монтажа; разработка эффективных структур данных и алгоритмов контроля конструктивно-технологических нарушений в топологии печатного монтажа; создание и адаптация к промышленным условиям эксплуатации быстродействующих программных средств автоматической верификации топологии узлов РЭС на печатных платах,
7 микросборках и СБИС.
Научная новизна диссертационной работы заключается: в обосновании использования гиперграфовой модели электрической схемы устройства при решении задачи верификации печатных узлов РЭС; в разработке алгоритма определения изоморфности гиперграфов; в разработке методов получения оценки числа пересечений ребер линейной и циклической реализаций двудольного графа; в разработке методов переназначения функционально эквивалентных вентилей и контактов микросхем на различных этапах синтеза топологии печатного монтажа; в разработке эффективных структур данных и алгоритмов контроля конструктивно-технологических нарушений в топологии печатного монтажа.
Практическая ценность работы состоит в создании прикладных программ, предназначенных для решения задачи верификации топологии печатного монтажа в автоматическом режиме. Применение разработанных программ обеспечивает улучшение качества и сокращение сроков проектирования СБИС и печатных узлов РЭС.
Результаты диссертационной работы в виде конкретных положений, выводов, методов, алгоритмов, машинных программ и расчетных данных внедрены и инженерную практику и используются на промышленных предприятиях в Москве, Санкт-Петербурге и Нижнем Новгороде, а также в учебном процессе СПбГУАП и СПбГЭТУ (ЛЭТИ). Акты, подтверждающие внедрение, приведены в приложении.
Основные положения и результаты диссертационной работы докладывались и были одобрены на следующих конференциях:
III Международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 1999г;
III научно-практической конференции "Современные информационные и электронные технологии", г. Одесса, 2002г.; VI международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 2002г.;
9-й международной конференции "Современные технологии обучения", С.-Петербург, 2003 г.;
4-й международной НПК "Современные информационные и электронные технологии", Одесса, 2003 г.; VII международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 2003г.;
Международной научно-технической конференции ИПЩСАЬЭ)-2003 "Информационные технологии в управлении жизненным циклом изделий", С.-Петербург, 2003г.;
Всероссийской научно-практической конференции "Информационные технологии в российской промышленности", С.Петербург, 2004 г,;
5-й международной НПК "Современные информационные и электронные технологии", Одесса, 2004 г.;
III международном симпозиуме "Аэрокосмические приборные технологии", С.-Петербург, 2004 г.;
Международной научно-практической конференции "Фундаментальные и прикладные проблемы приборостроения", Сочи, 2004 г.; - VIII международной научно-практической конференции "Системы и средства передачи и обработки информации", Одесса, 2004 г.; - 6-й международной НПК "Современные информационные и электронные технологии", Одесса, 2005 г.
По теме диссертации опубликована 21 работа, из них 4 статьи и 17 тезисов к докладам на международных научно-технических конференциях.
Диссертация состоит из введения, пяти глав, заключения и приложения. Текстовый материал изложен на 121 странице.
Во введении кратко освещен предмет исследования, обоснована актуальность темы диссертационной работы. Сформулированы основные положения, выносимые на защиту, научная новизна и практическая ценность результатов. Кратко описано содержание диссертации по главам.
В первой главе проводится анализ методов формальной верификации топологии печатного монтажа, а также анализ соответствия используемых моделей и критериев действительным целям верификации.
Вторая глава посвящена выбору модели представления топологии печатного монтажа и принципиальной схемы устройства в задаче верификации. Предложен метод определения изоморфности моделей.
Третья глава посвящена разработке методов переназначения функционально эквивалентных вентилей и контактов микросхем на различных этапах проектирования топологии печатного монтажа.
В четвертой главе рассмотрены вопросы контроля конструктивно-технологических нарушений в топологии печатного монтажа.
Пятая глава посвящена вопросам организации программного обеспечения подсистемы автоматизированной верификации топологии
10 печатного монтажа, кроме того, в ней приведены результаты экспериментальных исследований разработанных алгоритмов и программ.
В заключении сформулированы основные научные и практические результаты работы.
В приложении даются сведения, подтверждающие использование полученных результатов в народном хозяйстве страны.
Избыточность мультиграфового представления принципиальной схемы
Покажем, что подобный мультиграф дает в общем случае существенно ошибочную оценку реального числа межсоединений. Модели электрической цепи: а) простая цепь; б) полный граф
Полный Я-вершинный граф имеет п{п— 1) / 2 ребер, в то время как построенное на вершинах этого же графа любое дерево, в виде кото 25 рого реализуется некоторая цепь, содержит П — \ ребер (рис.8). Отсюда количество "лишних" ребер в мультиграфе, описывающем WI цепей, т N = Z / = ukz!L( і) т = 2 ( - ,-2). (1) 1 = где ЇІІ - число элементов, связанных I -й цепью. Из (1) видно, что количественная избыточность мультиграфа по сравнению с адекватной моделью тем выше, чем больше звеньев (72.) в каждой из цепей.
Введем коэффициент, характеризующий степень избыточности мультиграфа электрической схемы. Назовем его коэффициентом адекватности
Из (2), в частности следует К Є (ОД], причем К=1 (N=0) соответствует случаю, когда все цепи в схеме однозвенные (соединяют два элемента) и мультиграф адекватно представляет электрическую схему. Пусть П - среднее количество звеньев в цепи 1 m n=-Yjni (з) Подставляя (3) в (2), имеем „ т(п-\) К=2 }— (4) X"1 2 -— І=І или К= =— , (5) П п-\ т где D — —/.(я. — и) можно определять как среднеквадра тичныи разброс количества контактов в цепях.
Таким образом, степень избыточности мультиграф а, моделирующего электрическую схему, непосредственно определяется средним значением и среднеквадратичным разбросом числа звеньев в цепях и может быть без труда подсчитана для каждой конкретной электрической схемы. Как видно из (5), для схемы с одинаковым средним количеством контактов в цепях мультиграф тем хуже (ошибочнее) описывает схему, чем выше разброс количества контактов в цепях (больше величина D).
В матрице смежности мультиграф а теряется информация о каждой из цепей и учитывается лишь вероятность появления некоторого соединения в пределах конкретной цепи. Это обстоятельство приводит, например, к тому, что две различных схемы могут описываться идентичными матрицами смежности мультиграфа. Пара таких схем представлена на рисунке 1.9 (а и б).
Матрица смежности мультиграфовой модели схем, изображенных на рис.9 и рис. 10, будет иметь вид:
1. Проведен анализ применяемых моделей и алгоритмов верификации принципиальных схем и топологии узлов РЭС на печатных платах, микросборках и СБИС.
2. Показана неадекватность мультиграфовой модели принципиальной электрической схемы, традиционно используемой при решении задач верификации топологии печатного монтажа и принципиальной схемы.
Представим схему соединений в виде гиперграфа Н{ХУК) (математическая модель М2\ где каждое ребро е. єЕ гиперграфа представляет собой некоторое подмножество вершин, инцидентных этому ребру. В М2 каждому ребру гиперграфа Н соответствует определенная электрическая цепь схемы соединений. При этом заранее не задается, как и в каком порядке будут соединены вершины, инцидентные данному ребру. Графически каждое ребро гиперграфа представляется в виде замкнутой кривой, охватывающей инцидентные ребру вершины. На рис. 11 показан гиперграф Н (математическая модель М2) для схемы соединений (рис. 10).
Компактное представление гиперграфа
Следует отметить, что матрицы инцидентности, описывающие схемы электрические принципиальные, обычно сильно разрежены. Например, современная СБИС может содержать десятки миллионов транзисторов. При этом любой столбец матрицы инцидентности, соответствующий некоторому компоненту схемы (транзистору) будет содержать только три единицы.
Таким образом, существует проблема хранения больших объемов данных и доступа к ним, таким образом, чтобы обеспечивалась достаточная скорость вычислительных процессов и, одновременно, экономия памяти.
Ниже предложен подход, основанный на использовании особых списковых структур данных, а так же виртуальной памяти, которые обеспечивают компактное хранение данных и более быстрый к ним доступ по сравнению с принятыми типами структур данных (стек, очередь, В-дерево, массивы, использующие динамическую память).
Предлагается использовать два типа списка: Массив (2.1) это массив описания начала строк списка, т.е. в данной структуре присутствует четыре строки списка. Первая строка начинается с 0-го элемента в массиве (2.2), вторая с 2-го и т.д. Элементы массива (2) А0 ... А5 могут быть либо информационными полями, либо ссылками на информационные поля, находящиеся в другом месте (оперативной памяти, виртуальной памяти, файле и т.п.).
4-ый элемент массива (2.1) со значением 6 имеет специфическое название - «сторож». Он служит для ссылки, как видно из рисунка, на несуществующий еще элемент в массиве (2.2). Благодаря этому сторожу отслеживается место положения конца списка.
Минусы данного представления состоят в том, что при вставке нового элемента и удалении старого необходимо сдвинуть массив (2.2) и перенумеровать массив (2.1). 2) Список, у которого известно начало строки и в котором у каждого элемента есть ссылка на следующий элемент.
В данном случае используется три массива. Первый массив (2.3) хранит начало строк списка, второй (2.4) хранит индекс следующего элемента и третий (2.5) хранит информационные поля об элементе. Значение N во втором массиве (2.4) соответствует концу строки и обычно N = -1.
Минусы данного представления состоят в том, что при вставке нового элемента необходимо пройти по всей строке до конца и вместо N вписать индекс нового элемента. Приходится хранить 3 массива.
Хранение и оперирование с информацией большого объема достигается использованием виртуальной памяти. Таким образом, все элементы, описанных выше массивов хранятся в виртуальной памяти, что обеспечивает высокое быстродействие при обработке данных.
Схема в виде списка соединений может задаваться двумя способами: для каждого компонента задается список инцидентных ему цепей, или для каждой цепи задается список соединяемых ею компонентов.
Для того чтобы не потерять преимущества матричного представления, позволяющего, задав пару индексов, получить элемент без осуществления поиска, следует задавать оба описания. Каждый из вариантов описания будем задавать парой массивов. Один массив содержит списки цепей (компонентов), а второй -указатели на первый элемент списка.
Использование функциональной эквивалентности контактов микросхем на этапе компоновки
Для эффективного решения задач топологического проектирования необходимо иметь некоторую интегральную характеристику, учитывающую не только наличие или отсутствие непосредственной связи между парой вершин на графе (мультиграфе), но и транзитивную связность, а по возможности, и структуру графа в целом.
Наиболее простой способ определения степени близости вершин на графе - определение кратчайшего пути между ними. Найдя кратчай шиє пути между парами вершин, можно построить матрицу расстояний. Однако матрица расстояний не несет информации в явном виде о степени связности графа и его частей, о числе путей различной длины между вершинами. Так, например, добавление к некоторому графу G двусвязных компонент не изменяет в матрице смежности нового графа G подматрицы расстояний, соответствующей G.
Одним из параметров, косвенно характеризующих степень связности графа, является число путей длины / (/ = 1,2,..) между парой вершин. Пусть, например, вершины х,- и х, смежны. Если число путей длины 2 из хі в х - равно 3, то это означает, что Х(- и X, имеют три общих смежных вершины. Возведем матрицу смежности М=\ Шц графа С? в степень р. Значение элемента т]? соответствует числу путей длины р из вершины х;. в вершину X - [38]. Близость вершин X; и X. графа можно характеризовать набором т)? .
Недостатком подобного подхода является сравнительно высокая комбинаторная сложность и то обстоятельство, что т)- включает не только простые цепи, но и цепи с повторяющимися вершинами, т.е. щ и ш?\ имея одинаковое значение (т% —т? ), могут характеризовать окрестности разного радиуса.
Рассмотрим другой подход к определению степени близости вершин графа, особенностью которого является использование нетрадиционной метрики для определения расстояний на графе. Близость между парой вершин определяется на основе информации об отдаленности (близости) их по отношению к другим вершинам графа: чем больше суммарная разность расстояний до одноименных вершин графа, тем более удалены вершины друг от друга.
На основании этого положения предлагается следующая функция для определения расстояний на графе при решении задачи компоновки где bt- - "отдаленность" вершины я, от вершины х ; rki и гк- элементы матрицы расстояний (кратчайших путей) R. Полученную матрицу В = h назовем матрицей отдаленнос тей. Нетрудно убедиться, что малейшие изменения графа приводят к изменению всей матрицы В, т.е. элементы Ь.. являются в некотором смысле интегральными характеристиками близости вершин хг и д:.-, учитывающими структуру графа и реагирующими на ее изменения.
Rf отличаются только наличием дополнительных строк и столбцов в R . В то же время одноименные элементы матриц В и В различаются существенно. Так в В вершины 3 и 5 находятся на одинаковом удалении от вершины 1, в то время как в В вершина 3 оказалась существенно дальше. Это связано с наличием новой вершины 7 , которая как бы «оттянула» вершину 3 от вершины Г.
Особенности контроля конструктивно-технологических ограничений в гибкой топологической трассировке
Модель гибкой трассировки, в отличие от сеточных или, так называемых, Shape-based моделей, не приводит к образованию большого количества препятствий метрического характера, имеющих искусственное, а не естественное происхождение и возникающих вследствие жёсткой фиксации трасс. Когда некоторая трасса пересекает ребро макродискрета, фиксируется лишь сам факт пересечения, но не точные координаты трассы. Поэтому, если на ребре ещё осталось место, последующие трассы имеют возможность пересечь это же ребро справа или слева от данной трассы, как им окажется удобнее.
Важное отличие метода гибкой трассировки от других макротрассировок состоит в том, что на ребре фиксируется относительное расположение пересекающих проводников.
В методе гибкой трассировки геометрическая форма проводников не фиксируется, фиксируются лишь их топологические пути. Два пути называются топологически эквивалентными, если один из них можно перевести в другой с помощью непрерывной деформации, не пересекая при этом вершин разбиения (рис. 4.L).
В практике современного конструирования нашли применение три модели монтажного пространства: дискретное рабочее поле (ДРП), сканирующая модель и триангуляция Делоне (рис.4.2.). Точность контроля для ДРП напрямую зависит от шага сетки. При большом шаге точность не высока, а для малого шага требуется огромная память. Использование методов сканирования для контроля топологии оказывается длительным и чреватым ошибками.
Из названия ясно, что все грани триангуляции являются треугольниками. Окружность, описанная вокруг грани триангуляции Делоне не содержит внутри себя никаких вершин триангуляции (однако на самой окружности вершины лежать могут) (рис. 4.3). Триангуляция Делоне может быть получена из любой другой триангуляции с помощью последовательности так называемых флипов. Флипом ребра называется замена этого ребра на ребро, соединяющее противолежащие вершины инцидентных этому ребру граней (рис. 4.4).
Количество рёбер в триангуляции меньше, чем утроенное число вершин, количество граней - меньше, чем удвоенное число вершин.
Триангуляцию Делоне в общем случае можно построить за O(NlogN) операций, но в практически важном частном случае, когда вершины распределены в рабочей области почти равномерно, порядок количества операций уменьшается почти до линейного.
Триангуляция Делоне обладает многими полезными свойствами, в том числе, и тем свойством, что любая вершина триангуляции всегда соединена ребром с ближайшей к ней вершиной. А это позволяет использовать такую структуру для быстрого определения расстояния между вершиной и ближайшими к ней вершинами, причём, узнать точную величину этого расстояния, а не только ответить на вопрос: "Не меньше ли это расстояние, чем заданная величина h?". Но, к сожалению, все преимущества триангуляции Делоне обесцениваются тем простым фактом, что вершины триангуляции - точки, а не отрезки. Это затрудняет её применение на практике. Кроме того, в ряде случаев на триангуляции невозможно обнаружить нарушения конструктивно-технологических нарушений. В некоторых случаях для обнаружения и устранения нарушений бывает достаточно осуществить флип ребра триангуляции (рис.4.5).
Таким образом, при топологической трассировке наряду со средствами контроля топологии на триангуляции (on line) необходимы дополнительные средства контроля, позволяющие проверить окончательный вариант для обнаружения и устранения ошибок, связанных с нечувствительностью используемой модели.
Задача. Задан набор контактов и принадлежность их цепям и компонентам. Кроме того, задан набор проводящих и непроводящих деталей (сегментов), расположенных в трассировочных плоскостях. У цепей и компонентов могут быть атрибуты. Неформальное описание задачи Требуется проверить, что все контакты каждой цепи надёжно соединены проводящими сегментами (или другим способом), что между проводящими сегментами разных цепей имеется надёжный зазор, и что между проводящими сегментами и барьерами или запретами имеется надёжный зазор. Требуется также сообщить о неразведённых цепях и о расположении ненадёжных соединений и ненадёжных зазоров.
Зазоры между непроводящими сегментами контролировать не требуется. В постановку задачи не входят: проверка зазоров между сегментами на нетрассировочных плоскостях; проверка непопадания межслойных переходов в зоны запрета переходов; поиск циклов в соединениях; проверка соблюдения тепловых и электромагнитных требований. Модель Имеется набор контактов, заданных их координатами и слойностыо. Каждый контакт принадлежит некоторой цепи и некоторому компоненту.
Задан набор проводящих и непроводящих сегментов, расположенных в логических слоях, отображаемых на трассировочные плоскости. Некоторым проводящим сегментам изначально приписана цепь. Имя цепи «?» означает, что контакт не задействован в схеме. Соединение незадействованных контактов должно индицироваться как ошибка.
Кластером будем называть набор проводящих сегментов, имеющих надёжное соединение. Будем считать, что все непроводящие сегменты составляют один специальный кластер запретов. Таким образом, кластеры бывают 4 видов: принадлежащие цепи не «?», принадлежащие цепи «?», не принадлежащие никакой цепи и запреты.
