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

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

Бессонов Андрей Валерьевич

АЛГОРИТМЫ ЛОКАЛЬНОЙ ОПТИМИЗАЦИИ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ ПЕЧАТНОГО МОНТАЖА

Специальность: 05.13.12 - «Системы автоматизации проектирования (промышленность)»

Автореферат

диссертации на соискание ученой степени г г ш 2015 кандидата технических наук

005570801

Санкт-Петербург - 2015

005570801

Работа выполнена в федеральном государственном автономном образовательном учреждении высшего образования «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В. И. Ульянова (Ленина) (СПБГЭТУ «ЛЭТИ»), на кафедре САПР.

Научный руководитель:

кандидат технических наук, профессор Лячек Ю.Т., доцент кафедры САПР СПбГЭТУ «ЛЭТИ»

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

доктор технических наук, доцент Жаринов Игорь Олегович, руководитель учебно научного центра - ученый секретарь научно-технического совета ФГУП «Санкт-Петербургское опытно-конструкторское бюро «Электроавтоматика» имени П.А.Ефимова»

кандидат технических наук Балашов Вадим Владимирович, начальник отдела разработки и внедрения ИПИ-технологий ФГУП «Федеральный Научно-Производственный Центр «Научно-Исследовательский Институт Измерительных Систем имени Ю. Е. Седакова»

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

Открытое акционерное общество "Авангард", Санкт-Петербург.

Защита состоится 24 сентября 2015 года в 14— часов на заседании диссертационного совета по защите докторских и кандидатских диссертаций Д 212.238.02 при Санкт-Петербургском государственном электротехническом университете «ЛЭТИ» им В.И. Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, д. 5.

С диссертацией можно ознакомиться в библиотеке университета и на сайте http://eltech.ru.

Автореферат разослан 29 июня 2015 года.

Учёный секретарь

диссертационного совета Д 212.238.02

к.т.н., доцент

Сафьянников Н.М.

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

Актуальность исследования

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

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

Объектом исследования диссертационной работы является печатный монтаж радиоэлектронной и электронно-вычислительной аппаратуры.

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

Цели и задачи исследования

Цель работы - повышение эффективности автоматического размещения элементов топологии печатного монтажа.

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

1) анализ применяемых моделей и алгоритмов размещения элементов топологии печатного монтажа на печатных платах;

2) разработка методики кластеризации схемы электрической принципиальной;

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

4) разработка методики назначения межслойных переходов в области ВОА-компонентов;

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

6) разработка методики размещения точек ветвления проводников на основе динамического построения деревьев Штейнера;

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

Основные методы исследования

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

Новые научные результаты

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

1) предложена методика кластеризации схемы электрической принципиальной;

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

3) предложена методика размещения сквозных межслойных переходов в области ЕЮА-компонентов и назначения им цепей;

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

5) предложена методика оптимального размещения точек ветвления проводников на основе динамического построения деревьев Штейнера.

Научные положения, выносимые на защиту

1) Кластеризация схемы электрической принципиальной позволяет существенно повысить эффективность известных алгоритмов размещения компонентов.

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

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

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

Реализация результатов работы

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

Апробация работы

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

14-й международной НПК "Современные информационные и электронные технологии", г. Одесса, 2013г.;

13-й Международной конференции "САО/САМ/РОМ-2013", г. Москва, 2013г.;

15-й международной НПК "Современные информационные и электронные технологии", г. Одесса, 2014г.;

14-й Международной конференции "САО/САМ/РОМ-2014", г. Москва, 2014г.;

16-й международной НПК «Современные информационные и электронные технологии», г. Одесса, 2015 г.

Публикации

Основные теоретические и практические результаты диссертации опубликованы в 11 научных работах, из них - 6 статей в научно-технических журналах, рекомендованных действующим перечнем ВАК РФ, и 5 докладах в трудах международных конференций.

Структура и объем диссертации

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

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

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

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

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

