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

5 ОД 7 0Н1 1993

На правах рукописи УДК 621.3.049.75: 004.3

КОКОТОВ ВАЛЕРИЙ ЗЯМОВИЧ

САПР РЕЛЬЕФНОГО МОНТАЖА

05.13.12 - системы автоматизации проектирования

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Москва - 1998

Работа выполнена в Научно - исследовательском институте АРГОН

Официальные оппоненты:

доктор технических наук, профессор, член-корреспондент РАН Рябов Геннадий Георгиевич;

доктор технических наук, профессор, действительный член РАЕН Норенков Игорь Петрович;

доктор технических наук, профессор Назаров Александр Викторович.

Ведущая организация - ОАО ЦКБ АЛМАЗ, г. Москва.

Защита состоится " "_1998г. в_час._мин. на

заседании диссертационного совета Д.053.18.01 в Московском государственном авиационном институте (Техническом университете).

Отзывы на автореферат в 2-х экземплярах, заверенные печатью, просьбе высылать по адресу: 125871, Москва, ГСП, Волоколамское шоссе, 4, Ученый совет, Ученому секретарю диссертационного совета Д.053.18.01.

С диссертацией можно ознакомиться в библиотеке МАИ.

Автореферат разослан " "_1998г.

Ученый секретарь диссертационного совета, ^ кандидат технических наук, доцент /'/ грс.^ Федотов Л. М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

Обоснование достоверности полученных результатов. Обоснованием эффективности заимствования составляющих разработки САПР РМ являетсяо-пыт "быстрой" разработки и эффективной эксплуатации САПР ИЕЬЕР, описанной в главе 4 диссертационной работы. Обоснованием эффективности разработанных алгоритмов сложных ФК проводится теоретическими методами в главе 3 и подтверждается экспериментами, описанными в главе 5.

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

- для создания новых САПР "стабильных по правилам проектирования" объектов проектирования предложена концепция заимствования составляющих разработки САПР;

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

- предложена классификация ФК САПР, отражающая сложность и приоритет при разработке;

- сформулированы принципы разработки САПР РМ, позволяющие начать опытную эксплуатацию на стадии проектирования, а также обеспечивающие удобство эксплуатации, сопровождения и модернизации;

- разработан новый алгоритм итеративного улучшения расстановки равно-габаритных ЭРЭ;

- разработан способ деконцентрации групп сильно связанных ЭРЭ, повышающий эффективность "силовых" алгоритмов размещения;

- разработан новый алгоритм плотного размещения разногабаритных ЭРЭ;

- разработаны эвристические способы повышения быстродействия и трассировочных способностей алгоритма малоповоротных путей;

- разработана модификация алгоритма рекапитуляции цепей (доводка не-проведенных связей);

- разработан быстродействующий алгоритм анализа статических и динамических режимов цепей питания;

- предложены способ настройки на формат управляющих программ и два новых эвристических способа оптимизации траектории инструмента для постпроцессоров технологического оборудования;

- разработан алгоритм контроля проектных норм РМ;

- впервые разработан алгоритм внутренней сортировки менее чем линейной сложности.

Практическая значимость работы. Сформулированные в первой главе диссертационной работы принципы разработки САПР РМ использовались при создании Комплекса прикладных программ автоматизации проектирования рельефных печатных плат (КППАП РПП) и САПР RELEF.

При разработке САПР RELEF использовались все теоретические и алгоритмические аспекты, рассмотренные в первой и третьей главах диссертационной работы. Часть этих аспектов использовалась для создания КППАП РПП. КППАП РПП применялся в НИЦЭВТ для проектирования РП СЦВМ, а трассировщик КППАП РПП использовался для проектирования МаБИС ЭВМ ЕС 1067. КППАП РПП внедрялся на ряде предприятий для проектирования РП. САПР RELEF используется в НИИ АРГОН для проектирования РП БЦВК. САПР RELEF начиная с 1996 года используется в учебном процессе в Московском государственном авиационном институте (Техническом университете).

Перечисленные использования и внедрения КППАП РПП и САПР RELEF подтверждены актами внедрения.

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

Структура диссертации. Диссертация состоит из введения, пяти глав и заключения, списка литературы и 9 приложений. Работа содержит 230 страниц текста, выполненных в редакторе WORD 6, 62 иллюстрации, 43 таблицы, список литературы из 89 наименований, 34 страницы приложений.

СОДЕРЖАНИЕ РАБОТЫ

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

САГТР РМ вызывается не совершенствованием технологических процессов, а переходом на новые аппаратные платформы или принципиально новые операционные системы.

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

В первой главе рассматриваются проблемы создания и общие концепции построения САПР РМ.

Описывается специфика разработки САПР РМ, позволяющая заимствовать существенную часть составляющих разработки от уже созданных САПР РМ. Обосновывается перечень заимствуемых составляющих разработки, в который входят специальные требования к САПР РМ, принципы разработки САПР РМ, математическое обеспечение, лингвистическое обеспечение, определяемое конструкцией РМ, методическое обеспечение разработки процедур проектирования и критерии оценки качества САПР РМ. Формулируется проблема, решаемая в диссертационной работе, как создание таких заимствуемых (типовых) составляющих разработки для новых создаваемых САПР РМ. Указывается, что прототипом части незаимствуемых (нетиповых) составляющих разработки САПР РМ могут являться такие составляющие описанной в главе 4 САПР ЯЕЬЕР.

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

Для оценки ФК, влияющих на трассировочные способности всей САПР, предлагается использовать показатель Т - процент непроведенных связей сигнальных цепей

т = £^(о/о)) (1)

N-0

где: п - число непроведенных связей;

N - общее число монтажных точек всех сигнальных цепей таблицы цепей;

С - общее число сигнальных цепей в таблице цепей.

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

Вводятся понятия основные и неосновные ФК, а также проблематичные (первого или второго типа) и непроблематичные ФК. Предлагается классификация всех ФК САПР, при которой каждый ФК имеет свойство быть основным или неосновным и проблематичным (первого или второго типа) или непроблематичным.

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

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

Принцип основных проблематичных ФК предусматривает разработку САПР в три стадии.

На первой стадии проектируются "макеты" всех основных проблематич-

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

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

На третьей стадии создаются неосновные ФК и некоторые общесистемные средства (интегрированная среда, система тестирования, демо-версии и т. д.), а также проводится документирование САПР.

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

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

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

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

Во второй главе описаны конструктивные особенности РМ, как объекта проектирования САПР.

Приведены предпосылки появления в 70-х годах отечественных РП.

Описывается конструкция РП (рис. 1 и 2), представляющая собой диэлектрическое основание 1, в которое углублены медные проводники 2, выполненные в виде металлизированных канавок, и сквозные металлизированные отверстия, имеющие форму двух сходящихся конусов 3. Такие канавки и отверстия заполняются припоем 4. РП имеют два проводящих и один изоляционный слой.

Переходные Монтажное Глухие отверстия отверстие монтажные

с^3 - второй проводящий слой • - переходные металлизированные отверстия

Рис.1. Рис.2.

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

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

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

По статистическим данным сформулирована эквивалентность РП и многослойных печатных плат по трассировочным возможностям (таблица 1).

Таблица 1.

Эквивалент трассировочных возможностей МПП

шт Н (мм) Количество Шаг Конструкция

РП сигнальных слоев трассировки (технология)

0.62 6 + 8 1.25 Сквозная металлизация

0.5 8 1.25 Сквозная металлизация

