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

Р Г Б ОД

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

ВЛАСОВ Сергей Евгеньевич

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

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

АВТОРЕФЕРАТ ДИССЕРТАЦИИ на соискание ученой степени кандидата технических наук

»

Н.Новгород 1995

Работа выполнена на кафедре "Конструирование и технология радиоэлектронной аппаратуры" Нижегородского государственного те;:нического университета.

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

¡Ю.Е.Седаков I

I___1

заслуженный деятель науки РФ. доктор технических наук, профессор Д. И. Батащев

Официальные оппоненты: академик Международной академии

информатизации. Академии естественных наук, доктор технических наук, профессор А.М.Бершадский

кандидат технических наук .доцент И. В. Полозов

Ведущая организация: Научно - исследовательский институт

технологии и организации промышленности (г.Н.Новгород)

Защита состоится -/_» ШШЯг 1995 г. в часов на заседании диссертационного • совета Д.063.85.02 Нижегородского государственного технического университета по адресу: 603600, г.Нижний Новгород, ул.Минина, 24. НГТУ, корпус/, аудитория 12{¡'З.

С диссертацией моано ознакомиться в научно - технической библиотеке университета.

Автореферат разослан 1995 г

афгж

Ученый секретарь диссертационного Совета ' г кандидат технических наук А.П.Иванов

У^здУТО. ЧГ^то 1Газтак6а?х9а4в'./1|6с^У писчая- Печать офе™«.

кп?л??Т0Еи2 офсв7ной печати полиграфической базы НГТУ бозогг, н. Новгород, просп. Гагарина, 1.

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

•Актуальность темм.

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

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

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

Для аналоговой н аналогово-цифровой техники (ПП, мпсросбор-ки. гибридные интегральные микросхемы (П1С)) . ШП с открытия контактными пловдкаки (МПП с ОКЕ) . функциональных устройств микроэлектроники, т.е. устройсгз с существенно_ нерегулярной структурой и, в особенности, с однослойной коммутацией суцест-вувцие конструкторские САЛР либо недостаточно эффективны, либо не ориентированы на современные средства вычислительной техни-

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

Настоящая работа посвящена исследованию и разработке системы конструкторского проектирования топологии гибких полиимидных носителей (ГПН) в автоинтерактивном режиме на базе ПЭВМ типа IBM PC, подготовлена по открытому плану НИИ измерительных' систем в соответствии с научно-исследовательской программой "Разработка комплекса технологических процессов и средств автоматизации, обеспечизавщих проектирование и изготовление печатных плат 4-5 класса точности" (тема "Точность").

Цель работы. '

Целью диссертационной работы является исследование и разработка математических моделей коммутационного поля, алгоритмов и программных модулей для трассировки устройств РЭА, имеющих нерегулярную структуру и однослойную коммутацию. Разработанные алгоритмы реализованы в вида САПР конструкторского проектирования гибких полиимидных носителей. - которые представляют собой односторонние металлополимерные ГШ и предназначены для соединения бескорпусных кристадлов ИС с монтакно-коммутационными платами. Основной задачей, возникающей при конструкторском проектировании ГПН. "является трассировка соединений с соблюдением конструкторско-технологических ограничений.' Однослойная коммутация устройства выдвигает в качестве базового критерия эффективности алгоритмов трассировки требование 100-процентной реализации связей. Программное обеспечение системы функционирует на ПЭВМ класса IBM PC. реализует полный цикл проектирования устройства (от ввода исходных данных до выдачи программ для технологического оборудования), обеспечивает интерактивный рении работы.

Для достижения^ данной цели решались следующие задачи:

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

соединений;

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

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

- разработка структур данных, системной и программной реализации системы конструкторского проектирования ГЛН.

Методы исрлеяования.

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

Научная норизща работы:

- задача конструкторского проектирования ГПН представлена в виде набора многокритериальных задач оптимизации. Для которых определены методы решения с использованием различных моделей принятия решений;

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

- разработаны алгоритмы формирования макродискретного рабочего поля (МРП) ка основе триангуляционной модели, ребра которой оптимально соединяв? особые точки КШ:

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

- разработан комбинированный алгоритм трассировки мезсоеди-нений в одном слое,- сочетаний геометрические методы и принципы гибкой трассироаки. в котором построение трассы цепи рассматривается как задача поиска пути в лабиринте, образованная запретными областями и ранее реализованными проводника^;;

- на базе разработанных методов. структур данных, сценариев проектирования реализована азтокнтерактквная САПР ГПН.

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

' Реализованные в системе алгоритмы и программные модули могут быть эффективно применены для проектирования и верификации топологии других устройств МЭА и РЭА: ГИС. ЕЛ. имеющих однослойную коммутацию -и нерегулярную структуру.

Внедрение результатов работы.

САПР ГПН используется в НИИ измерительных систем (г. Н.Новгород) для.разработки приборов по ряду тем с целью повышения уровня интеграции МЭА и.снижения ее ыассогабаритных характеристик.

АцроОЗЩЩ РЭбРТН-

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

- научно - практической конференции "Состояние н перспективы развития САПР ПРАМ 5.3-91" г. С.-Петербург, 1991.г.;

- научно - техническом семинаре "Применение персональных ЭВМ в проектировании и технологии* г. С.-Петербург, 1991 г.;

- отраслевых научно - практических семинарах "Состояние работ по САПР РЭА в отрасли" г. Москва. 1991-1992 г.;

- научно - техническом семинаре "Прикладные интеллектуальные системы" г. Иосква. 1992 г.;

- отраслевом семинаре "Проблемы и перспективы развития работ по САПР в отрасли" г. Протвино, 1992 г.;

- научном семинаре при кафедре "Информатика и автоматизация научных исследований" НГУ г. Н.Новгород. 1995 г.

С целью апробации разработанная система демонстрировалась и обсуждалась со специалистами в области САПР и конструирования РЭА НГУ. НГТУ, БНИИА (г. Москва). НПО "Физика" (г. Москва). Публикации- ' '

Научные результаты были изложены и опубликованы в 7 печатных работах и 1 монографии. .

б .

' Структура и объем paOofij.

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

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

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

В первой главе приводится описание конструкций ГПН как объекта проектирования в САПР, типовых оптимизационных'многокритериальных задач конструкторского проектирования ГПН, рассмотрены алгоритмические подхода к реализации задач трассировки в САПР, сформулирован комбинированный метод для синтеза топологии ГПН.

В п. 1.1. рассмотрены современные-конструкции, способы компоновки и монтажа устройств НЭА, конструктивно-технологические приемы, направленные на снижение массогабаритных показателей и повышение уровня интеграции приборо'з.

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

?

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

В п.1.2. рассмотрена конструкция ГПН и выделены его специфические характеристики как объекта проектирования в САПР.

Ленточный носитель представляет собой конструктивный узел -гибкую одностороннюю металло-полимернув (алзоминий-полиимид) ПЛ. включающую в себя топологию проводящего слоя, формируемую методом фотолитографии й выполненную в виде взаимосвязанных зон, диэлектрический рисунок, ■ базовые и технологические отверстия, маркировку. Топология ГШ показана на рис.1.

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

- однослойная коммутация металло-полимерной платы:

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

- произвольная, ориентация элементов проводящего слоя топологии. -

В п. 41.3. описаны постоянные, переменные и выходные параметры устройства на ГПН. выполнена математическая постановка оптимизационных задач трассировки ГПН, рассмотрены подхода к- их ре. • шению.

Задача трассировки (синтеза'топологии ГПН) связана с решением ряда задач конструкторского проектирования ГПН:

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

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

- достиаение минимального времени прохождения сигнала между ЙС в блоке ЫЭА (3) ;

- достижение минимальных материалоемкости и массогабаритных - показателей (4) ;

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

- проектирование устройства из типовых оптимизированных конструкций, повышение его серийнопригодности. технологичности, обеспечение хорошей ремонтнопригодности (6).

Основным показателем успешного решения задач (1) - (6) является формирование планарной топологии ГШ (стопроцентной разводки связей), при которой трассы проложены оптимальным образом и имеют минимально возможную длину.

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

- решение комбинаторной задачи, которая заключается в выборе из ГтИ возможных вариантов оптимального порядка трассировки связей, при котором обеспечиваются наилучше показатели критериев: 5 к 5, т1п ? ), где 3 -число нереализованных соединений, 1 - длина I соединения;

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

В п. 1.4. проанализированы существующие подходы алгоритмического решения задачи трассировки для определения наиболее эффективных методов решения задач (1) - (6). позволяющие получать планарную топологию ГПН.

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

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

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

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

Исследовать и разработать методы оптимального упорядочения цепей для трассировки и трассировки межсоединений для односторонних монтажно-коммутационных плат-с нерегулярной структурой. На базе данных методов реализовать эффективные программные модули трассировки подобных устройств. Разработать автоматизированную систему конструкторского проектирования ГПН. функционирующую на ПЭВМ класса IBM PC/AT. допускающуа сквозной цикл проектирования и обеспечивающую: ввод, просмотр и редактирование исходной информации для процесса проектирования; . синтез топологии ГПН; просмотр результатов проектирования и редактирование топологии в интерактивном режиме; формирование управляющих программ для получения фотошаблонов и выпуск комплекта конструкторской документация на ГПН.

Во второй главе приводится описание методов решения задачи проектирования ГПН на основе геометрических процедур трассировки.

В п! 2.1. рассматриваются модели МКП, позволяющие адекватно отражать его метрические и топологические параметры so -время трассировки. Показано, что использование дискретных топологических моделей ( множества квадратных ячеек со стороной d , d = h + Д , Ь - щрина проводника, Д - допустимый зазор ~ менду проводниками) не позволяет эффективно реализовать процедуры синтеза топологии с отрезками произвольной ориентации, не обеспечивает возможностей модификации положения ранее реализованных проводников в ходе построения текущего соединения. 10

Для описания параметров коммутационного пространства ГПН автором предложена комбинированная модель, содержащая: ■

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

- вектора ресурсов . где "Цк -ресурс К. направления вдоль ^ контакта, равный максимальному числу печатных проводников, которые возможно провести на дискретной модели, огибая контакт по смежным ортогональным направлениям;

- контура запрещенных для трассировки областей и внешнюю границу ГПН, которые описываются координатами образующих их отрезков и уравнениями прямых и - йХ 6 . содержащих данные отрезки;

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

Грани МРП описываются номерами входящих в них ребер, для каждого ребра хранится упорядоченный список пересекающих его . трасс. Пропускные способности ребер граней слузглт для учета числа трасс, которые пересекают участок конструктива-между особыми точками, вектора ресурсов'вероин - для учета трасс, поворачивающихся вокруг вершин в определенном направлении. На рис.2 представлена грань МРП и описаны ее метрические параметры.

' Данная математическая модель Ш1 ГПН позволяет:

- описывать любые элементы топологии ГШ (его переменные л выходные параметры) и координаты их расположения на МКП. обеспечивая на этапе трассировки пеиск оптимальных ресений экстремальных задач (1) - (6);

- в ходе трассировки однозначно определять число.. проводник ков, проходящих мегду особыми точка«! ККП (пересекающих ребра граней) и поворачивающихся вокруг особых точек;

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

- обеспечивать 'гибкость'^проложенных трасс в пределах граней на первом этапе трассировки:

Технологическое Контактная площадка Зона контактирования

Рис. 1. Топология гибкого полиишдного носителя

RFOn/CKlbE СПОСОБНОСТИ PES' гез (AB), гез ШС). • res (АС) УЧГГЪВАЮТ

чисхо трасс, проходящх юду ocoEtju токами грани:

гез(АВ1 =2 . гез (ЕС) = 3. гез(АО=3.

ESTOPA FECVTCOß Ra. Rb. Rc ^ЯПСАОГ Н5СП0 ТРАСС, СГИБАВШИХ BffUlWfPAHt Гд» Г д,- 1, Гс. ГСГ 2, ГВ=ГВГ1.

Рис. 2. Фрагмент МРП

- легко получать точные координаты проводников после реализации плоской укладки всех электрических соединений на МКП.

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

Для каждой вершины j- ( = •!,// ). соответствующей контакту элемента, с помощью цифровой волновой процедуры определяется вектор ресурса . При формировании компонент вектора ресурса производится соединение ребром J. вершины с теми вершинами,точками излома запретных областей и конструктива, которые попали в последний фронт волны.

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

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

Вычисляются пропускные способности каждого ребра. На основании построенных ребер формируются описания макродискретов.

В п. 2.2. рассматриваются методы реализаций бесперекрёстного леса соединений на основе геометрических методов. Задача трассировки ГПН формулируется следующим образом: в соответствии с указанными связями L'b , t=*i,m выполняя1 конструкторско -технологические ограничения, соединить все bl контактов кусочно-ломаными отрезками прямых таким образом, чтобы:

1) ks?доё построенное соединение Li. имело минимальную длину li: mini;, tM.m ;

2) число пересечения S при реализации всех m связей было наименьшим : mln S (7).

Показано, что решение векторной задачи оптимизации (7) ■ с использованием метода '-жгидазацин уступок по каждой связи и аддитивного обобщенного критерия сводится к следующей экстремальной задаче:

Пг»1и1 (^-й), 2=0 ...

Для решения задачи (8) предлагается следующая комбинированная процедура.

Каждая контактная площадка заменяется вершиной с фиксированными координатами X;,, , I - \ ^И , для которой определяется вектор ресурсов . Формируется МРП, на котором в виде особых точек представлены контактные площадки и -запретные для трассировки области.- Пропускные способности ребер макродискретов вычисляются с учетом размеров и формы контактных площадок.

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

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

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

Нереализованные соединения могут доразводиться волновш алгоритмом или в интерактивном резаке.

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

ровку автором предлагается следующая оценка:

О).

- коэффициент важности соединения:

L - длина между парами контактов в евклидовой метрике :

' К00РДИ!1аты контактов;

Й - число пересекаемых ветвей минимальных связывающих деревьев еще не реализованных связей:

Ш - число пересекаемых построенных соединений и запретных областей;

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

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

На очередном шаге для каждой нереализованной связи L. ¿-i,hi вычисляется значение pj, по (9), для трассировки выбирается соединение, имеющее минимальную величину 'Р=ГПУЗ Pl-

t.*a,m<

Другой подход к решению задачи выбора наилучыего порядка трассировки m связей заключается в применении алгоритмов, которые за линейное число итераций трассировки позволяют выбрать из Hl! возможных вариантов оптимальное упорядочение соединений, гарантирующее наилучшее значение функции качества (например, минимальную суммарную длину связей). К таким методам относятся генетические алгоритмы, применение которых для решения задачи упорядочения связей рассматривается в п.'3.2.

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

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

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

ти^чеДк^ч^О . т. е. огибаемые вершины и пересекаемые ребра должны иметь ненулевые значения ресурсов.

Базовая вершина для обхода препятствия и направление обхода выбираются по следующим критериям:

А) число пересечений (S) с другими соединениями минимально

