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

/ • Л//'> ' У У у /

Калининградский Государственный Технический Университет

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

Горбачев Андрей Александрович

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

05.13.12. - Системы автоматизации проектирования ДИССЕРТАЦИЯ

на соискание ученой степени кандидата технических наук

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

НОРЕНКОВ И.П.

Калининград 1999

СОДЕРЖАНИЕ

ВВЕДЕНИЕ...........................................................................................5

1. АНАЛИЗ МЕТОДОВ ТРАССИРОВКИ ПЕЧАТНЫХ ПЛАТ.........14

1.1. Место задачи трассировки в процессе разработки радиоэлектронной аппаратуры и ее особенности...................14

1.2. Получение списка соединений.................................................20

1.3. Расслоение.................................................................................23

1.4. Очередность прокладки соединений.......................................26

1.5. Трассировка соединений..........................................................29

1.5.1. Волновые алгоритмы......................................................29

1.5.2. Алгоритмы трассировки по магистралям......................36

1.5.3. Алгоритмы канальной трассировки...............................38

1.5.4. Комбинированные алгоритмы ........................................41

1.6. Выводы к главе 1.......................................................................44

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

2.1. Математическая модель печатной платы................................46

2.1.1. Способ задания монтажно-коммутационного поля печатной платы...............................................................46

2.1.2. Аппарат фиктивных длин...............................................53

2.2. Алгоритм отображения печатной платы в граф.....................58

2.3. Трассировка печатных проводников........................................64

2.3.1. Алгоритм пространственной трассировки.....................64

2.3.2. Структура комплекса алгоритмов пространственной трассировки....................................................................70

2.3.3. Количественная оценка основных параметров алгоритма пространственной трассировки...............70

2.4. Выводы к главе 2...................................................................75

3. АЛГОРИТМ СОВМЕСТНОЙ ТРАССИРОВКИ ДВУХ ПАР КОНТАКТНЫХ ПЛОЩАДОК, ПРИНАДЛЕЖАЩИХ РАЗНЫМ ЭЛЕКТРИЧЕСКИМ ЦЕПЯМ...............................................77

3.1. Макродискретное представление печатной платы....................77

3.1.1. Способ задания макродискрет..........................................77

3.1.2. Отображение печатной платы в граф...............................80

3.1.3. Определение фиктивных расстояний на графе, образованном макродискретами.......................................87

3.2. Трассировка макродискрет.........................................................89

3.2.1. Алгоритм трассировки макродискрет..............................89

3.2.2. Алгоритм "сшивания" макродискрет...............................95

3.2.3. Трассировка внутри макродискрет..................................96

3.3. Обобщенная схема и количественные характеристики комплекса алгоритмов совместной трассировки.......................98

3.3.1. Структура комплекса алгоритмов совместной трассировки.......................................................................98

3.3.2. Оценка эффективности алгоритма совместной трассировки.....................................................................103

3.4. Выводы к главе 3.......................................................................105

4. РАЗРАБОТКА ЭКСПЕРИМЕНТАЛЬНОГО ИНТЕРАКТИВНОГО ПРОГРАММНОГО КОМПЛЕКСА.................................................106

4.1. Общие требования и принципы построения специализированного программного обеспечения.................106

4.2. Экспериментальный интерактивный программный комплекс..................................................................108

4.2.1. Структура программного комплекса..............................108

4.2.2. Структура данных...........................................................112

4.3. Организация взаимодействия с пользователем.......................116

4.3.1. Управление вводом и корректировкой данных............116

4.3.2. Управление отображением и трассировкой соединений......................................................122

4.4. Примеры практической реализации алгоритма пространственной трассировки...............................................131

4.5. Выводы к главе 4....................................................................139

ЗАКЛЮЧЕНИЕ....................................................................................140

ЛИТЕРАТУРА......................................................................................144

ПРИЛОЖЕНИЕ 1.................................................................................154

ПРИЛОЖЕНИЕ 2...............................................................180

- 5 -ВВЕДЕНИЕ

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

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

