Методы и алгоритмы пространственной трассировки печатных плат тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Горбачев, Андрей Александрович

• Горбачев, Андрей Александрович
• кандидат технических наук
• 1999

Оглавление диссертации кандидат технических наук Горбачев, Андрей Александрович

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

ПРИЛОЖЕНИЕ 1

ПРИЛОЖЕНИЕ 2

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы пространственной трассировки печатных плат»

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

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

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

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

задачи трассировки ППЛ детализированы пути и цели дальнейшего исследования.

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

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

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

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

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

На защиту выносятся следующие вопросы:

1. Метод пространственной трассировки ППЛ.

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

3. Математические модели ППЛ, ориентированные на применение методов пространственной и совместной трассировки.

4. Структура и основные характеристики экспериментального интерактивного программного комплекса.

В заключении хочу высказать слова благодарности доценту кафедры математической кибернетики Калининградского Государственного Университета, к.т.н. Алешникову С.И. за множество научных и методических советов, данных мне в период подготовки диссертационной работы, а также выражаю свою признательность доценту кафедры технологии судостроения и судоремонта Калининградского Государственного Технического Университета, к.т.н. Морозову В.Н. за оказанную помощь при решении ряда организационных вопросов.

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

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

Всякий процесс создания сложных систем, в том числе и РЭА, представляет собой последовательность определенных этапов. При разработке изделий РЭА традиционным является метод нисходящего проектирования [9, 33, 38, 43, 50]. Если при этом исключить стадию производства элементной базы (как правило, интегральные схемы, транзисторы, диоды и др. создаются независимо от того или иного радиоэлектронного комплекса), то процесс конструирования будет иметь вид, представленный на рис. 1.1.

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

Первой задачей на этом пути является задача компоновки. Она имеет два основных аспекта:

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

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

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

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

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

Рис. 1.1 Схема нисходящего процесса разработки РЭА.

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

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

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

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

При раздельном решении этих задач большой трудностью является выбор критерия оптимизации для задачи размещения, который бы в достаточной мере удовлетворил требованиям трассировки. Основными критериями при размещении элементов являются [53]:

- Минимальная суммарная длина связей;

- Минимальная длина самой длинной связи;

- Минимальные числа возможных пересечений;

- Минимальные числа изгибов соединений.

Все эти критерии косвенно способствуют решению основной задачи: максимизировать число печатных соединений при последующей трассировке.

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

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

рические точки. А для измерения длин вводится соответствующая система координат.

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

Таким образом, конечная задача - трассировка соединений ППЛ является одной из наиболее трудных задач в общей проблематике автоматизации разработки РЭА и при ее решении необходимо учитывать следующие характерные свойства [1, 9, 38, 49]:

- Большая размерность;

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

- Недопустимость пересечения трасс, принадлежащих разным электрическим цепям;

- Связь топологических ограничений со схемотехническими и теплофи-зическими ограничениями.

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

Согласно [53] алгоритмические методы трассировки печатных соединений в зависимости от конструкции коммутационного поля делятся на две основные группы: топографические и графо-теоретические (рис. 1.2).

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

На первом этапе формируется список цепей, определяющий группы эквипотенциальных выводов. Здесь главной задачей является предварительное определение порядка соединений выводов внутри отдельных цепей. Такое упорядочение осуществляется с помощью алгоритмов построения минимальных деревьев [24, 29, 45, 96, 100].

На втором и третьем этапах решаются вопросы, на каком из слоев будет осуществляться трассировка соединений и в каком порядке. Большинство известных методов расслоения соединений [ 3, 11, 28, 39, 52, 63, 79, 105, 106] основано на анализе взаимного расположения всей совокупности соединений на одной плоскости с целью распределения конфликтующих между собой соединений по отдельным слоям. Поскольку подавляющее большинство алгоритмов трассировки принадлежит к алгоритмам последовательного типа, то порядок прокладки соединений определяется заранее.