0.4 8+10 1.25 Сквозная металлизация

0.32 6 0.625 Межслойные переходы

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

статического и динамического режимов.

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

Сформулированы следующие специальные требования к САПР РМ, степень выполнения которых существенно влияет на эффективность таких САПР:

- обеспечение автоматического плотного размещения ЭРЭ;

- обеспечение стопроцентной автоматической трассировки;

- обеспечение "корректной" и не избыточной трассировки цепей питания;

- обеспечение проектирования РП с переменным шагом трассировки;

- обеспечение оптимальных траекторий инструмента технологического оборудования;

- обеспечение бездефектного проектирования автоматическими методами.

В третьей главе рассматриваются теоретические аспекты и алгоритмы

всех проблематичных ФК и одного инструментального компонента.

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

Для расстановки равногабаритных ЭРЭ используется известный алгоритм Р4 Л. Б. Абрайтиса первичного размещения (с небольшой модификацией) и разработанный вариант алгоритма итеративного улучшения. Кроме того разработан и применяется способ деконцентрации групп сильно связанных ЭРЭ.

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

Разработанный вариант алгоритма итеративного улучшения работает по

следугощему принципу. Переназначения установочных мест для ЭРЭ проводятся или в одной строке или в одном столбце таких мест (при матричном расположении установочных мест на поле размещения). Перед переназначением все ЭРЭ "снимаются" с установочных мест для последующего одномерного назначения на "новые" установочные места той же строки или столбца. Критерием выбора очередного назначаемого ЭРЭ является максимум связей с уже назначенными ЭРЭ данной строки (столбца) и со всеми ЭРЭ других строк. Критерием выбора места установки является минимум суммы длин связей данного ЭРЭ со всеми установленными ЭРЭ.

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

Одной итерацией считается последовательное однократное переназначение ЭРЭ во всех строках и всех столбцах установочных мест. Окончание итеративного процесса происходит в случае, когда после очередной итерации не изменилось положение ни одного ЭРЭ. Для реальных РП с большим количеством установочных мест (более 100) число итераций обычно не превышает 50 (при условии проведения первичного размещения).

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

Для размещения разногабаритных ЭРЭ предложен алгоритм, использую-

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

Для каждой исходной области такие операции проводятся как для вертикальной границы, так и для горизонтальной. В окончательном варианте принимается граница, имеющая максимальные значения "а" и "Ь" (рис. 5). Далее для каждой полученной подобласти проводятся аналогичные операции. Область становится неделимой в случае, если содержит всего один ЭРЭ или в случае невозможности плотной упаковки ЭРЭ в подобластях без пересечения этих подобластей (рис. 4). В каждой неделимой области проводится "разрежение" установки ЭРЭ. Такое "разрежение" выполняется бинарным поиском, каждый шаг которого проводится путем плотной упаковки ЭРЭ при искусственно изменяемых габаритах ЭРЭ.

ЭРЭ левой ЭРЭ правой

подобласти а Ь подобласти Граница правой подобласти

Описанный алгоритм "плотного" размещения совмещает в себе два критерия. Первый (доминирующий) - возможность размещения ЭРЭ на РП и ее частях при дихотомическом делении. Второй (вспомогательный) - минимальное число связей на границе подобластей при дихотомическом делении. При использовании данного алгоритма для реальных РП с разногабаритными ЭРЭ наблюдались случаи успешного размещения таких ЭРЭ при суммарной площади их установочных мест до 83% от общей площади поля размещения.

Граница деления Граница исходной исходной области области

Граница левой подобласти

Рис. 3.

Рис. 4.

В данном алгоритме деление ЭРЭ каждой исходной области на две части выполняется итеративным способом. Исходным является "случайное" разбиение на две равные по количеству ЭРЭ части. Каждая итерация заключается в обмене по принадлежности к частям по одному ЭРЭ от каждой части. Выбор ЭРЭ для перенесения в другую часть проводится по модифицированному автором критерию, предложенному Tong Gao, P. M. Vaidya и С. L. Lui.

Для плотной упаковки ЭРЭ решается задача раскроя прямоугольной полуплоскости на прямоугольники (модели корпусов ЭРЭ). Для решения этой задачи предложен эвристический алгоритм, который предусматривает последовательный выбор ЭРЭ для плотного размещения и выбор мест для их установки. Критерии выбора ЭРЭ и выбора места его установки локально максимизируют величины "а" и "Ь" в исходных областях при дихотомическом делении (рис. 5).

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

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

Для данного ФК проводился выбор способа упорядочения сигнальных цепей и упорядочения монтажных точек внутри каждой цепи среди известных способов упорядочения. Отсутствие аналитических методов такого выбора привело к использованию статистического подхода. Экспериментально анализировалось по показателю (1) 16 способов упорядочения для 9 реальных РП, с увеличенными значениями шагов трассировки (для обеспечения Т>0 во всех экспериментах).

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

Трассировщик является основным проблематичным ФК первого типа. По-

скольку данный ФК критичен по машинным ресурсам ко всякого рода изменениям алгоритма, то для него представляется целесообразным в большей степени придерживаться принципа специализации. Это привело к созданию трех трассировщиков в САПР ЯБЬЕР (в КППАП РПП было пять трассировщиков). Однако базовый алгоритм для всех трассировщиков является общим.

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

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

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

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

Третий способ ускорения - переход от матричной модели поля трассировки к списковой структуре. Такой переход существенно сокращает время распространения лучей, но увеличивает время обратного прохода (построение трассы). Однако суммарный эффект от данного способа - это уменьшение общего времени трассировки в 7+10 раз.

Эксперименты по трассировке сложных РП показали недостаточные трас-

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

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

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

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

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

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

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

Шестой способ улучшения - перетрассировка. Этот способ был применен автором по совету Л. Б. Абрайтиса и заключается в следующем. После проведения "обычной" трассировки в случае наличия непроведенных связей проводится последовательное изъятие и трассировка каждой цепи. При этом конфигурация цепей иногда изменяется (за счет различия условий при "обычной" трассировке и перетрассировке). Это приводит к тому , что некоторые цепи, имевшие непроведенные связи, при перетрассировке стопроцентно трассируются. Здесь важным является то, что при перетрассировке принципиально не могут появляться "новые" непроведенные связи.

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

Для базового алгоритма трассировки разработаны также алгоритмы моди-

фикаций, обеспечивающие следующие дополнительные возможности.

Установка переходных отверстий во всех "свободных" монтажных точках -обеспечивает специальные конструктивно-технологические требования.

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

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

Трассировка с заданным зазором - позволяет по возможности не создавать концентрации трасс на РП со средней плотностью монтажа.

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

ФК "Доводка непроведенных связей" является неосновным проблематичным ФК первого типа и использует в качестве подпрограммы трассировщик. Поэтому здесь также в большей степени использовался принцип специализации, что привело к созданию трех доводчиков в САПР ИЕЬЕР (в КППАП РПП применялось два доводчика). Базовый алгоритм всех доводчиков - единый и является модификацией алгоритма Л. П. Рябова. Принцип работы базового алгоритма доводки непроведенных связей заключается в следующем. Определяется нескольких групп "мешающих цепей", не позволяющих стопроцентно трассировать "доводимую цепь". Далее выполняется изъятие "доводимой цепи" и первой такой группы цепей с поля трассировки. После этого проводится трассировка сначала "доводимой цепи", а затем всех изъятых цепей (в различной последовательности). Если все цепи имели стопроцентную трассировку, то подобные действия выполняются для следующей "доводимой цепи". Если же при трассировки изъятых цепей появляются непроведенные связи, то подобная операция выполняется для следующей группы "мешающих цепей". Если для всех групп мешающих цепей не было получено стопроцентной трассировки, то выбирается группа с минимальным общим числом непроведенных связей, и если это число меньше или равно исходному такому числу "доводимой цепи", то фиксируется данный вариант трассировки, а "новые" цепи с непроведенными связями обра-

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

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

