Методы и алгоритмы пространственной трассировки печатных плат

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

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

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) — Всесоюзная научно-техническая конференция «Микросистема — 92 м (Томск — Калининград, 1992) — 4-ое Международное совещание-семинар «Инженерно-физические проблемы новой техники» (Москва, 1996) — 5-ое Международное совещание-семинар «Инженерно-физические проблемы новой техники» (Москва, 1998).

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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

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

7. В основе принципа работы подавляющего большинства алгоритмов трассировки ППЛ лежит процедура построения лишь элементарных соединений (между двумя точками). Поэтому для автоматической реализации требуется предварительно задавать очередность прокладки соединений внутри самой цепи. В основе подхода, обеспечивающего задание очередности лежат в основном эвристические соображения. В этой связи разработан метод пространственной прокладки печатных проводников на ППЛ без ограничения количества слоев, гарантирующий построение в 3—мерном пространстве трассы, если только она существует. Метод обеспечивает одновременную трассировку всей электрической цепи, что позволило отказаться от предварительной разбивки цепи на упорядоченные пары и от выбора последовательности трассировки этих пар.

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

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

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

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

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

13. Проведены эксперименты по трассировке двуслойных печатных плат, подтверждающие работоспособность и возможности предлагаемого подхода к пространственной трассировке проводников. Установлено, что временны’е затраты на трассировку экспериментальных плат оказались существенно ниже по сравнению с временны’ми затратами на трассировку этих же плат при помощи пакета Р-САБ 4.5 в условиях производства!