Графо-теоретические методы трассировки предполагают предварительный анализ планарности схемы, представленной в виде графовой модели, и последующую ликвидацию пересечений с помощью технологических приемов. Окончательная фаза состоит в получении эскиза топологии схемы при оптимальном распределении функций между конструктором и ЭВМ [48].

В настоящее время достигнуты относительно скромные успехи в практической реализации графо-теоретического подхода к конструированию топологии печатных плат и интегральных схем. Отдельные результаты таких работ освещены в [7, 66, 76, 82, 104, 107]. Главным образом развитие алгоритмических методов этой группы идет в направлении синтеза однослойных соединений. Это прежде всего связано со сложностью учета различных метрических ограничений на расположение элементов и соединений. И кроме того, для корректного проведения топологического анализа необходимо при-

Рис.1.2 Классификация методов трассировки

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

В этой группе методов центральное место отводится алгоритмам определения планарности графов. С точки зрения удобства реализации на ЭВМ выделяются следующие: алгоритм Бадера-Фишера [75, 84], алгоритм Дана и Чена [83], а также алгоритмы [78, 81, 98]. Попытки применить графо-теоретические методы к проектированию многослойных схем нашли наиболее яркое отражение в работе [74]. Здесь представлена модель, позволяющая в принципе расположить схему соединений любой сложности в двух слоях с переходами между ними, при условии, что метрические параметры коммутационного поля не влияют на возможность такой раскладки. Но если меж-слойные переходы могут быть выполнены лишь по КП устанавливаемых элементов, то возникает задача расположения соединений в минимальном числе слоев. В топологическом плане она сводится к нахождению минимального планарного разбиения графа схемы [54] (задача покрытия). Однако ввиду указанных выше сложностей для практического использования наиболее приемлемыми оказались эвристические последовательные процедуры выделения планарных подграфов из исходного графа [46].

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

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

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

Стандартная задача построения минимального связывающего дерева формулируется следующим образом:

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

ф) = 5ВД(и) ,

где К; - коэффициенты; ^(и) - характеристики (в том числе и длина) соединений.

Найти в графе в дерево, включающее все вершины X и имеющее минимальный суммарный вес ребер.

Решение этой задачи дано в работах Краскала [96], Добермана и Уэйн-бергера [100] и Прима [45]. Наиболее эффективным с точки зрения реализации на ЭВМ является алгоритм Прима. Он предполагает последовательное выполнение следующих принципов:

- всякая изолированная вершина соединяется с ближайшей;

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

Минимальное дерево, построенное по алгоритму Прима обладает тем свойством, что степень любой вершины не превышает 6. При разработке монтажных схем, как правило, вводится технологическое ограничение на максимальное число соединений X, подходящих к одному выводу. Если А>6, то используются специальные алгоритмы построения минимальных связывающих деревьев. В работах [24, 29] показано, что построение минимального дерева с ограничением на степени вершин возможно с использованием процедур, основанных на методе ветвей и границ. На практике, однако, предпочтение отдается эвристическим алгоритмам. В некоторых случаях, помимо ограничения на степени вершин связывающего дерева, задаются начальная и

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

Особое место в проектировании печатного монтажа занимает построение связывающих деревьев Штейнера. Такие деревья в отличие от минимальных связывающих содержат некоторое множество вершин, отличных от исходного множества выводов. Задача Штейнера состоит в следующем:

Пусть Р = {Рь Р2, ... Рп} - множество точек плоскости. Требуется найти дерево Т = (X, и) с множеством вершин X и множеством ребер Ц, для которого Р с X и суммарная длина ребер и минимальна.

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