Задача размещения обычно сводится к нахождению варианта отображения графа схемы б = (X, II) в решетку б> монтажного пространства, при котором минимизируется суммарная длина соединений

'<7

или суммарное число пересечений

где £/,, - расстояние между вершинами; - число ребер между

вершинами х„ х/, р(щ) - число пересечений ребра ии.

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

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

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

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

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

Л /I //

Рисунок 1 - Простая цепь и все варианты соединений контактов

Если каждая цепь представлена в модели схемы полным подграфом, то число избыточных соединений (¡\) равно:

Щ{п-1)

-(/1-1)

1

^ /=1

где щ — число контактов в многозвенной цепи.

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

Рисунок 2 - Многополюсники связаны не непосредственно, а через двухполюсники

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

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

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

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

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

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

Выделение подсхемы (кластера)

Для построения кластера будем распространять волну от источника к приёмникам.

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

Формирование следующего фронта.

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

Если новый фронт не пуст, сделать его текущим и перейти к формированию следующего фронта.

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

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

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

Окрестности каждого из многополюсников будем наращивать последовательно.

Некоторые правила:

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

• одноконтактный компонент (например, контрольная точка), по-

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

• двухполюсник, оба контакта которого соединены с многополюсником (или окрестностью многополюсника), принадлежит окрестности многополюсника;

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

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

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

Определение ширины каналов трассировки между соседними компонентами.

Даны два параллельных друг другу многоконтактных компонента, все контакты которых расположены на равных расстояниях друг от друга. Требуется расположить их на минимальном расстоянии, позволяющем произвести «поконтактную» разводку проводников между ними с учётом заданной ширины проводника ¿1 и минимального зазора

с12.

В случае ортогональной разводки (рисунок 4, а) минимальное расстояние подсчитывается легко: если число контактов равно 2Ы-1, то минимальное расстояние равно сумме N ширин проводников и N зазоров между ними. В случае трассировки в произвольных направлениях (рисунок 4, б) с дугами расчет не так прост.

§

Ц

I шщщиншпм 1

1111IIII11111111111II1111п

а) б)

Рисунок 4 — Канал между компонентами при ортогональной (а) и гибкой (б) топологической трассировке

Пусть (рисунок 5):

• А - расстояние между компонентами (считаем горизонтальными);

(0,0) - координаты самой левой точки О нижнего компонента; Р] — правая точка того контакта верхнего компонента, для которого отрезок С^ пересекает ровно у проложенных проводников (это у-й слева контакт). Координаты этой точки равны (А + у'В, К), где коэффициенты А (абсцисса тоски А) и В (шаг расстановки контактов верхнего компонента) ищутся из уравнений, которые можно получить, зная координаты правых точек любых двух контактов верхнего компонента; с! 1 - заданная ширина проводника;

с12 - величина минимально допустимого зазора между проводниками;

с13 - ширина контактов для верхнего компонента;

(14- зазор между соседними контактами верхнего компонента.

Рисунок 5 - К определению минимального расстояния между компонентами

|ОР;| =£У+С12(/-1) lOPj.il >с11(/+1) + с12/' |ОРк| > с1а(/- 1) + с!2(/-2)

|ОР;+1|2 - |ОР/> (<1, + + 1) + ЫУ- 1))

|ОР/ - |ОР^,|2 < (ё, + СЬ)(<1,(2/- 1) + с!2(2у - 3)) С другой стороны, по теореме Пифагора:

ЮР,

>11