. min S ;

Б) величины ресурсов вершины и пересекаемых при ее огибании_ ребер граней максимальны maxmln;

Б) суммарная длина огибающих ребер (I) как можно меньше отличается от длины заменяемого ребра t* :

minft-n .

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

После построения соединения предпринимается попытка улучшения его конфигурации путем итерационной замены отрезков (ЦЧУи (i4,L+2") Ha(t,i+2) . если при этом отсутствуют пересечения с препятствиями и положительны значения ресурсов огибаемых вершин и- пересекаемых ребер.

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

В п. 2.4. рассматриваются методы получения точной конфигурации проводников на этапе микротрассировки (геометрической укладки). В результате анализа возможных типов рисунков нежсоеди-

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

Глава 3 посвящена описанию программной реализации САПР ГПН на ПЭВМ типа IBM PC.

В п. 3.1. рассмотрено линвистическое и информационное обеспечение системы. Алгоритмическое обеспечение САПР ГПН реализует следующие функциональные возможности: . - ввод и верификацию исходных данных;

- синтез топологии ГПН;

- получение таблиц контроля топологии переменной часта ГПН:

- формирование данных дл% редактирования топологии в интерактивном режиме;

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

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

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

Первоначальная

030Я

-Пгрвдачаупрадлаиия г=5> -Пгргдачеяаиккх

Рис. 3. Схема построения САПР ГПН

объект.

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

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

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

Под критерием оптимальности- реализации N связей в процессе трассировки принимается суммарная длина всех разведенных трасс: Q~Z{Il . где Ц - длина проводников Ь - ой связи.

Генотипом Пй^4) называется битовая строка следующей структуры: -

% ... h ... %-к %

12 К Н-Ч Н

где Ъ;, - номер электрической связи, которая будет разводиться I - ой по порядку в процессе раззодки N связей;

Мера, приспособленности - значение обобщенного критерия оценки качества трассирсвки всех чения гэ.чотипа Г(си):

связей для конкретного зна-

jUfat

±

G-t-Jt-Q S - число пересечений:

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

cL - "штраф" за 1 пересечение.

Особь йв. с генотипом ГС&с^ и мерой приспособленности J^ÍQ-kV эта печатная плата (ГПН). на которой проведена трассировка всех íí связей в порядке, указанном генотипом ) •

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

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

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

помощью комбинированного подхода: геометрических методов и методов гибкой трассировки;

- по полученной реализации всех связей вычисляется мера приспособленности JÜ. .

Если условие окончания поиска оптимального решения:

maa jnfaí), at e ^

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

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

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

