Содержание к диссертации
Введение
I. Сравнение топологической трассировки с другими методами 9
1.1. Чисто топологические методы 9
1.2. Метод гибкой трассировки 12
1.3. Технология Shape-based 16
1.4. Признак топологического трассировщика 17
1.5. Недостатки метода гибкой трассировки 19
1.6. Выводы 21
II. Модели печатного монтажа 22
2.1. Диаграммы «сущность —связь» 24
2.2. Топологическая модель печатного монтажа 26
2.3. Геометрическая модель печатного монтажа 32
2.4. Выводы 38
III. Синтез геометрической модели по данным топологической и синтез топологической модели по данным геометрической 39
3.1. Синтез геометрической модели печатного монтажа по данным топологической 39
3.1.1. Постановка задачи 39
3.1.2. Прокладка ребра 43
3.1.3. Добавление в триангуляцию межслойных переходов 46
3.2. Синтез топологической модели печатного монтажа по данным геометрической 52
3.2.1. Постановка задачи 52
3.2.2. Построение триангуляции рабочего поля 53
3.2.3. Добавление в триангуляцию вершин, представляющих межслойные переходы и точки ветвления проводников 54
3.2.4. Преобразование проводника 56
3.2.5. Удаление из триангуляции вершин, представляющих межслойные переходы и точки ветвления проводников 59
3.3. Выводы 64
IV. Оптимизация топологии печатного монтажа 65
4.1. Перекладка проводников 66
4.2. Методика отбора вариантов при оптимизации разводки соединений 68
4.3. Управление процессом перекладки проводников 74
4.4. Стратегия работы с вариантами разводки 79 4.5. Выводы 80
V. Практическое применение разработанных методов. сравнение сапр "topor" с другими системами трассировки 81
5.1. Методы отладки работы алгоритмов 81
5.2. Пошаговая отладка с визуализацией 84
5.3. Сравнение результатов автоматизированного проектирования печатных плат 87
5.4. Выводы 91
Заключение 92
Глоссарий 93
Список литературы 94
- Чисто топологические методы
- Диаграммы «сущность —связь»
- Синтез геометрической модели печатного монтажа по данным топологической
- Методика отбора вариантов при оптимизации разводки соединений
Введение к работе
Актуальность работы. Сложность радиоэлектронной аппаратуры неуклонно повышается. Не только увеличивается количество элементы на печатной плаїе или кристалле БИС. но и сами элементы становятся всё более сложными: увеличивается количество контактов микросхем при одновременном уменьшении расстояний между контактами. В результате задача трассировки соединений становится всё более сложной, возникает ос і рая необходимость в средствах качественного автоматизированного проектирования. Обычно повышение плотности печатного монтажа связывают с ужесточением проектных норм: уменьшением размера оіверстий и контактных площадок; уменьшением ширины проводников и торов: отказом от сквозных отверстий в пользу глухих и слепых межслойных переходов: увеличением количества слоев. Однако всё это приводит к увеличению себестоимости плат. Но существует ещё одна возможность - совершенствование моделей и алгоритмов автомашзированного проектирования печатного монтажа. Причём реализация указанной возможности не только не веде і к удорожанию изделий, а напротив, способна снизшь затраты на их производство.
Ещё в 70-х годах прошлого столетия в качестве альтернативы сеточным методам был предложен метод гибкой топологической трассировки (в более поздних зарубежных публикациях - river routing). Однако в рамках топологического подхода рассматривался только ситез пленарных укладок графа схемы, то есть последовательная укладка на плоскости фрагментов графа без пересечений. Предполагается, что до этого уже решена весьма непростая задача распределения соединений по слоям. Поскольку существующие методы решения задачи плана-ризации не позволяют учесть в полной мере конструктивно-технологические 01-раиичения, а также осуществлять оптимизацию полученных решений, подход не получил широкого распространения в промышленных САПР.
В работах, посвященных топологической трассировке, авторы пытались разрешить все возникающие проблемы в рамках єдине і венной модели. Решение проблем существенно упрощается, если для решения различных задач использовать различные модели. Например, топологическая модель позволяет эффективно решать задачи прокладки проводников и ошимизации топологии, но не позволяет в полной мере учитывать конструктивно-іехнологические ограничения, а учет точной іеометрии проводников и их редактирование может осущеспзляїься на др\гой модели - геометрической, которая лучше приспособлена для зтих целей. При этом приобретает особую важность задача синтеза одной модели по данным Др>гой.
Поскольку разработка топологии печатного монтажа - процесс итерационный, включающий чередование автоматических и интерактивных процедур, обеспечение интеграции процессов оптимизации и редактирования в системе і покой іопологической трассировки являеіся актуальной задачей.
л^^4актираванттяга-так-
Цели и шдачи исследования Целью диссер і анионной работы является разработка ал горім мов синтеза моделей печатного монтажа, позволяющих возоб-
новлять процесс ошимизации разводки соединении по
Ь"
.
Щ ft
же разрабоїка методов, позволяющих получать более качественные результаты проектривання іополоіии печатного монтажа.
Досги/кение указанной цели предполагает решение следующих основных задач'
-
Анализ применяемых моделей и алгоритмов трассировки соединений )злов Р')С на печашых іілаїах и микросборках;
-
Разработка моделей печатного монтажа, позволяющих эффективно решать задачи оптимизации и редактирования топологии печатного монтажа в сисіеме і покой тополої ической трассировки;
-
Разработка алгоритмов синтеза топологической модели печатного монтажа по данным геомеїрической модели и алгоритмов синтеза іеометрической модели по данным топологической модели;
-
Разработка меюдов локальной коррекции юнологии печатного моніажа;
^) Разработка методики отбора вариантов при оптимизации разводки соединений,
6) Реализация программных средств, обеспечивающих интеграцию процессов омтмизации и редактирования топологии печатного монтажа.
Методы исследования. Для решения поставленных задач использовались аппараты теории графов, векторной алісбрьі и аналитической геометрии, методы оптимизации на графах, исследования операций и искусственного инісллекта. Разработка программных средств проводилась с помощью обьекіно-ориен і ированної о программирования
Научная повита представляемой диссертационной работы заключается в следующем-
-
Разрабоїана юпологическая модель печатного монтажа, позволяющая эффективно решать задачи оптимизации топологии, и геометрическая модель, позво-тяющая осуществлять эффективный контроль метрических ограничений;
-
Разработаны алгоритмы синтеза топологической модели печатного монтажа по данным і еометрической модели и синтеза геометрической модели по данным юпологической;
-
Разработана методика о і бора вариантов при многокритериальной оптимизации разводки соединений, позволяющая получать целесообразное множество варианте разводки, оптимальных для разных функционалов.
На тщиту выносятся следующие положения:
-
І Іредложенпьіе топологическая и геометрическая модели печатного монтажа
-
Предложенные алгоритмы синтеза моделей позволяют синтезировать юполо-гическлю модель по данным геометрической, и геометрическую по данным то-ПО.ЮІ ической.
-
Предложенная меюдика отбора вариантов при многокритериальной оптимизации разводки соединений позволяет получать целесообразное множество вариантов разводки, оптимальных для разных функционалов.
Практическая ценность работы состоит в создании программных средств, іюзво іяіошііч поочередно использовать авюматические и интерактивные процедуры оптимизации и редактирования топологии печатного монтажа. Указанные
программные средства входят в состав САПР "TopoR". Применение разработанных средств обеспечивает существенное сокращение сроков проектирования печатных \ їлов РОС. повышение надёжности, улучшение качества, снижение ) ровня перекрёстных электромагнитных помех.
Реализация реіультатов работы. Результаты диссертационной рабоїьі в виде конкретных положений, выводов, методов, алгоритмов, машинных программ и расчетных данных внедрены в инженерную практику и исполыуются на промышленных предприятиях Москвы, Санкт-Петербурга Нижнего Новіорода, 1>лы, Рязани и Киева, а также в учебном процессе СПбГУАП и СПбГЭТУ (ЛЭТИ). Акты, подтверждающие внедрение, приведены в приложении.
Апробация работы. Основные положения и результаты диссертационной работы докладывались и были одобрены на следующих конференциях:
III научно-практической конференции "Современные информационные и электронные технологии", г. Одесса, 2002г.;
VI международной научно-практической конференции "Сисіемьі и средства передачи и обработки информации", г. Одесса, 2002г.;
9-й международной конференции "Современные технологии обучения", С.-Петербург, 2003 г.;
4-й международной НПК "Современные информационные и электронные технологии", Одесса, 2003 г.;
VII международной научно-практической конференции "Сисіемьі и средства передачи и обработки информации", і. Одесса, 2003г.;
Международной научно-технической конференции ИПИ(САЦ5)-2003 "Информационные технологии в управлении жизненным циклом изделий", С -Петербург, 2003г.;
Всероссийской научно-практической конференции "Информационные технологии в российской промышленности", С.-Псісрбург, 2004 і.;
5-й международной ППК "Современные информационные и электронные технологии". Одесса, 2004 г.;
III международном симпозиуме "Аэрокосмические приборные техноло-I ни". С.-Петербург, 2004 г.;
Международной научно-практической конференции "Фундаментальные и прикладные проблемы приборостроения", Сочи, 2004 г.;
VIII международной научно-практической конференции "Системы и средства передачи и обработки информации", Одесса, 2004 г.;
6-й международной НПК "Современные информационные и электронные іехнологии", Одесса. 2005 г.
Публикации По теме диссертации опубликовано 22 на}чные работы, ш них - 1 авторское свидетельство, I статья и тезисы к 20-ти докладам на меж-т\ народных научно-технических конференциях.
Структура и объем диссертации. Диссертационная работа сосюиі из введения, пят глав, заключения, списка литераіурьі. включающею I 10 наименований, и одного приложения. Основная часть работы изложена на 93 страницах машинописного текста. Рабо і а содержит 40 рисунков и 1 таблиц)
Чисто топологические методы
Строго говоря, для того, чтобы метод можно было назвать чисто топологическим, он должен совсем не оперировать такими метрическими понятиями, как длина, ширина или расстояние, а может иметь дело только с понятиями лежать между, обход по или против часовой стрелки (так как речь идёт о трассировке на ориентированной поверхности - плоскости) и, возможно, слой проводника и пересечение проводников. Такие методы были разработаны [9], в основном, они базируются на алгоритмах плоских укладок графов. Элемент обычно представляется множеством контактов, между которыми запрещено проведение соединений, а синтез топологии сводится к выбору такой укладки проводников относительно элементов, которая минимизирует количество пересечений проводников или требуемое число слоев коммутации (рис. 1.1). В случае однослойной трассировки задача размещения проводников зачастую совмещается с задачей размещения элементов.
Чисто топологические методы требуют для представления данных очень небольшого количества машинной памяти, а пространство допустимых решений настолько невелико, что появляется возможность говорить даже о поиске точного решения за приемлемое время. Под точным решением задачи трассировки понимается достижение не просто стопроцентной трассировки, но трассировки, точно минимизирующей выбранный критерий качества.
Как хорошо известно, традиционные методы трассировки не могут претендовать на точную оптимизацию разводки по какому-либо критерию качества (например, суммарной длины трасс или числа межслоиных переходов), они не всегда находят даже и просто стопроцентную разводку всех соединений. Современные системы автоматизированного проектирования печатных плат различаются между собой настолько незначительно, что, наблюдая процесс трассировки или её результат, трудно отличить одну САПР от другой. Такая схожесть систем является следствием схожести применяемых ими алгоритмов, а особенно схожести моделей коммутационного пространства печатной платы. [36]
Тем не менее, имеющиеся на производстве фотопостроители не умеют работать с топологическим описанием схемы. Для получения платы «в железе» на фотопостроитель необходимо передать чисто геометрическое описание всех проводников и контактных площадок. Переход от чисто топологического к чисто геометрическому представлению топологии называется задачей метризации и представляет очень большую трудность. Обычно печатная плата имеет заранее заданную, непростую форму, на ней могут присутствовать элементы с фиксированным расположением: разъёмы, технологические отверстия, зоны запрета трассировки. Поэтому может оказаться, что найденное топологическое решение не имеет допустимого отображения на заданный конструктив, то есть не может быть реализовано без нарушения технологических норм. С другой стороны, современные технологии обычно позволяют проводить дорожки между контактами элементов РЭЛ или под планарными контактами в другом слое. Отсутствие учёта такой возможности топологическим трассировщиком будет приводить к неоптимальным решениям из-за того, что чисто топологическая модель коммутационного пространства неадекватно отражает свойства реального конструктива.
Вышеуказанные недостатки привели к тому, что на практике чисто топологические методы применения не получили. Учёные пришли к выводу, что «кроме возможности описания топологической ситуации, модель рабочего поля должна содержать информацию о его метрических параметрах, характеризующих допустимую загруженность трассами промежутков между контактными точками, а также позволяющих определять длины трасс и выделять оптимальные из них» [10]. Такие модели и методы сначала стали называть топо-геометрическими или топографическими, но названия не прижились, и эти методы тоже включили в класс топологических, видимо, желая подчеркнуть, что они не являются чисто геометрическими.
Диаграммы «сущность —связь»
Все структуры данных в работе описаны диаграммами «сущность-связь». Сущности - это нумерованные множества, на диаграмме они представляются прямоугольниками. В заголовке прямоугольника указано название сущности. В нижней части прямоугольника перечислены атрибуты данной сущности. Связи между сущностями отражены стрелками.
Тонкая стрелка представляет связь "многие к одному", такая связь реализуется одним массивом, одна сущность служит индексом массива, а другая - значением элементов, имя массива указано рядом со стрелкой. Жирная стрелка представляет связь "один ко многим", такая связь может быть реализована разными способами, конкретная реализация указана рядом со стрелкой.
Пунктирная стрелка представляет вычислимую связь, такая связь определяется соглашениями, массивы для её реализации не требуются. Например, если над стрелкой указано 1:2, то это значит, что на один элемент левой сущности приходится два элемента правой сущности, и соответствующий индекс вычисляется умножением или делением на 2. Примером таких сущностей служат ребро (EDGE) и дуга (ARC) графа, представленные на диаграмме (рис. 2.2). Ещё одна сущность - вершина графа (ТОР), у которой согласно диаграмме есть атрибут Dot_top, определяющий координаты вершины. Связь между вершиной и дугой осуществляется тремя массивами. По номеру дуги через массив TopOut можно определить вершину, из которой дуга выходит. Все выходящие из вершины дуги можно определить по массивам ArcOut (первая выходящая дуга), и ArcRolI (следующая по часовой стрелке выходящая дуга).
Топологическая модель коммутационного пространства основывается на триангуляции Делоне (рис. 2.3) рабочего поля. Триангуляция Делоне — это такое разбиение плоскости на треугольные грани, что окружность, описанная вокруг любой грани не содержит внутри себя вершин других граней (рис. 2.4). Триангуляция Делоне может быть получена из любой другой триангуляции с помощью последовательности так называемых флипов. Флипом ребра называется замена этого ребра на ребро, соединяющее противолежащие вершины инцидентных этому ребру граней (рис. 2.5). Количество рёбер в триангуляции меньше, чем утроенное число вершин, количество граней - меньше, чем удвоенное число вершин.
Триангуляция Делоне обладает многими полезными свойствами, в том числе, и тем свойством, что любая вершина триангуляции всегда соединена ребром с ближайшей к ней вершиной. А это позволяет использовать такую структуру для быстрого определения расстояния между вершиной и ближайшими к ней вершинами, причём, узнать точную величину этого расстояния, а не только ответить на вопрос: "Не меньше ли это расстояние, чем заданная величина h?". Вершинами триангуляции выступают контакты и барьеры. Круглые контакты представляются одной вершиной, некруглые - несколькими.
Топологическая модель печатного монтажа является совмещённой топологией. В качестве вершин триангуляции выступают контакты с обеих сторон платы, а проводники, проходя друг над другом в разных слоях, образуют пересечение, называемое крестом типа WW(CROSSJWW). Существуют также кресты типа WA(CROSS_WA), которые являются пересечениями проводника с ребром триангуляции. Кресты содержат информацию о слоях образующих их проводников, и состоят из четырёх хвостов (TAIL). Топологический путь проводника на плате представляется двусвязным списком хвостов, определяющим их смежность (рис. 2.7.).
Как видно из рисунка на концах проводников тоже есть хвосты, особого типа WIRE_TAIL. Также хвосты есть и на концах рёбер, их тип ARC_TAIL. Точки ветвления проводников представлены в модели как вершины (TOPS), не включённые в триангуляцию. Так как точки ветвления проводников в процессе оптимизации часто порождаются и удаляются, их включение в триангуляцию сильно бы усложнило процесс перекладки проводника.
Совмещённая топология позволяет эффективно решать задачи оптимизации путей проводников. Оптимизация разводки соединений на этой модели состоит из последовательных перекладок проводников и переслоения с целью уменьшения количества межслойных переходов. Для решения первой задачи, то есть определения нового пути проводника, достаточно задать список смежности хвостов и определить слои проводников на полученных крестах. Для задачи переслоения преобразование модели заключается в изменении атрибутов слоя крестов и ветвлений. В то же время, совмещённая топология не содержит необходимых данных для получения конечного результата. В модели даже не присутствуют межслойные переходы.
Синтез геометрической модели печатного монтажа по данным топологической
Проблема синтеза геометрической модели печатного монтажа по данным топологической заключается в определении геометрии проводников и местоположения межслойных переходов. При этом не ставится задачи получения проводников минимальной длины, то есть представления проводника отрезками и дугами, так как эта задача хорошо решается на этапе геометрической коррекции. Для определения координат проводника достаточно вычислить координаты его пересечений с рёбрами и с другими проводниками. Координаты крестов WA, то есть пересечения проводника с ребром, рассчитываются исходя из количества пересечений на ребре и радиуса вершины (контакта, переходного отверстия). Координаты крестов WW (пересечение проводников), а также координаты ветвлений рассчитываются при помощи силового алгоритма [80]. Силовой алгоритм расчёта пересечений проводников выбран из-за планарности графа, образованного вершинами-пересечениями и рёбрами-участками проводников. Расчёт производится по следующим формулам
Проводится несколько итераций расчёта. Такой способ даёт хорошую наглядность (рис. 3.1). Далее необходимо произвести расслоение топологии, то есть назначить проводникам слои, добавить межслойные переходы и точки ветвления проводников.
Из-за того, что во время оптимизации разводки соединений нет полного контроля размеров переходных отверстий, могут возникать наложения межслоиных переходов друг на друга, что является нарушением технологических ограничений. Поэтому необходимо принять меры для более равномерного расположения переходных отверстий по площади печатной платы.
Таким образом, задачами синтеза геометрической модели печатного монтажа являются: Расчёт геометрической формы проводников. Определение положения межслоиных переходов. Более равномерное распределение межслоиных переходов.
На этапе оптимизации трассировки могут быть удалены некоторые рёбра триангуляции (рис. 3.2). Это связано с тем, что эти рёбра не изменяют топологию проводников. Во время перехода к геометрическому этапу, такое нарушение триангуляции Делоне помешает корректному добавлению переходных отверстий в качестве вершин триангуляции. Поэтому, прежде всего, необходимо восстановить удалённые рёбра.
Под прокладкой ребра понимается добавление ребра триангуляции в структуру данных совмещённой топологии, то есть с уже проложенными проводниками. Эта операция требуется при восстановлении удалённых рёбер, при добавлении новых вершин в триангуляцию, а также при флипах рёбер. При прокладке ребра ставится задача минимизации числа пересечений с проводниками. Это связано как с экономией памяти, так и с увеличением быстродействия при использовании полученной модели.
Для определения проводников, которые будут пересекаться с прокладываемым ребром, можно использовать геометрический способ. Он состоит в простой проверке на пересечение отрезков, представляющих ребро и участки проводников. Из рисунка 3.3 видно, что геометрический способ не даёт минимума пересечений. Альтернативный способ решения задачи — определение пересекаемых проводников топологически. При таком способе используется волновой алгоритм [2]. Из одной вершины ребра распространяется волна, узлами которой являются хвосты дуг, проводников, крестов WA и WW. Алгоритм прокладки ребра АО в грани АВС (рис. 3.3).
1. Включить в начальный фронт волны хвосты между дугами АС и АВ , а также хвост дуги АС .
2. Распространять волну, пока не достигнута целевая вершина 0 : Для каждого узла текущего фронта Перейти к хвосту по часовой стрелке Добавить узел к новому фронту Пока не достигнут хвост узла или не достигнута вершина 0 о Найти смежный хвост о Перейти к хвосту по часовой стрелке о Если хвоста и смежного с ним хвоста не было в предыдущих фронтах, и это не хвост дуги, то добавить узел к новому фронту, Перейти к новому фронту.
3. Расставить кресты: Для каждого узла найденного пути о Вставить хвосты нового креста WA между двумя хвостами узла, о Определить атрибуты слоя и принадлежность проводнику. о Перейти к родителю узла.
4. Сформировать циклы хвостов вокруг вершин 0 и А ( хвост, по которому была достигнута вершина 0 , является предыдущим для дуги ОА . Хвост дуги АС , который является родительским для узла, откуда была достигнута вершина 0 , - предыдущий хвост для дуги АО ).
Методика отбора вариантов при оптимизации разводки соединений
Качество разводки связей на печатной плате нельзя охарактеризовать каким-то одним параметром. Требуется учитывать и суммарную длину проводников, и количество переходных отверстий, и количество связей, проведённых с нарушениями технологических норм или не проведённых вовсе, и множество других параметров.
Итерационные алгоритмы трассировки начинают с какого-то варианта разводки (например, с отсутствия трасс) и последовательно применяют шаги локальной оптимизации, такие как прокладка проводника, снятие проводника с проведением его по-другому и т.п. Шаг оптимизации обычно не может улучшить одновременно все оцениваемые параметры, например, для уменьшения длины проводника приходится добавлять межслойный переход, или наоборот, чтобы убрать переход, приходится увеличивать длину проводника.
Неприятной особенностью методов локальной оптимизации является «застревание» в локальных минимумах, когда качество разводки ещё далеко от совершенства, но в то же время никакой шаг локальной оптимизации не может привести к его улучшению. Например, на рисунке 4.2 слева показан типичный «клинч» двух проводников. Перекладка ни одного из двух проводников не может перевести топологию в ситуацию, показанную на том же рисунке справа.
Разные последовательности шагов могут приводить в разные локальные минимумы, поэтому для улучшения имеющегося варианта топологии целесообразно опробовать разные последовательности оптимизации. Современные компьютеры в состоянии генерировать очень много вариантов разводки в секунду, поэтому требуется как-то определять, какие варианты следует сохранить для дальнейшего или окончательного использования, а какие можно отбросить. Для этого необходимо уметь сравнивать варианты, отделяя перспективные от явно неоптимальных. Широко распространены два подхода к сравнению вариантов: по критерию Парето и по интефальному критерию [27].
Вариант называется оптимальным по Парето, если он лучше каждого из других вариантов, хотя бы по одному оцениваемому параметру. На рисунке 4.3 жирно отмечены варианты, оптимальные по Парето для случая двух параметров. Чем больше параметров, тем больше вариантов оказываются оптимальными по Парето, хотя очевидно, что не очень разумно за малое улучшение одного параметра платить офомным ухудшением другого.
В альтернативном подходе все параметры сводят в один интефальный функционал Ф = 2]Й/УІ rRQfi оцениваемые параметры, а а; — весовые коэффициенты. Один из коэффициентов обычно полагают равным 1 или нормируют коэффициенты каким-то другим способом. На рисунке 4.4 наклонной прямой обозначена линия уровня интегрального функционала для одного из значений коэффициента (для случая двух оцениваемых параметров достаточно выбора одного коэффициента, который определяет наклон прямой). Все варианты, лежащие на одной и той же линии уровня, имеют одинаковое значение функционала. Понятно, что обычно оптимальным оказывается только один из вариантов (выделен жирно).
Трудность использования интегрального критерия состоит в том, что, вообще говоря, не существует универсального обоснованного способа выбора весовых коэффициентов, так как зачастую невозможно выразить ценность одного параметра через другой. Как, например, оценить, сколько миллиметров длины проводников «стоит» одно переходное отверстие? Ясно, что для плат разного вида, сложности, размера и технологии — да даже и для разных разводок одной и той же платы - эта стоимость будет различной. С другой стороны, нет нужды подбирать коэффициенты с чрезмерно большой точностью, так, на рисунке 4.4 видно, что при небольших изменениях коэффициента оптимальным остаётся выделенный вариант. Поэтому выглядит нелепым, когда конструкторы тщательно подбирают «самые-самые лучшие на все случаи жизни» наборы коэффициентов, бережно хранят их и обмениваются друг с другом.
