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

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

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

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

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

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

Н.Новгород 1995

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

I-1

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

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

I_I

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

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

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

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

Ведущая организация:

Научно - исследовательский институт технологии и организации производства (г.Н.Новгород)

Защита состоится «_£_« июня 1995 г. в 151 часов на заседании диссертационного совета Д. 063.85.02 Нижегородского государственного технического университета по адресу: 603600, г.Нижний Новгород, ул.Минина. 24. НГТУ, корпус-/, аудитория

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

Автореферат разослан "М^" &пре.л9 1995 г.

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

Подп. к печ. 14.04.95. Формат бОхМ'/М'. Бумага писчая. Печать офсета Уч.-изд.л. 1.0. Тираж 70 экз. Заказ 98. Бесплатно. *

Лаборатория офсетной печати полиграфической базы НПГУ. 603022, Н. Новгород, просп. Гагарина, 1.

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

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

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

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

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

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

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

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

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

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

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

соединений;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ацродавдя.рзботн-

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

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

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

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

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

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

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

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

Публикации.

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

Структура и обьем работа.

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

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

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

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

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

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

7

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

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

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

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

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

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

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

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

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

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

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

- достижение минимального времени прохождения сигнала между ис в блоке мэа (3) :

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

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

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

- обеспечение хорошей ремонтнопригодности (6).

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

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

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

связей, при котором обеспечиваются наилучшие- показатели крите-

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

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

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

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

риев: 5 ализованных

I

I ), где о - число нере-- длина I соединения;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПРСПУСЮЬЕ СПОСОБНОСТИ РЕБЕР гсз(АВ), res (ВС), res (АС) УЧГГЬЕАЮТ ЧИСЛО ТРАСС. ПРОХОДШЩ ЮДУ ОСОБЬМ) ТОЧКАМИ ГРАШ:

res (AB) =2 ■ res (ВС) =3. res(AO=3.

EßiTOPA РЕСУРСОВ Ra. Re. Rc V41TbBADr Ч1СЛ0 ТРАСС, СПЕЩЦИХ ВВШЖ ГРАНИ ГА. Гд,-1. ГС.ГСГ2. Гв=Га,-1.

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

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

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

Для каждой вершины j ( ), соответствующей контак-

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

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

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

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

В п. 2.2. рассматриваются методы реализаций бесперекрестного леса соединений на основе геометрических методов. Задача трассировки ГПН формулируется следующим образом; в соответствии с указанны;« связям! Lt т L = -1 . выполняя' кснструкторско -технологические ограничения, соединить все iJ контактов кусочно-ломаными отрезками прямых таким образом. чтобы:

1) каждое построенное -соединение Lü имело минимальную длину Ii min ¿l, 1-4,m ;

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

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

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

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

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

трассировке, выбирается очередное соединение кандидат для прокладки. '

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

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

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

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

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

О). * '

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

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

1,'лЦ-г координаты контактов;

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

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

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

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

На очередном саге для каждой нереализованной связи I, ¿-^И! вычисляется значение по (9), для трассировки выбирается соединение, имеющее минимальную величину Т^Р^-Ь рь.

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

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

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

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

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

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

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

min S ;

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

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

-min (1-1*) . '

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

После построения соединения предпринимается попытка улучше- •. ния его конфигурации путем итерационной замены отрезков(ЦЬЧ) и {.1*4,1 + 2Л на(¿,1+2) . еели при этом отсутствуют пересечения с препятствиями и положительны значения ресурсов огибаемых вершин и пересекаемых ребер.

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

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

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

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

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

- ввод и верификацию исходных данных;

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

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

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

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

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

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

Первоначальный свод

Рвдаетиро-

ВОИИО

параметров

Моди<{икация управляем« параметров

АЯМЧУЛОН'

-Передача управлвкмя -Пзрвдача ааннкх

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

объект.

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

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

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

Под критерием оптимальности- реализации N связей в процессе трассировки принимается суммарная длина всех разведенных трасс: Q-^ti где Ь\. - длина проводников i- - ой связи.

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

Pi * % ftf-4 %

12 К М-Ч и

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

Мера приспособленности - значение обобщенного критерия оценки качества трассировки всех связей для конкретного значения генотипа Г(С1К):

JH(al){

± Q

G- й-Л-Q

S - число пересечений;

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

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

Особь О-к. с генотипом ГСсх.^^) и мерой приспособленности JU-(Q.kV эта печатная плата (ГШ), на которой проведена трассировка всех М связей в порядке, указанном генотипом ) .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

быстрой адаптации на базовые конструктивы и ■элементную базу, 100 - процентную реализации связей КПП - ПМ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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