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



МОСКОВСКИЙ УНИВЕРСИТЕТ им. М. В. ЛОМОНОСОВА Факультет нычнслителыюй математики н кибернетики ..... Кафедра системного программирования

• -.j

I Iii 111Uiix руке innen

- ■ —'

ГЛЯМЖА АЛДАС ЙОНО

ИССЛЕДОВАНИЕ \1 КТО ДОН Л11ТОМЛТ1ПШЧ)ВАННГО ПЛОТНОГО РАЗМЕЩЕНИЯ РАЗНОГАБАРИТНЫХ ЭЛЕКТРОННЫХ РАДИОЭЛЕМЕНТОВ

l.vU.I I математическое и программное обеспечение нычис iine ii.ni.ix машин, комплексов, систем и сетей

А В Т О IJ Ii Ф Ii F> А I'

диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА - 1994

Работа выполнен;» па кафедре системного ирм (т(мм1 ■)«<ii.iiш)| факультета вичнслшелыюй математики и кибернетики М• •«■ I»«»шч;«л и государственного у инверсию га имени М.В.Ломонигииа.

Науише руководители: доктор филнео-математн'и'.-ки.ч наук,

профессор Э.З.Любнмскнп кпплплпт филнко-матемапне( кн\ наук. доцент А. Ю. М нталхю) 1."и

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

доктор фнлпко-математпчеекнх наук профессор А. 11. Гоми лип

кандидат технических наук' В. II .Сулханов

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

I¡петитут Системногг* П рограммирования I 'А 11

Защита состоится "46" с^кс^с^З1 1 994 года 11 41 часов н; заседании Специализированного совета Д.053.05.38 по математике нр! Московском государственного университете им, Ni.il. Ломоносова ш адресу: 119899, Москва, Ленинские горы, МГУ. факулые вычислительной математики и кибернетики, аудитория

С диссертацией можно ознакомиться в библиотеке факультет; вычислительной математики и кибернетики МГУ.

у.

Автореферат разослан иС^СУр _ 199^ года,

Ученый секретарь Специализированного совета профессор г^Ц^

li.il.Трифонов

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

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

Актуальность темы. Автоматизация процесса проектирования радиоэлектронной аппаратуры (РЭА) и вычислительной техники (ВТ) является составной частью перспективной концепции автоматизации всего цикла производства - CAD / CAE / САМ (Computer Aided Design / Engineering / Manufacturing). При ручном проектировании платы средней сложности, проект создается в течении одной-двух недель, однако объемы данных, которыми приходится оперировать в процессе проектирования более сложной РЭА, резко увеличивают трудозатраты проектирования, порой до такой степени, что ручное проектирование становится практически неприемлемым. Автоматизация проектирования на низком уровне (применение специализированных графических редакторов, автоматизация элементарных одношаговых действий) сокращает время разработки проекта, но объемы и требуемые темпы разработки проектов могут быть достигнуты лишь автоматизацией ряда этапов, относящихся непосредственно к проектированию топологии РЭА и ВТ.

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

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

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

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

2. Предложен ряд экспериментально подтвержденных критериев оценки последовательности размещения, непосредственно влияющих на качество размещения ЭРЭ.

3. Разработана техника оптимизации последовательности размещения на основе оценки связей ЭРЭ.

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

5. На основе выполненных исследований создана система (комплекс программ) размещения ЭРЭ на печатной плате. Система интегрирована в промышленную САПР печатных плат P-CAD с целью повышения качества размещения и упрощения его проведения по отношению к модулю размещения PC-PLACE системы P-CAD.

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

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

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

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

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

На основе разработанных методов созданный комплекс программ размещения разногабаритных ЭРЭ был внедрен на Каунасском научно-исследовательском институте средств телевидения "Банга" и на Александровском научно исследовательском институте телевизионной техники "Рекорд" в 1993 году. Система размещения элементов интегрирована в состав промышленной САПР печатных плат P-CAD с целью расширения ее функциональных возможностей.

Апробация л публикации, По теме диссертации опубликовано 9 работ. Материалы диссертации докладывались на заседании кафедры системного программирования факультета ВМК МГУ (1993 г.) и на научном семинаре кафедры Информатики математического факультета Вильнюсского Университета. Результаты работы докладывались на XXIX, XXX, XXXI и XXXIII конференциях Литовского математического общества в 1988, 1989, 1990 и 1992 г.г., на республиканской конференции "Программное обеспечение ЭВМ" в 1989 г., на всесоюзная научно-технической конференции "Проектирование вычислительных средств" в 1989 г., на международной конференции "Design Automation Conference АРК'92" (Каунас, Литовская республика) в 1992 г.