1. Многослойные ППЛ являются основным средством коммутации в самом широком смысле этого понятия в РЭА, ЭВТ, приборостроении и т.д. В ближайшее время, по всей видимости, не появятся другие виды коммутации успешно конкурирующие с ППЛ по ряду таких параметров, как технологичность, стоимость, серийноспособность, электрические параметры и т.п.

2. Возникшие позднее методы проектирования интегральных схем (ИС), больших интегральных схем (БИС) и сверхбольших интегральных схем (СБИС) основывались в силу частичной общности задач на методах проектирования ППЛ, математических моделях электрических схем, оптимальных методах размещения, трассировки и т.д.

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

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

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

5. Области радиоэлектронного приборостроения и ВТ являются наиболее "чувствительными" к достижениям научно-технического прогресса. Моральное устаревание техники в этих областях происходит значительно быстрее, чем в других. Постоянно повышающаяся степень интеграции ППЛ и сокращение сроков их разработки выдвигают на передний план более жесткие требования к процессу их проектирования, в том числе - повышению процента трассируемых соединений при ограниченном количестве слоев ППЛ и их разнородном элементном насыщении. Учет этих требований делает необхо-

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

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

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

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

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

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

Отсутствие универсальных систем трассировки, дающих результаты 100%-ой разводки для различных функциональных узлов прежде всего связано с несовершенством алгоритмической базы и недостаточным быстродействием используемых ЭВМ. В этой связи является весьма актуальной проблема разработки алгоритмов автоматизированной дотрассировки печатных проводников, повышающих процент и качество трассируемых соединений. Для практического использования таких алгоритмов ввиду их высокой степени сложности большое значение имеет степень их "информационной согласованности" с базовыми алгоритмами трассировки.

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

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

В соответствии с поставленной целью решались следующие задачи:

1. Разработка метода пространственной трассировки, ориентированного на ППЛ, имеющие высокую степень интеграции и ограничение на количество слоев.

2. Разработка математической модели ППЛ, позволяющей использовать данный метод, а также формализовать условия, ограничения и критерии при пространственной трассировке.

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

4. Разработка математической модели ППЛ, ориентированной на применение метода совместной трассировки двух пар КП, принадлежащих разным электрическим цепям.

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

6. Проверка работоспособности комплекса алгоритмов и выполнение контрольных примеров.

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

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

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

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

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

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

Практические результаты диссертационной работы в виде демонстрационного программного комплекса, методики подготовки исходных данных и руководства пользователя внедрены в экспериментальное производство печатных плат специального назначения на ОАО "МЕХБАНК" (г. Калининград), в практику составления технических условий на изготовление и монтаж ППЛ на ОАО "СИСТЕМА" (г. Калининград), а также в учебные процессы в Балтийском Военно-Морском Институте (г. Калининград) и в Калининградском Государственном Техническом Университете в качестве составляющей части лабораторного практикума.

Результаты диссертационной работы докладывались на следующих конференциях и семинарах: ХУ11 Межвузовская конференция профессорско-преподавательского состава, научных и инженерно-технических работников, аспирантов калининградских вузов МРХ СССР (Калининград, 1989); Всесоюзное совещание-семинар молодых ученых и специалистов "Разработка и оп-

тимизация САПР и Г АЛ изделий электронной техники на базе высокопроизводительных мини и микро ЭВМ" (Воронеж, 1989); Отраслевая научно-практическая конференция "Применение в САПР типовых и объектно-независимых программно-технических комплексов" (Омск, 1989); Х1У объединенный республиканский семинар "Прикладная информатика автоматизированных систем проектирования, управления, программированной эксплуатации" (Калининград, 1989); Республиканская конференция "Разработка новых информационных технологий проектирования и управления на промышленных и разрабатывающих предприятиях" (Киев, 1990); 2-ая Республиканская научно-техническая конференция "Функционально-ориентированные вычислительные системы" (Харьков - Алушта, 1990); 4-ая Всесоюзная школа "Проектирование автоматизированных систем контроля и управления сложными объектами" (Харьков - Туапсе, 1990); Всесоюзная научно-техническая конференция "Микросистем