! - ЮР,! = (А + В + /В)- + Г - (А + /Ву - /г = В(2А + (2у + 1)В)

|2 _ / а , Т>\2

|ОР/ - |ОРь,Г = (А + /В) + Л - (А - В + у В) - /Г = В(2А + (2у - 1)В)

Подставив полученные значения в соответствующие неравенства и сделав из двух неравенств одно двойное, получим:

В{В - 2А) - (Зй2 + ^ХЪ + й2)

2у<-

в^ - (сгх + а2у

< 2у + 2

или

В(_В-2А)~ (Зс12 + ^(с^ + с12)

в2 - (а! + й2у

Тогда минимальная ширина канала (/?) с учетом трассировки: Л = + - I))2 - (А + В)У,

где В = (13 + с14, А = 0.5(с11-с13)-с14-(М-1)(Л3 + с14-с11-<12),

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

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

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

Перепендикулярные шины: каждый переход располагается в «своей» горизонтали и в «своей» вертикали (рисунок 6, а). Для ликвидации нарушений применяется автоподвижка переходов (рисунок 6,6).

тмшшш нтж

•■Ж

а) б)

Рисунок 6 - Перпендикулярные шины до (а) и после (б) подвижки переходов

В случае параллельных шин (рисунок 7, а) направим все проводники левой группы под углом (примерно 45°) вправо-вверх, а правой - под таким же углом влево-вверх. Точки пересечения пар проводников, принадлежащих одной цепи, являются точками топологической расстановки переходов.

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

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

а) б) в)

Рисунок 7 - Параллельные шины

Расстановка межслойных переходов в области BGA-компонента

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

Рисунок 8 - BGA-компонент в топологической модели печатной платы

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

При трассировке области BGA в "ячейках" между контактами

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

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

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

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

Следует отметить, что для цепей земли/питания возможно назначение нескольких соседних контактов на один переход (ограничение должно задаваться пользователем). Однако это не всегда поможет.

Для разрешения конфликта возможны два направления: уменьшение числа контактов-претендентов и увеличение числа доступных ячеек.

Уменьшение числа контактов-претендентов

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

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

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

имели минимальный диаметр или примерно равное число контактов). По-видимому, важнее уменьшать размеры кластеров контактов ВОА, чем двухполюсников на противоположной стороне. Увеличение числа доступных ячеек

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

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

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

Рисунок 9 - Деревья Штейнера приналичии препятствий

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

Локальная оптимизация

Наличие угла, меньшего 120° (рисунки 10, а и 10, в), между парой сегментов, инцидентных одной вершине (терминальной или дополнительной), - признак локальной неоптимальности подсети. В этом случае следует добавить дополнительную вершину: пара сегментов заменяется на три сегмента, инцидентных дополнительной вершине (рисунки 10, б и 10, г). Положение дополнительных вершин

оптимизируется с использованием силового алгоритма (рисунки 10, в и 10, д).

Рисунок 10 - Перестроение локально неоптимальной сети

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

Если четырехконтактная сеть не минимальна (рисунок 11, а):

- выбрать пару "диагональных" (принадлежащих диагонали четырехугольника) терминальных либо виртуальных терминальных вершин;

- отрезок, соединяющий терминальную (виртуальную терминальную) вершину с ближней к ней добавленной вершиной, заменить отрезком, соединяющим терминальную (виртуальную терминальную) вершину с дальней добавленной (рисунок 11,6);

- положение дополнительных вершин оптимизировать с использованием силового алгоритма (рисунок 11, в).

ххи

а) б) в)

Рисунок 11 - Перестроение неминимального дерева Штейнера

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

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

САПР "ТороЯ" (от Торо1о§юа111ои1ег) - отечественная система проектирования печатных плат, включающая редактор топологии, средства автоматического размещения компонентов, средства гибкой

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

Окно управления автоматическим размещением приведено на рисунке 12. ___

Рисунок 12 - Окно управления автоматическим размещением в САПР "ТороИ."

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

Результаты приведены в таблице 1.

Для вариантов размещения "Ручное" и "ТороЯ" трассировка соединений осуществлялась средствами САПР "ТороЯ", для варианта "БрессН-а" - средствами САПР "Брессйа".

Таблица 1

Размещение Длина проводников, мм Число переходов

Ручное 4454 1

Бресйга 6853 74

ТороЯ 5.4 3526 0

ТороЯ 6.1 2922 (-17%) 0

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

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

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

2. Предложена методика кластеризации схемы электрической принципиальной.

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

4. Предложена методика назначения межслойных переходов в области BGA-компонентов.

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