Структура м объем диссертационной работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложений. Основной (без приложений) текст занимает 92 машинописных страниц.

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

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

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

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

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

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

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

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

В § 1 анализируются конструктивные методы размещения наращиванием (елением. Показаны недостатки методов размещения делением: частично 1 полностью игнорируются цепи, не принадлежащие делимым блокам, на )вых шагах методов принимаемые решения, определяющие последующие |ения, являются заведомо неточными, но впоследствии не корректируются. ;вязи с этим более подробно рассматриваются последовательные методы ¡мещения наращиванием. Далее в § 1 рассматривается тактика выбора ¡метаемого элемента и позиции для него. Так как невозможно достаточно

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

В Й 2 определяются критерии оценки последовательности размещения ЭРЭ и рассматриваются методы ее построения. Допустим, что на плате есть N цепей и М элементов. Обозначим через С1 модель цепи I в последовательности - отрезок последовательности размещения ЭРЭ, лежащий между парой наиболее удаленных друг от друга в последовательности элементов, принадлежащих цепи ¡. Длину О (количество ЭРЭ в СО обозначим через ЛСк Через Р] обозначим плотность цепей при размещении ]-того элемента. Р] равно числу всех СК ¡=1^ , которым принадлежит элемент Используя введенные обозначения, определяются критерии оценки последовательности :

1.]ГсЮ , 1 = 2.]ГРь 3. тах^),

' J

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

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

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

-У-

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

I. ]Г\У1ч , ] = 1,М 2. тах(\У1у), \ -•1,М

I

Во время конструирования последовательности, цепи платы делятся на (есколько типов по отношению к добавляемому элементу. Цепи, все »лементы которых уже находятся в последовательности, будем называть ¡акрытыми. Те цепи, которые становятся закрытыми при добавлении очередного элемента, определим как закрываемые. Открываемыми цепями >удем считать те цепи добавляемого элемента, которым не принадлежит ни >дин из элементов последовательности. Цепи, которым принадлежат как лементы последовательности, так и пока не находящиеся в последовательности ЭРЭ, определим как открытые. Неиспользованными епями будем считать цепи, все элементы которых пока не принадлежат оследовательности.

Определяя последовательность элементов целью ставится минимизация ышеупомянутых трех критериев оценки последовательности. На очередном шге построения последовательности элементы, все цепи которых открыты, рибавляются к очередности. Если из оставшихся ЭРЭ не находится таких цементов, то кандидат определяется минимизируя число элементом гкрываемых (дотоле неиспользованных) цепей. Пусть О] - число открытых епей для ]-того ЭРЭ, - открываемых, а Zj - число закрываемых цепей на гом шаге из числа открытых. Чем больше соотношение (Oj+aZj)/Nj, (а>0) ;м лучше элемент] минимизирует критерии последовательности.

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

ОС=£(Кл , ¡ = 1,М; ОР=£Р) , ]= 1,М,

МР= тах(Р)), }= 1,М; йХР = £{Р>3-ЙР/М] , |,М, РК=ОС+ОР+МР+ОХР.

Критерий Г;К обладает всеми свойствами критериев, определенных в § 2 и включает сглаживающее выражение ОХР. Выбор перестанавливаемых ЭРЭ производится произвольно, но каждый ЭРЭ должен принадлежать концу хотя бы одного отрезка О. При проведении экспериментальных исследований значение критерия РК уменьшалось на 5-40%.

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

Пусть 0| - расстояние от позиции размещаемого элемента до минимального прямоугольника, покрывающего размещенные элементы, входящие в цепь ¡, а с1С) - число элементов в цепи ¡. Из последовательности размещения ЭРЭ выделим § элементов (прогнозирующую группу), непосредственно следующих за размещаемым ЭРЭ. Обозначим размещаемый элемент Е(), первый ЭРЭ прогнозирующей группы Е| и так далее до последнего элемента группы Е£. При размещении элемента Е() цепи платы взвешиваются по их отнощению к размещаемому элементу и прогнозирующей группе. Пусть 5 - подмножество цепей платы, которым принадлежит не менее одного элемента Е^, к=0,ц. Через <21к определим признак принадаежания элемента Е^ цепи через VI - вес рассматриваемой цепи к