Проведенные в работах [89, 94, 102] исследования показали, что методы решения задачи Штейнера существенно зависят от метрики. При машинной трассировке печатных соединений чаще всего используется ортогональная опорная сетка. В работе Ханана [94] дан алгоритм построения минимального дерева Штейнера при п < 5 и описаны свойства таких деревьев для произвольного п. Точные методы решения задачи Штейнера также предложены Шейном [80] и Штейном [67]. Методы используют аппарат булевой алгебры. Однако в этих работах сделан вывод о том, что прямое применение метода булевых функций для построения деревьев Штейнера становится практически невозможным даже при относительно небольших п. В связи с этим необходимо уменьшить размерность задачи перед применением указанных методов.

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

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

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

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

Но в большинстве случаев расслоение выполняется после размещения элементов и более простой путь состоит в учете "взаимодействия" отдельных соединений или связывающих деревьев при условии их одновременного расположения на одной плоскости. При этом учитываются метрические параметры соединений, так как положение КП на коммутационном поле уже известно. Наиболее распространенным приемом является выделение некоторых приоритетных направлений, группирование соединений в соответствии с выбранными направлениями и разнесение этих групп на отдельные слои. Различные способы оценки "взаимодействия" соединений приводятся в работах [39, 52, 93].

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

Фундаментальные теоретические основы указанного подхода заложены работами Кодреса [95] и Вайссмана [105, 106].

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

Аналогичная задача состоит в ликвидации минимального числа проводников для получения двухслойного разложения [11, 63] .

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

Обобщение задачи расслоения для неограниченного числа слоев выполнено Вайссманом [105, 106]. Для исходной системы комплексов КП {VI} (электрических цепей) на плоскости задается семейство Т различных реализаций связывающих деревьев, причем для отдельного комплекса может быть задано несколько вариантов связывающего дерева {Т/}, j = 1, 2, ... к(1) . В простейшем случае для каждой пары соединяемых выводов задается один путь.

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

В работах [3, 79] дано обобщение метода Вайссмана для случая задания различных вариантов построения связывающих деревьев. В работе [3] помимо решения основной задачи расслоения, дан способ выбора кратчайших связывающих деревьев.

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

В ряде работ при ортогональной трассировке соединений предлагается тривиальное распределение проводников на два слоя, когда все горизонтальные отрезки помещаются в одном слое, а вертикальные - в другом. В точках изгибов соединений размещаются контактные переходы. Однако в этом случае возникает избыточное число переходов. Приближенный способ их минимизации приводится в работе [14]. Алгоритм дает сокращение числа переходов до 60 % по сравнению с чисто ортогональным расслоением.

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

терес также представляют алгоритмы Хейса [81] и Джейера [88], в которых процессы трассировки и расслоения совмещены.

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

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

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

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

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

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

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

3}

а)

4

б)

4

Зь

в)

2

1-

3

41

г)

Рис. 1.3 Различные порядки трассировки.

о

Вопрос об эффективности различных методов упорядочения остается дискуссионным. В работе [69] дана статистическая обработка результатов трассировки для двуслойной печатной платы, выполненной при использовании различных тактик упорядочения, основанных на длине соединений. В ка-

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

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

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

ь О.............

О...................................................

с о

л

с а ъ ...............а

ао_

2 Ь

а

а

а

-о

а)

б)

в)

Рис. 1.4 Метод прямоугольника.

с

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

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

1 = Ш ,

где Ь - полупериметр минимального прямоугольника, содержащего выводы цепи; п - количество выводов. Приоритет отдается цепям с меньшей

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Горбачев, Андрей Александрович

ЗАКЛЮЧЕНИЕ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Горбачев, Андрей Александрович, 1999 год

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

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

2. Абрайтис Л.Б. Лучевой алгоритм для проведения печатных соединений // Вопросы радиоэлектроники. Сер. VII.- Электронная вычислительная техника. -1968,-Вып. З.-С. 35 -46.

3. Абрайтис Л.Б. Определение конфигураций соединительных деревьев комплексов с распределением коммутаций по слоям // Вычислительная техника.-Каунас: Каунас, политехи, ин-т, 1971,- Т.П.- С. 162 - 169.