Для определения групп "мешающих цепей" описана модель топологии печатного монтажа - порожденный граф цепи (ПГЦ). Рассмотрены способы формирования ПГЦ и нахождения групп "мешающих цепей" с использованием ПГЦ. Описывается алгоритм доводки непроведенных связей. Проводится критический анализ предложенного алгоритма доводки путем сравнения его с алгоритмом Л. П. Рябова. Предлагается три способа повышения эффективности разработанного алгоритма доводки.

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

ФК "Анализ цепей питания" является неосновным проблематичным ФК первого типа. Целесообразность использования данного ФК продиктована особенностями конструкции РП, при которых цепи питания, выполняемые тонкими проводниками, проводятся на тех же слоях, что и сигнальные цепи. При этом

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

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

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

Внутренний узел цепи питания (рис. 5); монтажная точка подключения ЭРЭ при анализе влияния заданной временной диаграммы тока нагрузки на напряжения во всех узлах данной цепи (рис. 6); монтажная точка подключения ЭРЭ при анализе влияния заданной временной диаграммы сопротивления нагрузки на напряжения во всех узлах данной цепи (рис. 7); монтажная точка под-

ключения ЭРЭ, имеющего индуктивную составляющую в нагрузке, при анализе влияния заданной временной диаграммы сопротивления нагрузки на напряжения во всех узлах данной цепи (рис. 8); монтажная точка подключения конденсатора "развязки" (рис. 9); монтажная точка подвода питания при анализе влияния заданной временной диаграммы потенциала питания на напряжения в других узлах данной цепи (рис. 10); монтажная точка подвода питания при анализе влияния активных и реактивных сопротивлений в подводе питания от источника с постоянным напряжением на напряжения во всех узлах цепи (рис. 11).

н

Рис. 5.

Рис. 6.

ьн к« ин

/тЧ=п—о

Рис. 7.

Рис. 8.

Рис. 9.

Ьп яп и„

—1—О

Рис.10. Рис.11.

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

а элементы главной диагонали по модулю - не меньше суммы модулей остальных элементов соответствующих строк.

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

п = тахтах

2х Ли

О

2х Ди

о;

ди,

2 х Ди

- +

О

(2)

2х Ди

о;

ди

о

(3)

(4)

где: I - множество узлов анализируемой цепи;

N - множество моментов времени при исходной дискретности Д1;

Ди0 - допустимая погрешность решений;

Ь = -2.5х и(.р)(1ы,Д1)+ 16х1Кр)(1М,—)-13.5 х и(р)(1к,—);

2 3

с = 3 X и(]р)а1Ч, ДО -12 X ) + 9 X ).

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

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

Описан способ выбора исходной дискретности времени Д1 для расчета ди-

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

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

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

Для ФК "Визуализация и контроль монтажа", являющегося неосновным проблематичным ФК первого типа, описываются функции, выполняемые им.

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

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

Описываются функция контроля проектных норм и предлагается алгоритм контроля зазоров и корректности электрических соединений элементов проводящего рисунка, учитывающий специфику формы таких элементов для РМ. Данный алгоритм состоит из двух частей - "сбора" корректно соединенных элементов проводящего рисунка в цепи (сбор цепей) и проверки условий корректности зазоров и соединений. Обе части данного алгоритма заключаются в проверке выполнения некоторых условий для пар элементов проводящего рисунка. Рассмотрены способы выбора таких пар. При ограниченном объеме оперативной памяти применяется известный способ, заключающийся в хранении в оперативной памяти только фрагмента модели РП и перемещении такого фрагмента по всей модели.

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

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

Описывается способ проверки зазоров и корректности соединений, выполняемый независимо для двух слоев РП.

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

Сортировка является одним из важнейших инструментальных средств для многих ФК САПР РМ. Для повышения эффективности такого средства разработана поразрядная сортировка менее чем линейной сложности. Известный алгоритм внутренней распределительной сортировки - поразрядная сортировка начиная с младшего разряда имеет линейную сложность <3(М), где N - количество элементов массива, подлежащего сортировке. Разработанная модификация (оптимизация) данного алгоритма имеет на конечном интервале 2-кМт значений N сложность, менее чем линейную. Принцип такой оптимизации заключается в следующем. Известно, что время выполнения поразрядной сортировки представимо, как

где а - пропорционально числу разрядов в ключе сортировки; Ь - пропорционально величине 2К (Я - число бит в одном разряде сортировки) и числу разрядов в ключе сортировки;

N - количество элементов в сортируемом массиве.

Если ключ сортировки состоит из В двоичных разрядов, то при увеличении Я значение "а" уменьшается, а значение "Ь" возрастает (рис. 12).

Т(>1) = а х N + Ь,

(5)

а то"

"к, \ ; N

Ы, N2

N3

N4

Рис. 12.

Из данного рисунка видно, что для любой заданной величины N можно найти такое (оптимальное) значение R«,, при котором T(N) минимально. При этом зависимость min T(N) будет кусочно-линейной. Нетрудно видеть, что огибающая зависимости min T(N) до определенного значения Nm имеет зависимость от N менее чем линейную. Здесь величина Nm является минимальным значением N, при котором min T(N) соответствует прямой T(N), образованной при R = В. Понятно, что для N > Nm зависимость min T(N) будет линейной. Все дальнейшее изложение аспектов оптимизации является описанием способов нахождения R0 при заданном значении N и оценки эффективности использования этих способов.

Рассмотрено три способа оптимизации для двоичнократных R0 и четвертый способ - для двоичнонекратных R<,.

Для первого способа оптимизации (точное решение для двоичнократных R0) доказано, что в общем случае Ro может "распадаться" на два значения R и R - 1, которые обеспечивают min T(N) при "разбиении" ключа сортировки на bi R-битовых разрядов и Ъ2 R-1-битовых разрядов. Введено понятие обобщенного количества элементов (К) исходного массива сортировки

К = N х tn/tm, (6)

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

tm - суммарное время выполнения операций "просмотра" одного элемента массива, состоящего из 2R или 2R_1 элементов при одноразрядной сортировке.

Показано, что все значения К (от 2 до а>) разбиваются на интервалы Ki+Ki+J (Ki < Ki+i), внутри которых min Т(К) достигается при одних и тех же значениях R, bi и Ь2. Получены выражения для вычисления значений Kj. Приведена таблица значений Kj, R, bi и b2 для величин ключей сортировки 8, 16, 24, 32, 40, 48, 64, и 80 бит. Описываются способы определения значений tn/tm. Приводится методика определения значений R, bi и Ь2 при заданном значении N. Для оценки эффективности первого способа оптимизации предлагаются количественные оценки и приводятся графики с семействами зависимостей таких оценок от значений К и В.

Для второго способа оптимизации (приближенное решение для двоично-

кратных Ro) получены простые выражения для вычисления Ki(Ro). Но при этоь значения Ro иногда получаются псевдооптимальными для min Т(К). Иным! словами, при заданном значении К данный способ позволяет определить значе ния R0 при почти минимальном значении Т(К). Достоинством данного способа кроме простоты, является независимость R<, от В (естественно, что при условш Ro < В). Приведены количественные оценки "погрешности" второго способ; оптимизации по отношению к первому способу оптимизации.