Приведены операции, выполняемые конструктором при редактировании топологии, выпуске чертежей ГШ и реализуемые средствами графического редактора, описаны структуры базовых графических примитивов, передаваемых' в САПР AutoCAD для формирования послойной топологии ГПН.

J В 4 главе рассматриваются вопросы применения САПР ГПН в сквозном цикле проектирования устройств МЭА.

В п. 4.1. представлена схема сквозного цикла конструирования ячеек МЭА. показаны конструктивно - технологические направления, при использовании которых • достигаются наилучшие показатели качества приборов. Данные подходы основаны на использовании:

- бескорпусных БИС и СБИС на ГПН;

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

- многослойных (до 10 - 12 слоев) коммутационных плат на по-лиимиднсй пленке (ИПП - ГШ) с ОКП и разводкой, выполненной по тонкопленочной технологии, используемых для коммутации в пределах функциональной ячейки;

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

При непосредственном участии автора разработан пакет прикладных программ (ПИП) трассировки !ШП с ОКП, который моает быть эффективно -применен для разводки ШШ - ПМ с ОКП. В данном ППП реализованы следующие возможности, отличные от стандартных волновых методов:

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

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

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

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

Для реализации ИСАПР бортовой МЭА на основе бескорпусных БИС с ГПН и МПП - ГО! (со сквозными переходными отверстиями либо ОКП) предложено:

а) дополнить. функциональные возможности САПР ГПН следующими процедурами:

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

- разработать модули разводки балочных выводов ГПН на контактные площадки знакоместа;

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

В п. 4.2. рассмотрены типовые сценарии проектирования с использованием САПР ГПН. Описаны процедуры ввода исходных данных, автоматического синтеза и редактирования топологии в интерактивном региые,. получение таблиц контроля топологии ГПН. Приведены копии, экранов, полученных в ходе Функционирования системы, рисунки с топологией спроектированных устройств ГПН для KMC средней степени интеграции и БИС на базовых матричных кристаллах.

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.

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

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

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

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

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

гз

достигает минимального значения.

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

Основное содержание диссертации опубликовано в следующих научных работах:

1. Батищев Д.И.. Власов С.Е.. Морозов В.Ф. Геометрический подход к трассировке соединений нерегулярных структур // Тез. докладов конференции. Опыт разработки и применения приборно -технологических САПР микроэлектроники. - Львов: ПО Полярон, 1995. - С. 13 - 14.

2. Батищев Д.И.. Власов С.Е.. Морозов В.Ф. Планаризация графа соединений с учетом метрико - технологических ограничений // Оптимизация и моделирование в автоматизированных системах: Межвузов, сб. науч. трудов. - Воронеж. 1995. - С. 63-70.