4. Абрайтис Л.Б. Система автоматизированного монтажно-коммутационного проектирования ячеек цифровых устройств // Вычислительная техника.- Каунас: Каунас, политехи, ин-т, 1972,- Т. III.- С. 230 - 233.

5. Айзерман М.А. Нечеткие множества, нечеткие доказательства и некоторые нерешенные задачи теории автоматического регулирования // Автоматика и телемеханика,- 1976,-№7,-С. 171-177.

6. Андреев Г.Ю., Петухов Г.А., Скородубский В.Н. Компенсирующий алгоритм поиска малоповоротных путей // Вычислительная техника. - Каунас: Каунас, политехи, ин-т, 1972,- T.III.- С. 380 - 386.

7. Алгоритм взаимного размещения компонентов полупроводниковых интегральных схем с минимальным числом внутрисхемных соединений / Б.В. Баталов, Г.Г. Казеннов, Ф.А. Курмаев и др. // Микроэлектроника,- М.: Сов. Радио, 1965,- Вып.З,- С. 7 - 18.

8. Апреснян Ю.Д. Лексическая семантика,- М.: Наука, 1974,- 367 с.

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

10. Беллман Р., Заде Л.А. Вопросы анализа и процедуры принятия решений: Пер. с англ.- М.: Мир, 1976.-215 с.

11. Беляков А.Н., Бугаев Е.К., Розанов В.А. Метод распределения проводников в многослойных печатных платах // Труды МИЭМ,- 1971,- Вып. 16, Ч.1.-

С. 148 - 165.

12. Гольдина JI.JL, Ландау И.Я. Алгоритм ортогональной трассировки печатных проводников // Вычислительная техника,- Каунас: Каунас, политехи, ин-т,

1972,- T.III.- С. 394 - 397.

13. Гурвич Е.И., Крапчин А.И. Быстродействующий алгоритм трассировки двуслойных печатных плат // Вычислительная техника,- Каунас: Каунас, политехи. ин-т, 1973,- T.IV.- С. 132 - 136.

14. Гуревич Д.З., Селютин В.А. Алгоритмические методы проектирования топологии БИС ячеечного типа // Методы расчета и автоматизации проектирования устройств микроэлектронных ЦВМ,- Киев: ИК АН УССР, 1973,- С. 83 - 92.

15. Дамбит Я.Я. Метод построения плоского графа // Латвийский математический ежегодник.- 1969,- № 6,- С. 41 - 63.

16. Зайцев Н.Г. Принципы информационного обеспечения в системах переработки информации и упавления,- Киев: Наукова думка, 1976,- 181 с.

17. Зиман Ю.Л. Рябов Г.Г. Волновой алгоритм и электрические соединения

// Электронные вычислительные машины,- М.: ИТМ и ВТ АН СССР, 1965,-С. 27-42.

18. Зыков A.A. Основы теории графов,- М.: Наука, 1987,- 380 с.

19. Интеллектуальные системы автоматизированного проектирования больших и сверхбольших интегральных микросхем / В.А. Мищенко, Л.М. Городецкий, Л.И. Гурский и др.; Под ред. В.А. Мищенко.- М.: Радио и связь, 1988,272 с.

20. Каплан A.B. Алгоритм уменьшения числа межслойных переходов в печатных платах // Вычислительная техника,- Каунас: Каунас, политехи, ин-т,

1973,-T.IV.- С. 126-131.

21. Каплан A.B. К вопросу уменьшения числа межслойных точек перехода в пе-

чатных платах // Вычислительная техника.- Каунас: Каунас, политехи, ин-т, 1973,-T.IV. С. 122 - 125.

22. Курейчик В.М., Лебедев В.К. Алгоритм уменьшения числа каналов при трассировке соединений // Методы расчета и автоматизации проектирования устройств микроэлектронных ЦВМ,- Киев: ИК АН УССР, 1974,- С. 52 - 63.