Третий способ оптимизации (приближенное решение для двоичнократны? Ro) является "промежуточным" между первым и вторым способами. Он позво ляет относительно просто (но сложнее, чем при втором способе) получить зна чения Kj(Ro) при меньшей (но имеющей место) "погрешности" относительнс первого способа. При этом способе существует (как и при первом способе) за висимость Ro от В. Приведена таблица значений Ki и Ro для величин ключе{ сортировки 8, 16, 24, 32, 40, 48, 64, и 80 бит. Представлены графики оцено! "погрешности" третьего способа оптимизации по отношению к первому способу оптимизации.

Для всех трех способов оптимизации при двоичнократных определяют« границы (по К и N) эффективного использования оптимизации, фактически являющиеся границами менее чем линейной зависимости T(N). Приведена табли ца значений границ по К и N с учетом разброса величин 1Д„ для величин ключей сортировки 8, 16, 24, 32, 40, 48, 64, и 80 бит. Из данной таблицы видно, чтс начиная с В=24 бита оптимизация поразрядной сортировки позволяет для N< 1000000 получить сложность алгоритма ниже линейной.

Для четвертого способа оптимизации (точное решение для двоичнонекратны> Ro) разработан метод получения значений К;. Приводится таблица значений К; Ro, bi и b2 для величин ключей сортировки 8, 16, 24, 32, 40, 48, 64, и 80 бит Сравнение оптимизированной поразрядной сортировки при двоичнократных R, и при двоичнонекратных Ro показало, что использование последней при В< 8( бит, даже при оптимистической оценке в чрезвычайно редких случаях - не боле< 30%, в нескольких случаях - не более 16,7%, а как правило - не более единш процентов. При этом, учитывая высокую сложность получения Kj для четверто го способа оптимизации, логичным является вывод о нецелесообразности ис-

пользования данного способа оптимизации.

Для второго способа оптимизации получена оценка сложности оптимизированного алгоритма сортировки. При этом все значения N разбиваются на три интервала

1 < N < В; (7)

В < N < ^ х 2В х (В х 1п 2 - 1 )/1п; (8)

1т х 2В х (В х 1п 2 - 1 )ЛП < N < со . (9)

Для интервала (7)

Т = СхВх1п2хК/(К(К)х1п2- 1), (10)

где

2К х (И. х 1п 2 - 1) = К. (11)

Из (10) и (11) видно, что <3(И) для этого интервала менее чем линейная. Для интервала (8)

(Ж>< N/(^N-0. (12)

где С - константа.

Для интервала (9) 0(>1) - линейная.

В четвертой главе приводится описание САПР ЯЕЬЕР, как пример специализированной САПР РМ, спроектированной в соответствии с принципами, описанными в главе 1 и с использованием алгоритмов, описанных в главе 3.

Описаны назначение, возможности и среда функционирования рассматриваемой САПР. Приводится описание двухуровневой структуры САПР ЯЕЬЕР (рис. 13), функционирующей в единой интегрированной среде.

Рис. 13.

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

При описании 32 ФК, обеспечивающих проектирование РП, приводится их назначение, краткое описание функционирования, характеристики входных и выходных файлов и кадры управляющих параметров и сопровождения функционирования. Такими ФК в САПР RELEF являются: "Символический ввод исходных данных"; "Препроцессор PDIF"; "Постпроцессор PDIF"; "Расстановка корпусов"; "Упорядочение цепей"; "Трассировка"; "Трассировка 2"; "Доводка непроведенных связей"; "Доводка непроведенных связей 2"; "Анализ цепей питания"; "Деление поля трассировки"; "Сбор поля трассировки"; "Препроцессор Н корпусов"; "Постпроцессор Н корпусов"; "Перенос подводов к ламелям"; "Сокращение файла базы"; "Контроль базы"; "Контроль трассировки"; "Визуализация трассировки"; "Формирование конструктивных номеров"; "Формирование таблиц проверки монтажа"; "Расчет площади металлизации"; "Постпроцессор технологического оборудования"; "Постпроцессор оптимизирующий технологического оборудования"; "Компилятор шаблона технологического оборудования"; "Визуализация и контроль монтажа"; "Вывод базы"; "Вывод поля трассировки"; "Вывод образа управляющих программ"; "Сравнение файлов"; "Копирование файла"; "Внешний вызов программы".

Описаны лингвистическое обеспечение САПР RELEF, которое состоит из "Языка описания исходных данных для сеточного проектирования монтажа", "Языка описания управляющих параметров постпроцессоров технологического оборудования", "Языка описания шаблона технологического оборудования" и "Языка описания версии САПР RELEF".

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

ходных данных для САПР ЯЕЬЕР; разработка процедур проектирования; выполнение процедур проектирования.

Кратко описана система тестирования САПР ЯЕЬЕР, обеспечивающая достаточно полный контроль работоспособности всех ФК и локализацию неправильно функционирующих ФК.

Приводится описание средств методического и маркетингового обеспечения САПР ЯЕЬЕР, которыми являются: проспект и прайс-лист; демо-версии; система тестирования; использование в учебном процессе высшего учебного заведения; защита от несанкционированного копирования. Эти средства обеспечивают рекламу, обучение профессиональной работе в САПР ЯБЬЕР, авторский надзор и защиту от несанкционированного распространения.

В пятой главе описываются результаты экспериментального исследования эффективности алгоритмов проблематичных ФК.

Для ФК "Расстановка корпусов" анализ эффективности использования способа деконцентрации групп сильно связанных ЭРЭ в алгоритме расстановки равногабаритных ЭРЭ показал следующее. При изменении процента свободных установочных мест от 1% до 14% улучшение трассируемости по показателю (1) монотонно увеличивается от 0,02% до 0,86%, однако такое увеличение не является линейным.

Для алгоритма плотного размещения разногабаритных ЭРЭ проведено две серии экспериментов.

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

- при увеличении допустимых зазоров процент дихотомического деления уменьшается (почти линейно);

- при увеличении процента дихотомического деления трассируемость по

показателю (1) улучшается (в интервале 50% -г 70% дихотомического деления трассируемость при автоматическом размещении становится лучше, чем при "ручном" размещении);

- при увеличении допустимого зазора между ЭРЭ трассируемость может как улучшаться (за счет уменьшения концентрации монтажных точек), так и ухудшаться (за счет уменьшения процента дихотомического деления). Оптимальное значение величины допустимого зазора индивидуально для каждой РП.

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

Для ФК "Упорядочение цепей" экспериментально исследовалась его эффективность по показателю трассируемости (1) для десяти различных РП. В результате установлено, что для использованных в экспериментах РП улучшение трассируемости при выполнении упорядочения цепей было в интервале 5,3% 4- 55,9% от величины Т для неупорядоченных таблиц цепей. Суммарное же увеличение времени трассировки (вместе с упорядочением цепей) не превышало 18,4% от времени трассировки неупорядоченных цепей.

Для трассировщиков экспериментально исследовалась эффективность эвристических способов повышения трассировочных способностей.

Для способа трассировки в двух описывающих прямоугольниках экспериментальные зависимости показывают, что увеличение значений параметров 1х и 1у (увеличение в дискретах по отношению к минимальному описывающему прямоугольнику соответственно по осям X и У) дает существенное увеличение трассировочных способностей базового алгоритма трассировки на интервале значений шт(1х,1у) НЮ (4.59% ч- 4.245% по показателю Т) в то время, как на интервале значений тт(1х,1у) 10^20 такое увеличение составляет всего 0.328% * 0.592%. При этом увеличение времени трассировки происходит почти линейно с коэффициентом =0.4 сек на единицу величины гшп(1х,1у).

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

ные способности, расплатой за что является увеличение времени трассировки на 12% ч- 31%. Причем увеличение значений параметров гх, ту эффективно до величины 8, а дальнейшее увеличение приводит только к весьма незначительному увеличению времени трассировки. При эффективных значениях параметров 1х и 1у - 10-И 5 использование второго описывающего прямоугольника при задании значений параметрам гх и гу равное 8 может повысить трассировочные способности базового алгоритма трассировки на 0.16% (по показателю Т) при увеличении на 16.7% + 32% времени трассировки.

Для способа ограничения числа "изломов" одной связи экспериментальные зависимости позволяют утверждать, что связи на РП обычно редко имеют более 10 "изломов" и весьма редко более 15 "изломов". При этом ограничение числа "изломов" одной связи величиной 15 во втором описывающем прямоугольнике является эффективным средством повышения трассировочных способностей базового алгоритма трассировки, а ограничение числа "изломов" одной связи в первом описывающем прямоугольнике приводит к незначительному (~ 6%) увеличению времени трассировки.

Для способа корректировки последнего луча экспериментальные зависимости подтверждают присутствие двух существенных факторов (уменьшение длины связи и блокировка дополнительной дискреты поля трассировки), "противоположно" влияющих на трассировочные способности и почти не влияющие на время трассировки. Использование оптимального значения параметра ¡с (указателя части последнего луча, на которой допустим "излом") в некоторых случаях может дать существенное (до 40% по проценту изменения показателя (1)) увеличение трассировочных способностей. Однако такое оптимальное значение индивидуально для каждой РП.

Для способа выбора направления первого луча результаты экспериментов показали, что априорный выбор "лучшего" такого направления практически невозможен, а трассировочные способности при различных направлениях первого луча могут отличаться по проценту изменения показателя (1) на 46,2%.

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

ности монтажных точек. Однако даже при этих условиях было получено боле( чем 50% улучшение трассировочных способностей (по проценту изменения пс казателя (1)), при определенных значениях управляющих параметров этого спс соба. При использовании данного способа время трассировки в проведенны экспериментах увеличивалось на 11,1% * 26,7%.

Для способа перетрассировки экспериментально показано, что его использова ние эффективно (при данном базовом алгоритме трассировки) только в сочета нии со способом введения фиктивных запретов на всем поле трассировка При этом с вероятностью =0,8 трассировочные способности увеличиваются н 10% -I- 38,5% (по показателю (1)) при увеличении времени трассировки на 69,4°/ + 107,7%.

Существенно отметить, что максимальное время трассировки при проведе нии всех экспериментов не превышало 1 мин 31 сек для РП, имеющей обще число цепей 307, число монтажных точек "типовых" цепей - 1008 и количеств! разногабаритных ЭРЭ - 68, при использовании IBM РС-АТ 360 / 40 Мгц. Эт< свидетельствует о весьма высоком быстродействии программных реализацш трассировщиков САПР RELEF.

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

Эффективность программных реализаций алгоритма доводки непроведенны) связей в САПР RELEF является весьма высокой что подтверждается следую щим. Ни в одном из более чем 50-и экспериментов по трассировке данной РП < использованием ФК "Трассировка 2" с различными значениями управляющие параметров не было получено стопроцентной трассировки, доводчик же непро веденных связей во всех 32-х проводимых экспериментах при исходном числе

непроведенных связей 1+26 обеспечивал стопроцентную трассировку не более, чем за 9 мин 46 сек (в среднем за 3,5 сек).

Для ФК "Анализ цепей питания" экспериментально исследовались зависимости времени решения систем линейных уравнений от числа уравнений в системе и зависимость точности расчета динамического режима от величины дискретности времени.

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

Схема 1 - вычисление треугольной матрицы всех N уравнений системы (полный прямой проход) и вычисление всех N корней системы (полный обратный проход). Эта схема решения используется только один раз при расчете статического режима.

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

Схема 3 - вычисление всех N корней системы (полный обратный проход). Эта схема решения используется во всех случаях, при которых не используются схема 1 или схема 2.

Проведенное экспериментальное исследование показало, что при увеличении числа узлов (числа уравнений) анализируемой цепи время решения по схеме 1 растет существенно быстрее, чем время решения по схемам 2 и 3. Увеличение времени решения системы по схеме 2 с ростом числа монтажных точек весьма незначительно. Время решения по схеме 3 более, чем в 1,5 раза меньше времени решения по схеме 2. Кроме того экспериментально определено, что время решения системы уравнений по схеме 1 для N=1588 составляет менее 3 мин., по схеме 2 - не более 10 сек., а по схеме 3 - не более 4,2 сек. Решение же

этой системы без использования способов сокращения времени, рассмотреннь в главе 3, превышает 1,5 часа для той же аппаратной платформы. Это позволж утверждать, что рассмотренные способы сокращения времени решения систем уравнений принципиально обеспечили возможность расчета за приемлемс время не только статического, но и динамического режима для цепей, имеющ* более 1000 узлов.

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

Первый эксперимент проводился способом, предложенным в главе (троекратный расчет динамического режима при Д1/2 и ¿Л/3 с последующи вычислением Д^ и расчетом динамического режима с Д^Ду. Второй и трети эксперименты - однократные расчеты динамического режима с Д12=2хД11 Д13=4хД^. Четвертый и пятый эксперименты - однократные расчеты динамич< ского режима с А14=Д1| /2 и А15=Д11/4. В каждом эксперименте фиксировалис потенциалы Щ0 в каждый момент времени с дискретностью Д^. Для каждог эксперимента (кроме пятого) была рассчитана абсолютная величина погрешнс сти Д1Л по отношению к пятому эксперименту (наиболее приближенному л значениям Щ0 к истинным величинам иф) в каждый момент времени.

В результате экспериментов установлено, что зависимость и3(ф для эксш римента 3, являясь прямой, существенно отличается от тех же зависимосте всех других экспериментов, поскольку при этом эксперименте решение систе уравнений проводилось для тех моментов времени, в которых отсутствовал сигналы возбуждающие изменение потенциалов в данном узле цепи. Зависимс сти для экспериментов 1, 2, 4 и 5 также несколько отличаются друг от друп однако имеют один и тот же характер. В отдельные моменты времени значени 11/(0 для всех экспериментов весьма близки.

При анализе максимальных значений Ди, для каждого эксперимента н всем интервале времени обнаружено, что значения Ди2 и ди3 выше допустимо го значения Ди, для которого автоматически вычислялось значение Д^, а Д111 и

ди4 не превышают величины ди. Это является предпосылкой для утверждения, что значения Д^ было выбрано близким к оптимальному (максимальному среди обеспечивающих непревышение заданной погрешности Ди). Кроме того, максимальная погрешность ДИ1 близка к допустимой погрешности ди, что свидетельствует о "не заниженном" значении Д^. Таким образом, получено экспериментальное подтверждение оптимальности выбора Д1р предложенным способом.

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

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

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

- анализируемая зависимость для управляющих программ изготовления отверстий существенно "глаже", чем такая зависимость для изготовления линий;

- оптимизированные траектории практически всегда короче неоптимизиро-ванных траекторий (для линий - примерно в 2 раза, для отверстий - примерно в 4 раза).

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

Результаты проведенных экспериментов показали следующее:

- для управляющих программ фрезерования линий трасс использование оптимизации позволило в 2,164-2,55 раз (в среднем в 2,33 раза) уменьшить длину траектории инструмента при увеличении времени формирования в 1,44^2,5 раза (в среднем в 2,23 раза);

- для управляющих программ сверления переходных отверстий длина тра-

ектории инструмента сократилась в 3,97+5,28 раза (в среднем в 4,44 раза) пр увеличении времени формирования в 4,86+5,74 раза (в среднем в 4,63 раза);

- для управляющих программ фрезерования ламелей длина траектории ин струмента сократилась в 3,51+5,11 раза (в среднем в 4,16 раза) при увеличени; времени формирования УП в 1,31+1,57 раза (в среднем в 1,43 раза).

Для ФК "Визуализация и контроль монтажа" экспериментально исследова лась зависимость времени контроля проектных норм от количества элемента проводящего рисунка (t(e)).

Экспериментальная кривая зависимости t(e) не является линейной. Однаю анализ значений At/Де показывает, что нелинейность проявляется только на ин тервале значений е 2666+4639. На интервале же 4639+6048 зависимость t(e можно считать линейной, поскольку здесь значения At/Де колеблются вокру среднего значения 0, 0454. Такие колебания можно объяснить точностью изме рения времени, которая в данном эксперименте составляет ±1 сек. При этои точность значений At/Ae составляет +6,7% + 10%. Изложенное создает предпо сылки считать зависимость t(e) асимптотически линейной.

Для оптимизированной поразрядной сортировки проводилось эксперимен тальное сравнение ее с "быстрой сортировкой" (quicksort) по быстродействию В качестве оптимизированной поразрядной сортировки использовалась сорти ровка с применением третьего способа оптимизации, описанного в главе 3.

Поскольку время выполнения оптимизированной поразрядной сортировк! практически не зависит от степени упорядоченности исходного массива, а врем; выполнения quicksort весьма существенно зависит от степени такой упорядо ченности, то в качестве тестовых исходных массивов для сравнения были вы браны три типа массивов. Первый тип - массивы, для которых в алгоритм! quicksort проводится минимальное число переназначений положения каждогс элемента (такие массивы обрабатываются quicksort быстрее любых других с тел же количеством элементов). Второй тип - массивы со "случайным" расположе нием значений ключей. Третий тип - массивы, упорядоченные по ключам в ton порядке, в котором их должна упорядочить quicksort (такие массивы обрабаты ваются quicksort "медленнее" всех других с тем же числом элементов).

В проводимых экспериментах использовались все три типа тестовых мае-

:ивов при значениях их величин 23+1535 и величинах ключей (В) - 24, 40 и 80 бит. Для сравнения быстродействия использовалось выражение

P(B,N) =

Tq(B,N)-T0(B,N)

х 100%,

(13)

T0(B,N)

где Tq(B,N) - время работы quicksort;

T0(B,N) - время работы оптимизированной поразрядной сортировки. По результатам экспериментов построены семейства зависимостей P(N) для трех значений В и трех типов тестовых массивов (рис. 14).

ДР(%)

Массивы типа 3

Массивы типа 2

767 Рис. 14

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

- при некоторых значениях В и N quicksort "быстрее" оптимизированной поразрядной сортировки, а при некоторых - "медленнее";

- с увеличением N время работы quicksort растет быстрее, чем оптимизированной поразрядной сортировки для всех типов тестовых массивов;

- с увеличением В время работы quicksort растет медленнее, чем оптимизированной поразрядной сортировки для всех типов тестовых массивов;

- для массивов третьего типа эффективность quicksort весьма мала по срав нению с оптимизированной поразрядной сортировкой.

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

В диссертационной работе обобщен опыт автора по созданию несколько версий двух САПР РМ, реализованных на двух принципиально разных аппарат ных платформах (ЕС ЭВМ и IBM РС-АТ).

Основными результатами диссертационной работы является следующее.

1. Обоснована полная заимствуемость следующих составляющих разработ ки новых САПР РМ:

- специальные требования к САПР РМ, определяемые конструкцией рель ефных плат;

- принципы разработки САПР РМ;

- математическое обеспечение;

- лингвистическое обеспечение, определяемое конструкцией РМ;

- методическое обеспечение разработки процедур проектирования РМ;

- критерии оценки функционирования САПР РМ.

2. Предложены простые оценки эффективности ФК и САПР для анализ! создаваемой САПР на ранних стадиях разработки.

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

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

5. Описаны конструктивные особенности РМ, отражающие его специфику как объекта проектирования, и сформулированы специальные требования к

САПР РМ.

6. Разработаны эффективные алгоритмы проблематичных ФК, позволяющие решать следующие задачи проектирования РМ:

- расстановка равногабаритных и размещение разногабаритных ЭРЭ;

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

- автоматическая трассировка РМ;

- автоматическая доводка непроведенных связей;

- анализ статического и динамических режимов цепей питания;

- оперативная настройка постпроцессора технологического оборудования на формат управляющих программ и оптимизация траектории инструмента;

- контроль проектных норм спроектированного проводящего рисунка.

7. Разработан алгоритм сортировки менее чем линейной сложности.

8. В качестве примера САПР РМ, разработанной в соответствии с предложенными концепциями, приведено краткое описание САПР RELEF.

9. Экспериментально подтверждена эффективность разработанных алгоритмов всех проблематичных ФК САПР РМ.

10. Экспериментально подтверждена эффективность разработанной сортировки менее чем линейной сложности путем сравнения ее с "быстрой сортировкой" (quicksort).

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

1. Кокотов В. 3. Комплекс программ автоматизации проектирования рельефных печатных плат. - Вопросы радиоэлектроники, сер. ЭВТ, 1982, вып. 1, с. 21 -27.

2. Кокотов В. 3. Оптимизация управляющих параметров программ трассировки при техническом проектировании печатных плат и больших интегральных схем. - Труды Всесоюзной научно-технической конференции "Автоматизация проектирования ЭВМ и систем", Ереван, 1983, с. 98 - 99.

3. Кокотов В. 3. Деконцентрация групп сильно связанных элементов при автоматической расстановке в САПР. - Вопросы радиоэлектроники, сер. ЭВТ, 1984, вып. 1, с. 87-91.

4. Кокотов В. 3. Уменьшение машинных ресурсов при трассировке коне: руктивов с большим трассировочным пространством. - Материалы Всесоюзно школы-семинара "Разработка и внедрение в народное хозяйство ЕС ЭВМ' Тбилиси, 1987, с. 34 - 36.

5. Кокотов В. 3., Кирсанов А. Е., Иванов М. А. Конструирование толстс пленочных микросборок с применением комплекса прикладных программ авте матизации проектирования рельефных печатных плат. - Материалы III Всесс юзной научно-технической конференции "Состояние и перспективы развита гибридной технологии и гибридных интегральных схем в приборостроении' Ярославль, 1991, с. 23 - 24.

6. Кокотов В. 3., Кирсанов А. Е., Коновалова Г. В., Иванов М. А. Адаптг ция САПР рельефных плат к проектированию толстопленочных микросборок. Технология и конструирование в электронной аппаратуре, 1992, № 1, с. 55 - 58.

7. Кокотов В. 3. САПР RELEF для проектирования рельефного печатног монтажа. - Технология и конструирование в электронной аппаратуре, 1993, № 1 с. 10-14.

8. Кокотов В. 3. Конструкции, технология и автоматизированное проекта рование рельефного монтажа. Учебное пособие -М.: Издательство МАИ, 1998 96 с.

9. Кокотов В. 3., Сычева Е. В. САПР рельефного монтажа. - PCWEEI (RUSSIAN EDITION), 1998, 24 марта - 30 апреля, № 11 (135), с 37.

10. Кокотов В. 3. Автоматизированное проектирование рельефного монта жа. - Проблемы информатизации, 1998, № 3, с. 43 - 48.

11. Кокотов В. 3. Поразрядная сортировка менее чем линейной сложности - Информационные технологии, 1998, № 10, с. 14 - 21.

12. Кокотов В. 3. Алгоритм плотного размещения разногабаритных эле ментов на плате. - Информационные технологии, 1998, № 11, с. 16-21.

НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ "АРГОН"

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

05.13.12 - системы автоматизации проектирования

Диссертация на соискание ученой степени доктора технических наук

Москва - 1998

СОДЕРЖАНИЕ

ВВЕДЕНИЕ......................................................................................................... 8

Глава 1. ПРОБЛЕМЫ СОЗДАНИЯ И КОНЦЕПЦИИ ПОСТРОЕНИЯ САПР РЕЛЬЕФНОГО МОНТАЖА

1.1. Проблемы создания специализированной САПР РМ......................... 17

1.1.1. Специфика разработки САПР РМ.................................................... 17

1.1.2. Типовые и нетиповые составляющие разработки САПР РМ........ 18

1.2. Понятия эффективности и классификация ФК САПР на стадии их разработки............................................................................................... 21

1.2.1. Эффективность ФК и САПР.............................................................. 22

1.2.2. Основные и неосновные ФК............................................................. 26

1.2.3. Проблематичные и непроблематичные ФК..................................... 27

1.3. Принципы разработки САПР РМ.......................................................... 28

1.3.1. Принцип основных проблематичных ФК..:..................................... 29

1.3.2. Принцип функциональной полноты................................................. 30

1.3.3. Принципы универсальности, специализации и унификации........ 31

1.3.4. Принципы компактности и неизменности информационной

базы.................................................................................................... 33

1.3.5. Принцип единства интерфейса пользователя.................................. 33

1.3.6. Принцип однородности системных и языковых средств

разработки......................................................................................... 34

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

Глава 2. КОНСТРУКТИВНЫЕ ОСОБЕННОСТИ РЕЛЬЕФНОГО

МОНТАЖА КАК ОБЪЕКТА ПРОЕКТИРОВАНИЯ

2.1. Предпосылки появления рельефного монтажа.................................... 36

2.2. Конструкции рельефного монтажа........................................................ 37

2.3. Варианты шагов трассировки................................................................. 39

2.4. Трассировочные возможности............................................................... 41

2.5. Сильноточные цепи рельефного монтажа............................................ 43

2.6. Взаимовлияющие цепи рельефного монтажа....................................... 45

2.7. Специальные требования к САПР РМ.................................................. 46

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

Глава 3. ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ И АЛГОРИТМИЧЕСКОЕ

ОБЕСПЕЧЕНИЕ ПРОБЛЕМАТИЧНЫХ ФУНКЦИОНАЛЬНЫХ КОМПОНЕНТОВ 3.1. Расстановка корпусов.............................................................................. 49

3.1.1. Расстановка равногабаритных корпусов.......................................... 49

3.1.2. Постановка и специфика задачи плотного размещения

разногабаритных ЭРЭ...................................................................... 53

3.1.3. Выбор критериев плотного размещения.......................................... 54

3.1.4. Принцип совмещения противоречивых критериев при

размещении....................................................................................... 56

3.1.5. Выбор и модификация алгоритма размещения по критерию

минимального количества связей в сечениях............................... 56

3.1.6. Эвристический метод решения задачи оптимального

раскроя................................................................................................. 59

3.1.7. Описание общего алгоритма плотного размещения разногабаритных ЭРЭ........................................................................ 62

3.1.8. Направления совершенствования алгоритма размещения разногабаритных ЭРЭ и алгоритма раскроя.................................... 65

3.2. Упорядочение цепей................................................................................ 67

3.3. Трассировщики........................................................................................ 70

3.3.1. Выбор базового алгоритма трассировки.......................................... 71

3.3.2. Базовый алгоритм трассировки......................................................... 72

3.3.3. Способы повышения быстродействия............................................. 75

3.3.4. Способы повышения трассировочных способностей.................... 77

3.3.5. Дополнительные возможности......................................................... 83

3.4. Доводчики непроведенных связей......................................................... 86

3.4.1. Принцип работы алгоритма доводки непроведенных связей....... 86

3.4.2. Порожденный граф цепи................................................................... 88

3.4.3. Способы формирования порожденного графа цепи и нахождения мешающих цепей.......................................................... 90

3.4.4. Алгоритм доводки непроведенных связей...................................... 91

3.4.5. Анализ эффективности и пути совершенствования алгоритма доводки непроведенных связей........................................................ 94

3.5. Анализ цепей питания............................................................................. 98

3.5.1. Формальная постановка задачи......................................................... 98

3.5.2. Описание модели................................................................................ 100

3.5.3. Повышение точности решений системы разностных уравнений. 107

3.5.4. Сокращение времени решений линейной системы уравнений..... 110

3.5.5. Определение исходной дискретности времени разностных уравнений............................................................................................ 111

3.5.6. Укрупненный алгоритм анализа цепи питания............................... 113

3.5.7. Направления совершенствования метода анализа цепей

питания................................................................................................ 113

3.6. Постпроцессоры технологического оборудования.............................. 116

3.6.1. Способ настройки на формат управляющих программ технологического оборудования...................................................... 117

3.6.2. Способы оптимизации траектории инструмента............................ 119

3.7. Визуализация и контроль монтажа........................................................ 122

3.7.1. Функция визуализации монтажа....................................................... 123

3.7.2. Функция контроля проектных норм................................................. 124

3.8. Сортировка менее чем линейной сложности........................................ 134

3.8.1. Принцип оптимизации алгоритма поразрядной сортировки........ 134

3.8.2. Первый способ оптимизации............................................................ 137

3.8.3. Определение tn / tm.............................................................................. 143

3.8.4. Оценка эффективности первого способа оптимизации................. 143

3.8.5. Второй способ оптимизации............................................................. 148

3.8.6. Оценка эффективности второго способа оптимизации................. 149

3.8.7. Третий способ оптимизации.............................................................. 153

3.8.8. Оценка эффективности третьего способа оптимизации................ 154

3.8.9. Определение границ эффективности оптимизации поразрядной сортировки........................................................................................... 155

3.8.10. Обобщение способа оптимизации для двоичнонекратных разрядов............................................................................................... 156

Сравнение оптимизированных поразрядных сортировок с

использованием двоичнократных и двоичнонекратных

разрядов............................................................................................... 162

3.8.12. Оценка сложности оптимизированного алгоритма

сортировкипри втором способе оптимизации................................. 166

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

Глава 4. ОПИСАНИЕ САПР RELEF

4.1. Назначение, возможности и среда функционирования....................... 172

4.2. Структура и состав.................................................................................. 172

4.3. Информационная база............................................................................. 173

4.3.1. Файлы САПР RELEF.......................................................................... 174

4.3.2. Директории САПР RELEF................................................................. 175

4.4. Режимы работы интегрированной среды САПР RELEF..................... 175

4.4.1. Режим "Выполнение программ"....................................................... 175

4.4.2. Режим "Редактор процедур".............................................................. 176

4.4.3. Режим "Выполнение процедур"........................................................ 177

4.4.4. Режим "Учебник"............................................................................... 177

4.5. Описание ФК............................................................................................ 178

4.5.1. Символический ввод исходных данных.......................................... 179

4.5.2. Препроцессор PDIF............................................................................ 179

4.5.3. Постпроцессор PDIF........................................................................... 180

4.5.4. Расстановка корпусов......................................................................... 181

4.5.5. Упорядочение цепей.......................................................................... 181

4.5.6. Трассировка и Трассировка 2............................................................ 182

4.5.7. Доводка непроведенных связей и Доводка непроведенных

связей 2............................................................................................... 182

4.5.8. Анализ цепей питания........................................................................ 184

4.5.9. Деление поля трассировки................................................................. 185

4.5.10. Сбор поля трассировки.................................................................... 186

4.5.11. Препроцессор H корпусов............................................................... 187

4.5.12. Постпроцессор H корпусов............................................................. 188

4.5.13. Перенос подводов к ламелям.......................................................... 188

4.5.14. Сокращение файла базы.................................................................. 189

4.5.15. Контроль базы................................................................................... 189

4.5.16. Контроль трассировки...................................................................... 190

4.5.17. Визуализация трассировки.............................................................. 191

4.5.18. Формирование конструктивных номеров...................................... 192

4.5.19. Формирование таблиц проверки монтажа..................................... 193

4.5.20. Расчет площади металлизации........................................................ 194

4.5.1. Постпроцессор технологического оборудования и

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

4.5.22. Компилятор шаблона технологического оборудования.............. 196

4.5.23. Визуализация и контроль монтажа................................................. 197

4.5.24. Вывод базы........................................................................................ 198

4.5.25. Вывод поля трассировки.................................................................. 198

4.5.26. Вывод образа управляющих программ.......................................... 199

4.5.27. Сравнение файлов............................................................................. 200

4.5.28. Копирование файла.......................................................................... 201

4.5.29. Внешний вызов программы............................................................. 201

4.6. Лингвистическое обеспечение............................................................... 202

4.6.1. Язык описания исходных данных для сеточного проектирования монтажа................................................................... 202

4.6.2. Язык описания управляющих параметров постпроцессоров технологического оборудования...................................................... 205

4.6.3. Язык описания шаблона технологического оборудования........... 206

4.6.4. Язык описания версии САПР RELEF............................................... 213

4.7. Проектирование рельефных плат в САПР RELEF............................... 214

4.7.1. Системные подготовительные операции......................................... 215

4.7.2. Подготовка исходных данных для САПР RELEF........................... 219

4.7.3. Разработка процедуры контроля и корректировки исходных данных.................................................................................................. 222

4.7.4. Контроль и корректировка исходных данных для САПР

RELEF........................................................................................................ 225

4.7.5. Разработка процедур проектирования............................................. 227

4.7.6. Выполнение процедур проектирования........................................... 231

4.8. Тестирование............................................................................................ 231

4.9. Методическое и маркетинговое обеспечение...................................... 232

4.9.1. Проспект и прайс-лист....................................................................... 232

4.9.2. Демоверсии.......................................................................................... 233

4.9.3. Система тестирования........................................................................ 234

4.9.4. Учебник............................................................................................... 234

4.9.5. Использование в учебном процессе высшего учебного заведения............................................................................................. 234

4.9.6. Защита от несанкционированного копирования............................. 235

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

Глава 5. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ

ЭФФЕКТИВНОСТИ АЛГОРИТМОВ ПРОБЛЕМАТИЧНЫХ ФУНКЦИОНАЛЬНЫХ КОМПОНЕНТОВ

5.1. Расстановка корпусов.............................................................................. 237

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

5.1.2. Экспериментальный анализ эффективности алгоритма плотного размещения разногабаритных ЭРЭ и ее зависимости

от значений управляющих параметров............................................ 238

5.2. Упорядочение цепей................................................................................ 244

5.3. Трассировщики........................................................................................ 245

5.3.1. Исследование эффективности трассировки в двух описывающих прямоугольниках...................................................... 246

5.3.2. Исследование эффективности ограничения числа изломов

одной связи.......................................................................................... 250

5.3.3. Исследование эффективности корректировки последнего луча... 253

5.3.4. Исследование эффективности выбора направления первого

луча....................................................................................................... 256

5.3.5. Исследование эффективности введения фиктивных запретов...... 257

5.3.6. Исследование эффективности перетрассировки............................. 259

5.4. Доводчики непроведенных связей......................................................... 260

5.5. Анализ цепей питания............................................................................. 262

5.5.1. Исследование зависимости времени решения системы линейных уравнений от ее размерности.......................................... 262

5.5.2. Исследование точности решений при анализе цепей питания...... 266

5.6. Постпроцессоры технологического оборудования.............................. 269

5.6.1. Исследование зависимости длинны траектории инструмента от минимального количества точек обхода в одной области............. 269

5.6.2. Анализ эффективности оптимизации минимального количества точек обхода в одной области........................................................... 272

5.7. Визуализация и контроль монтажа........................................................ 274

5.8. Экспериментальное сравнение оптимизированной поразрядной сортировки с быстрой сортировкой................. .................................... 276

5.9. Выводы к главе 5..................................................................................... 278

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

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

ПРИЛОЖЕНИЯ

Приложение 1. Акты внедрения результатов диссертационной работы.. 289

Приложение 2. Получение множителя К -(Ы х п,—) в выражении

п

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

линейной сложности....................................................................................................................296

ПЗ. 1. Доказательство свойства 1..............................................................................................................................297

П3.2. Доказательство свойства 2..............................................................................................................................297

ПЗ.З. Доказательство свойства 3..............................................................................................................................297

П3.4. Доказательство свойства 4..............................................................................................................................298

ПЗ.5. Доказательство свойства 8..............................................................................................................................300

П3.6. Доказательство свойства 9..............................................................................................................................301

Приложение 4. Пример описания исходных данных для сеточного

проектирования монтажа....................................................................................................303

Приложение 5. Примеры описаний управляющих параметров

постпроцессоров технологического оборудования........ 308

Приложение 6. Пример описания шаблона технологического

оборудования............................................................................................................................................311

Приложение 7. Проспект САПР КЕЬЕБ............................................................................................................321

Приложение 8. Прайс-лист САПР КЕЬЕР......................................................................................................323

Приложение 9. Используемые сокращения..................................................................................................324

ВВЕДЕНИЕ

В настоящее время существует значительное количество различных технологических процессов изготовления печатного монтажа (ПМ). Большая часть таких технологических процессов диктует свои правила выполнения проводящего рисунка.

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

- создание универсальных САПР, обеспечивающих проектирование проводящего рисунка для широкого спектра технологических процессов изготовления ПМ;

- создание специализированных САПР, ориентированных на какую-либо одну (иногда несколько близких по правилам выполнения проводящего рисунка) технологию ПМ.

Обычно расплатой за универсальность бывает меньшая эффективность работы универсальных САПР по сравнению со специализированными. Под меньшей эффективностью работы здесь понимается:

- большая сложность и продолжительность настройки на конкретные правила выполнения проводящего рисунка;

- меньшие трассировочные способности;

- большее время цикла проектирования.

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