6. Предложена методика размещения точек ветвления проводников на основе динамического построения деревьев Штейнера.

7. Разработаны и интегрированы в САПР «TopoR» программные средства локальной оптимизации размещения элементов печатного монтажа.

Список опубликованных работ по теме диссертации

Публикации в изданиях, рекомендованных ВАК России:

1. Бессонов A.B. Определение минимальной ширины канала между парой компонентов при топологической трассировке [Текст] / Бессонов A.B., Кноп К.А., Лячек Ю.Т., Попов Ю.И. // Известия СПбГЭТУ «ЛЭТИ». - 2013. -№ 10. - С.31-34

2. Бессонов A.B. Декомпозиция задачи размещения компонентов [Текст] / Бессонов A.B., Кноп К.А., Лячек Ю.Т. // Известия СПбГЭТУ «ЛЭТИ». - 2014. - № 1с. 11-15

3. Бессонов A.B. Динамическое построение деревьев Штейнера в САПР TopoR [Текст] / Бессонов A.B., Лузин С.Ю., Лячек Ю.Т., Попов С.И. // Известия СПбГЭТУ «ЛЭТИ». - 2014. - № 4. - С. 1922.

4. Бессонов A.B. Назначение межслойных переходов в области BGA-компонента [Текст] / Бессонов A.B., Кноп К.А., Лячек Ю.Т. // Известия СПбГЭТУ «ЛЭТИ». - 2014. - № 5. - С. 13-17.

5. Бессонов A.B. Определение относительного расположения переходных отверстий на группе проводников, пересекающихся в паре слоев [Текст] / Бессонов A.B., Кноп К.А., Лячек Ю.Т. // Известия СПбГЭТУ «ЛЭТИ». - 2014,- № ю. - С.21-25.

6. Бессонов A.B. Определение окрестностей многополюсника [Текст] / Бессонов A.B., Лузин С.Ю., Лячек Ю.Т. // Известия СПбГЭТУ «ЛЭТИ». - 2015. -№ 5. - С. 14-17.

Материалы международных научно-технических

конференций:

7. Бессонов A.B. Расчет минимального расстояния между парой многоконтактных компонентов [Текст] / Бессонов A.B., Кноп К.А., Попов Ю.И. // Труды 14-й международной НПК "Современные информационные и электронные технологии". Т.2. - Одесса. -

2013. -С.23-25.

8. Бессонов A.B. Позиционирование переходного отверстия в BGA-компоненте [Текст] / Бессонов A.B., Кноп К.А., Попов С.И., Попов Ю.И. // Труды Международной конференции "CAD/CAM/PDM-2013" / - М.: Институт проблем управления им. В.А. Трапезникова РАН,-2013.-С.137-139.

9. Бессонов A.B. Расстановка межслойных переходов в области BGA-компонента [Текст] / Бессонов A.B., Лузин С.Ю., Попов С.И. // Труды 15-й международной НПК "Современные информационные и электронные технологии". Т.2. - Одесса. -

2014. - С.46-47.

10. Бессонов A.B. Алгоритм расстановки переходных отверстий для соединения контактов двух групп [Текст] / Бессонов A.B., Кноп К.А. // Труды Международной конференции "CAD/CAM/PDM-2014" / - М.: Институт проблем управления им. В.А. Трапезникова РАН. - 2014. - С.171-173.

11. Бессонов A.B. Кластеризация схемы для автоматизированного размещения компонентов [Текст] / Бессонов A.B., Лузин С.Ю. // Труды 16-й международной НПК "Современные информационные и электронные технологии". Т.2. - Одесса. -

2015. - С.168-169.

Подписано в печать 26.06.15. Формат 60х84 1/16. Бумага офсетная. Печать цифровая. Печ. л. 1,0. Тираж 100 экз. Заказ 55. Отпечатано с готового оригинал макета в типографии Издательства СПбГЭТУ «ЛЭТИ» 197376, С. Петербург, ул. Проф. Попова, 5