23. Лазарева Т.С. Алгоритм трассировки печатных соединений на основе представления о каналах // Автоматика и вычислительная техника,- 1969,- №5,-С. 12-15.

24. Линский B.C. Построение кратчайших деревьев с ограничениями на степени вершин // Электронная техника. Сер. VI.- Микроэлектроника,- 1971 .Вып. 4,- С. 90 - 92.

25. Липский В. Комбинаторика для программистов / Пер. с польск.- М.: Мир, 1988.-213 с.

26. Малышева И.И., Розанов В.А., Юрин О.Н. Автоматизация технического проектирования многослойных печатных плат // Вопросы радиоэлектроники. Сер. VII.- Электронная вычислительная техника,- 1972,- Вып. 3,-

С. 115 - 118.

27. Мамиконов А.Г., Пискунов А.Н., Цвиркун А.Д. Модели и методы проектирования информационного обеспечения АСУ,- М.: Статистика, 1978,- 221 с.

28. Мартин Дж. Организация баз данных в вычислительных системах,- М.: Мир, 1980,- 162 с.

29. Матицкас К.Л. Алгоритм определения дерева оптимальной длины с ограничением степени его вершин // Вычислительная техника,- Каунас: Каунас, политехи, ин-т, 1971,- Т.П.- С. 121 - 131.

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

31. Нагао М., Катаяна Т., Уэмура С. Структуры и базы данных: Пер. с япон,-М.: Мир, 1986,- 197 с.

32. Ногис Р.В., Юркунас Д.Ю. Алгоритм трассировки печатных соединений с

малым числом поворотов // Вычислительная техника,- Каунас: Каунас, политехи. ин-т, 1970,- T.I.- С. 326 - 331.

33. Норенков И. П., Маничев В. Б. Системы автоматизированного проектирования электронной и вычислительной аппаратуры: Учеб. пособие для вузов.-М.: Высш. школа, 1983,- 272 с.

34. Об одном подходе к автоматизации проектирования печатных плат / А.В. Петросян, Ю.Г. Шукурен, С.Е. Макросян, СЛ. Амбарян // Кибернетика,-1974,-№ 1.-С. 50 - 57.

35. Орловский Г.В., Покровский А.М. Алгоритм трассировки печатных плат // Обмен опытом в радиопромышленности,- 1971.- № 7,- С. 11 - 15.

36. Особенности использования аналогового рабочего поля для машинной трассировки межсоединений / Р.П. Базилевич, И.В. Парканий, Н.Ф. Стороженко, 0.3. Ясеницкий // Вычислительная техника.- Каунас: Каунас, политехи, ин-т, 1974,- Т.VII,- С. 103 - 106.

37. Перспективы развития вычислительной техники. В 2-х кн.: Справ, пособие

/ Е.С. Кузин, А.И. Ройтман, И.Б. Фоминых и др.; Под ред. Ю.М. Смирнова,-М.: Высшая школа, 1989,- Кн. 2- Интеллектуализация ЭВМ,- 159 с.

38. Петухов Г.А. и др. Алгоритмические методы конструкторского проектирования узлов с печатным монтажом / Г.А. Петухов, Г.Г. Смолич, Б.И. Юлин,-М.: Радио и связь, 1987,- 152 с.

39. Помазанов В.Н., Крыжановский Ю.М., Клименкова Т.И. Алгоритм и программы комплекса трассировки // Обмен опытом в радиопромышленности.-1971,- Вып.7,- С. 29-31.

40. Попов Э.В., Фридман Г.Р. Алгоритмические основы интеллектуальных роботов и искусственного интеллекта,- М.: Наука, 1976,- 455 с.

41. Попов Э.В. Экспертные системы: Решение неформализуемых задач в диалоге с ЭВМ,- M.: Наука, 1987,- 288 с.

42. Поспелов Д.А. Ситуационное управление: теория и практика,- М.: Наука, 1986.-288 с.