Определим локальный критерий размещения, минимизируемый функционал:

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

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

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

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

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

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

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

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

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

Поиск ЭРЭ-кандидата проводится в зоне поиска на РДС. Возможны три ситуации:

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

б) В рассматриваемой зоне найден единственный пока неразмещенный ЭРЭ. Тогда делается попытка разместить его в позиции. Если размеры

позицни недостаточны для размещения ЭРЭ, позиция прикрывается контуром целиком;

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

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

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

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

В § 1 рассматривается состав системы размещения разногабаритных элементов, названной VUPLACE. Модуль интеграции предназначен дня согласования работы модулей, осуществляющих отдельные этапы процесса размещения, определению режима и языка вывода сообщений пользователю, конфигурации режимов проведения размещения. Модуль также контролирует наличие и формат задаваемой пользователем информации. Модули ввода и вывода данных в символьном формате PDIF (P-CAD Data Interchange Format) обеспечивают связь системы VUPLACE с промышленной САПР печатных плат P-CAD. При вводе ведется контроль корректности начальных данных, так как проект ПП в системе P-CAD может быть недостаточно подготовлен к проведению размещения. Модуль начального размещения проводит размещение ЭРЭ на РДС и итеративное улучшение начального размещения. Предусмотрена возможность в качестве начального размещения использовать данные, полученные другим путем. Модуль разногабаритного переразмещения отображает начальное размещение на ПП, при этом соблюдая технологические требования. В этот модуль входят подмодули диалога с пользователем и визуализации процесса размещения.

Система реализована в системе программирования Turbo Pascal 7.0, дня использования в среде операционной системы MS-DOS IBM PC совместимых персональных компьютеров.

§ 2 состоит из описания интерфейса системы VUPLACE с промышленной САПР печатных плат P-CAD и интерфейса пользователя.

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

VUPLACE создавалась как автоматическая система размещения ЭРЭ, поэтому диалог с пользователем сведен к минимуму. В системе предусмотрена графическая визуализация процесса размещения на ПП,

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

В § 3 рассмотрено несколько более характерных структур данных, использованных при разработке системы размещения.

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

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

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

Кроме того, в системе применяется модель РДС, которая позволяет, в совместном рассмотрении с координатами ЭРЭ, быстро вычислить оценку

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

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

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

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

Основные результаты опубликованы в работах:

1. Глямжа А., Миташюнас А., Рагайшис С. Крепление гибких трасс в автоматизированном проектировании односторонних печатных плат. XXIX конференция Литовского математического общества. Тезисы докладов, Вильнюс, 1988, с. 201-202 (на литовском языке).

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

3. Глямжа А., Миташюнас А., Рагайшис С. Плотное размещение разногабаритных радиоэлементов на печатной плате. XXX конференция Литовского математического общества. Тезисы докладов, Вильнюс, 1989, с. 219 (на литовском языке).

4. Глямжа А., Миташюнас А., Рагайшис С. Плотное размещение разногабаритных элементов. Всесоюзная научно-техническая конференция "Проектирование вычислительных средств". Тезисы докладов, Каунас, 1989, с. 210-211.

5. Глямжа А., Янкаускас Р., Майсеюс А., Миташюнас А., Рагайшис С., Жагунас И. Особенности реализации размещения разногабаритных элементов на печатной плате. XXX конференция Литовского математического общества. Тезисы докладов, Вильнюс, 1989, с. 235 (на литовском языке).

6. Глямжа А., Методы размещения разногабаритных радиоэлементов. XXXI конференция Литовского математического общества. Тезисы докладов, Вильнюс, 1990, с. 146 (на литовском языке).

7. Глямжа А., Миташюнас А., Рагинис А. Минимизация переходных отверстий на печатной плате. XXXI конференция Литовского математического общества. Тезисы докладов, Вильнюс, 1990, с. 147 (на литовском языке).

8. Глямжа А., Метод плотного размещения разногабаритных элементов используя предварительную оценку распределения цепей. ХХХШ конференция Литовского математического общества. Тезисы докладов, Вильнюс, 1992, с. 52 (на литовском языке).

9. A. Glemza, Method of various size component placing using forward net layout estimation. Design Automation Conference APK'92. Proceedings, Kaunas, 1992, c. 73-75.