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

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

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

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

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

28 ОКТ 2015

Автореферат диссертации на соискание ученой степени кандидата технических наук

005563902

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

005563902

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

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

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

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

доктор технических наук, профессор Коробейников Анатолий Григорьевич, заместителя директора по науке Санкт-Петербургского филиала федерального государственного учреждения науки "Институт земного магнетизма, ионосферы и распространения радиоволн им. Н.В. Пушкова" Российской академии наук (СПбФ ИЗМИРАИ)

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

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

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

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

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

Автореферат разослан 12 октября 2015 года.

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

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

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

(^¿0 ¿_ Сафьянников Н.М.

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

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

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

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

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

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

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

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

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

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, Ц) в решетку Сг, чтобы, например, суммарная длина

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

«)

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

кратных ребер между вершинами х„ х,), р(и,у) — число пересечений ребра "у-

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

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

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

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

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

Л

Ц

I

/з

Л

Ч 1

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

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

1=1

И, (И- 1)

(п-1)

1

^ 1=1

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

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

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

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

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

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

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

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

Рисунок 3 - Сигнальный кластер

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В случае ортогональной разводки (рисунок 4, а) минимальное

расстояние подсчигывается легко: если число контактов равно 2М.......1, то

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

щшшшшшшш

[ШТТШТЩШТШТЩ

а) б)

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

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

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

• (0,0) - координаты самой левой точки О нижнего компонента;

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

• <11 - заданная ширина проводника;

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

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

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

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

|0Р)| =<ц+ <Ы/-1)

|ОРК1| >с11(/ + 1) + с)2/'

|0РН| >^(/'-1) + с12(у'-2)

|0Р;+1|2 - |0Р/> ((1, + сЬ)(с1,(2/ + 1) + Ъ(2] - 1)) |ОР/ - |0РН|2 < (с!, + сЬ)(с1|(2/ - 1) + - 3))

С другой стороны, по теореме Пифагора:

|0Р;+,|2 - |0Р/ = (А + В + уВ)2 + к2 - (А + УВ)2 - Л2 = В(2А + (2/ + 1)В) |0Р/ - |ОРн12 = (А + ]В)2 + А2 - (А - В +/В)2 - Л2 = В(2А + (2/ - 1 )В)

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

В(В - 2А) - (Зй2 + ¿Жс^ + й2~)

2; <■

в2 - № + й2у

<2) + 2

или

} ~ [°-5 В2 _ № + а2у

Тогда минимальная ширина канала (й) с учетом трассировки:

Л = ^кТ + ^а^!))2 - (Л + В}У, где В =с13+ й4, А = 0.5(с11 -(!)- с14 - (М - 1) (с1} +с14-с1,- (1),

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

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

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

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

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

4 I ^.....

[? Н Л\

[ Гп О

1 .- ■■ 1 Дет! 1 * * ■ X 1 • £ Я О 1 1 . & Л я % V / Я и я ! ■й - 1 I А\Р I

1 "ЧУ* " 1

1 111Ш11 V'"""'1...... ч Шщ Щ I у О 1 I

а) б)

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

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

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

\

Т I . •

% Лив«*« 1

ж/;-'

-V I» , '• |

а)

б) в)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

а) б)

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

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

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

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

ппнн

а) б) в) г) д)

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

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

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

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

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

- положение дополнительных вершин оптимизировать с

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

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

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

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

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

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

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

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

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

Таблица 1

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

Ручное 4454 1

Бресс^а 6853 74

ТороЯ 5.4 3526 0

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

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

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

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

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

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

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

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,- № 10. - С.21-25.

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

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

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

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.

Подписано в печать 12.10.15. Формат 60x84 1/16. Бумага офсетная. Печать цифровая. Печ. л. 1,0. Тираж 100 экз. Заказ 86. Отпечатано с готового оригинал-макета в типографии Издательства СПбГЭТУ «ЛЭТИ» 197376, С.-Петербург, ул. Проф. Попова, 5 тел.: (812) 346-28-56