- 14843. Построение современных систем автоматизированного проектирования / К.Д. Жук, A.A. Тимченко, A.A. Родионов и др.- Киев: Наукова думка, 1983.-248 с.

44. Построение экспертных систем / Под ред. Хейеса-Рота, Д. Уотермана, Д. Ле-ната,- М.: Мир, 1987.-414 с.

45. Прим Р.К. Кратчайшие связывающие сети и некоторые обобщения // Кибернетический сборник (М.).-1961,- № 2,- С. 95 - 107.

46. Разбиение графа на плоские суграфы / А.Н. Мелихов и др. // Изв. АН СССР. Техническая кибернетика,- 1972. - № 6,- С. 166 - 170.

47. Разработка, эксплуатация и развитие систем автоматизированного проектирования РЭА,- М.: МДНТП, 1978,- 158 с.

48. Реализация теоретико-графового подхода к автоматизированному синтезу топологии интегральных микросхем / В.А. Селютин, Н.П. Львов, A.A. Пер-шурич, Т.В. Сердюк//Вычислительная техника. - Каунас: Каунас, политехи, ин-т, 1976,-T.VIII.-С. 22-25.

49. Реальность и прогнозы искусственного интеллекта: Сб. статей: Пер. с англ.; / Под ред. В.Л. Стефанюка.- М.: Мир, 1987,- 247 с.

50. Рябов Г.Г., Бликова Л.А. Динамический подход к задаче трассировки // Вычислительная техника,- Каунас: Каунас, политехи, ин-т, 1972,- Т.III,-

С. 403 - 407.

51. САПР систем логического управления / В.А. Горбатов, A.B. Крылов, Н.В. Федоров; Под ред. В.А. Горбатова,- М.: Энергоатомиздат , 1988,- 232 с.

52. Селютин В.А., Гуревич Д.З. Реализация на ЦВМ системы алгоритмов топологического проектирования // Электронная техника. Сер. VI,- Микроэлектроника." 1971,- Вып.6.- С. 145 - 152.

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

54. Селютин В.А. Топологические модели для задач проектирования коммутационных схем // Электронная техника. Сер. VI,- Микроэлектроника,- 1969,-

Вып.6,- С. 66 - 72.

55. Тверицкий Р.В. Алгоритм поиска кратчайшего пути и его применение для формирования цепей // Вопросы радиоэлектроники. Сер. VI1.- Электронная вычислительная техника,- 1970,- Вып.9,- С. 126 - 131.

56. Тюренков В.А. Алгоритм нахождения кратчайшего пути // Вычислительные системы,- Новосибирск: ИМ СО АН СССР, 1963,- Вып.6,- С. 41 - 44.

57. Учебно-исследовательская система автоматизированного проектирования радиоэлектронноых схем: Учеб. пособие / В.И. Анисимов, Г.Д. Дмитриевич, Н.К. Перков и др.; Под ред. В.И. Анисимова,- Л.: Изд-во Ленингр. ун-та, 1989.- 256 с.

58. Фиск, Кэски, Уэст. Автоматическое проектирование печатных плат // ТИИЭР,- 1967,- Т.55, № 11,- С. 217 - 228.

59. Фиск, Кэски, Уэст. Проектирование печатной платы // Электроника.- 1967.-№ 19,- С. 5- 16.

60. Четвериков В.Н. и др. Базы и банки данных: Учеб. для вузов по спец."АСУ" / В.Н. Четвериков, Г.И. Ревунков, Э.Н. Самохвалов; Под ред. В.Н. Четверикова,- М.: Высш. шк., 1987,- 248 с.

61. Чечкин А.В. Математическая информатика,- М.: Наука, 1991. - 416 с.

62. Чигварин Н.В. Экспертные компоненты САПР,- М.: Машиностроение, 1991.-240 с.

63. Шеуйкис В.А. Исследование алгоритмов для распределения связей по двум слоям платы // Вычислительная техника.- Каунас: Каунас, политехи, ин-т, 1971,-Т.Н.-С.170 - 174.