3. Власов С.Е. Разработка программ в интегрированной среде 'îyp6o Си. - Н.Новгород, 1992. - 114 с.

4. Власов С.Е. Эффективный алгоритм трассировки для структур с однослойной коммутацией // Вопросы атомной науки и техники. - Ы. : ЦНИИатоминфорк, 1993. - HI. - С. 29-31.

5. Власов С.Е. Создание интегрированной САПР РЭА. // Вопросы атомной науки и техники. - И. : ЦНИИатомикформ, 1993. -Hl. - С. 32-35.

6. Власов С.Е. Построение накродискрегного рабочего поля для реализации трассировки межсоединений // Оптимизация и моделирование в автоматизированных системах: Ыеавузов. сб. науч. трудов. - Воронег, 1995. - С. 60-62.

7. Власов С.Е., Морозов В.®. Автоматизированная система конструкторского проектирования гибких кристаллоносителей // Тез. докладов конференции. Опыт разработки и применения приборно - технологических САПР микроэлектроники. - Львов: ПО Полярон. 1995. - С. 53 - 54.

8. D.I. Batlahev. S.Ye. Vlasov, V.F. Morozov. CAD System for Flexible Chip Carries // 5-th International Synposlumon IS-RAKT* 95. - Kiev: SRI "Saturn".. 1995. - P. 57-59.