64. Широ Г.Э., Лапидус Л.И. Метод трассировки печатных соединений // Применение вычислительных машин для проектирования цифровых устройств.-М.: Сов. радио, 1968,- С. 199 - 215.

65. Широ Г.Э. Метод проектирования печатного монтажа, основанный на эвристических принципах // Методы разработки схем и конструкций цифровых систем,- Л.: ЛДНТП, 1967,- С. 132 - 148.

66. Широ Г.Э., Осипов Л.Б. Размещение компонентов интегральных схем

// Применение вычислительных машин для проектирования цифровых устройств,- М.: Сов. радио, 1968,- С. 216 - 228.

67. Штейн М.Е. Об ортогональных графиках и оптимальных соединениях схем // Известия АН СССР. Техническая кибернетика,- 1970,- № 2,-

С. 119-127.

68. Экспертные системы. Принципы работы и примеры: Пер. с англ.; А. Бру-кинг, П. Джонс, Ф. Кокс и др./ Под ред. Р. Форсайта.- М.: Радио и связь, 1987,-224 с.

69. Abel C.L. On the ordering of connection for automatic wire routing // IEEE Trans.- 1972,- V. C-21, № 11,- P. 1227 - 1233.

70. Aird Т., Milnes H.W. A program for automating circuit layout // The Journal of the Industrial Mathematics Society.- 1964,- V.14, pt.2.- P. 1 - 8.

71. Akers S.B. A modification of Lees path connection algorithm // IEEE Trans.-1967,- V. EC-16, № 1.- P. 97 - 98.

72. Alia G., Frosini G., Maestrini P. Automated module placement and wire routing according to a structured biplanar scheme in printed boards // Computer aided design.- 1973,- V.5, № 3,- P. 152 - 159.

73. Aramaki J., Kawabata Т., Arimoto K. Automation of etching pattern layout //Comm. ACM.- 1971,-V.14, № Ц.. p. 720-730.

74. Auslander L., Trent H.M. On the topology of printed circuits. // IEEE Trans, on— Circuit Theory.- 1959,- XII.- P. 390 - 391.

75. Bader W. Das topologische problem der ger gedruckten Schaltung und seine Losung // Arhiv fur Elektrotechnik.- 1964,- №1, Bd. 49,- S. 2 - 12.

76. Basden A., Nikols K. G. New topological method to laying out printed circuits // Proc. IEEE.- 1973,- V.120, №> 3,- P. 325 - 328.

77. Bellman R.E. On a routing problem. Quart. Appl. Math.- 1958,- 16,- S. 87 - 90.

78. Bruno J., Steiglitz K., Weinberg L. A new planarity test based on 3-connectivity // IEEE Trans.- 1970,- V.CT-17, №2,- P. 197 - 206.

79

80

81

82

83

84

85

86

87

88

89

90

91.

92.

93.

Chein M. Decomposition d'un schema en un nombre minimal de schémas planaires // L'onde electrique.- 1970,- V.50, £11.- P. 934 - 939. Chein M. An algorithm pour relies N points // Calcobo.- 1968,- V.5, № 4,-P. 537- 547.

Chung S.H., Roe R.H. Algoritms for testing the planarity of a graph // Proc. of the 13th Medwest symposium on Circuit Theory.- New York, 1970, P. 321 - 332. Dierick P., Lavie R., Martin J.L. Trace' automatique de masques de circuits in-te'gre's hybrides // L'onde electrique.- 1969,- Y.49, №1,- P. 98 - 103. Dunn W. N., Chan S. P. An algorithm for testing the planarity of a graph // IEEE Trans.- 1968,- V.CT-15, №2,- P 9 - 13.

Ficher G. J., Wing O. Computer recognition and extraction of planar graphs from incidence matrix // IEEE Trans..- 1966,- V.CT-13, №2,- P. 154 - 163. Ford L.R. Network flow theory. The Rand Crp.- New York.- August 1956, P. 923 Freitag H. Design automation for large scale integration / Wescon Technical Papers.- Los Angeles, Calif., 1966.

Galy P., Ghendrich P., Guillame G., Ombredan E., Wolf A. Trace' automatique des circuits imprime's // L'onde electrique.- 1969,- V.49, № 1.- P. 113 - 119. Geyer J. M. Connection routing algorithm for printed circuit boards // IEEE Trans.- 1971,- V.CT-18.-P. 95 - 100.

Gilbert E. N, Pollak H. O. Sterner minimal trees // SIAM J. Appl. Math.- 1968 -V.16, № l.-P. 1-29.

Glem R.R., Lathrop J.W. Two approaches to the computer routing of interconnections // Proc. 20th Electr. Comp. Conf. 1970,- № 4,- P. 390 - 411. Gresse M. A.. Une me'thode de trace' en technologie "blocs denses" // Colloque international sur la microe'lectronique avance'e.- Paris, 1970.- P. 393 - 401. Heiss S. A path connection algorithm for multilayer boards // Proc. of the 8th Annual 1969, IEEE Region 111 Connection.- Chicago, 1969,- P. 86 - 96. Hightower D. W. The interconnection problem: a tutorial // Computer.-1974.-V.7, № 4,- P. 18-32.

- 15294. Homan M. On Steiner problem with rectilinear distance // SIAM J. Appl. Math.-1966.-V.14, №2.-P. 255 -265.

95. Kodres U. R. Formulation and solution of circuit card design problems through use of a graph methods // Advances in Electronic Circuit Packaging.- 1962,- V.2, №7,- P. 121 - 142.

96. Kruskal J.B.Jr. On the shortest spanning subtree of a graph and the travelling salesman problem // Proc. Amer. Math. Soc.- 1956,- № 7,- P. 48 - 50.

97. Lee C. Y. An algorithm for path connections and its applications // IRE Trans.-1961,- V.EC-10, № 3,- P. 346 - 366.

98. Lempel A., Even A., Cederbaum I. An algorithm for planarity testing of graphs // Theory of Graphs, International Symposium . Rome, Ed. P. Rosenstiehl, Pub. Gordon and Breach.- 1966,- P. 215 - 232.

99. Litaize D. Trace' automatique de plaquettes de circuits imprime's // Automatisme.-1973,-V.XVIII,№1.-P. 7- 15.

100. Loberman H., Weinberger A. Formal procedures for connecting terminals With a minimum total wire length // J. ACM.- 1959,- V.4, № 4,- P. 428 - 437.

101. Mah L., Steinberg L. Topological class routing for printed circuit boards // Proc. ACM - IEEE Design-automation workshop.- Los Angeles, 1972,- P. 80 - 93.

102. Melzak Z. A. On problem of Steiner // The Journal of Industrial Engineering.-1961,- V.X1V, № l.-P. 143 - 148.

103. Mikami K., Tabuchi K. A computer program for optimal routing of printed circuit conductor // IFIP Congress 68,- Edinburg, 1968,- P. 76 - 79.

104. Sugiyama N., Nemoto S., Kani K., Ohtsuki T., Watanabe H. An integrated circuit layout design program based on a graphheoretical approach // IEEE Internat. Solid State Circuit Conference.- Tokyo, 1970,- P. 86 - 87.

105. Weissman J. Boolen algebra, map coloring, and interconnections // The Mathematical Monthly.- 1962,- V.69, № 7,- P. 608 - 613.

106. Weissman J. The mathematical basis of the Automatics Etched Interconnection Design Program // IRE International Convention Record.- Rome, 1962,- Part 6,-

P. 26-133.

107. Zibert K., Saal R. On computer aided hybrid circuit layouts // Proc. IEEE. Int. Symp. Circ. And Sust.- London, 1974,- P. 314 - 318.