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

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

Пегросян Геворг Самвелович

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Сап К1-Петербург -2005

к

Работа выполнена в Санкт-Петербургском государственном университете телекоммуникации им. проф. М.Л. Бонч-Бруевича.

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

доктор технических наук, профессор Лузин С.Ю.

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

доктор технических наук, профессор Дмитревич Г.Д.

кандидат технических наук, старший научный сотрудник Семеновых В.В.

Ведущая организация - Федеральное государственное унитарное предприятие ЦНИИ "Морфизприбор".

Защита диссертации состоится " 2?" ^йДй^и 2005 года в часов на

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

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

Авюреферат разослан "25? kCé&pa. 2005 года.

Учёный секретарь диссерт анионного сове i а

Юрков Ю.В.

мшьь

¿(З/Г

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

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

Ещё в 70-х годах прошлого столетия в качестве альтернативы сеточным методам был предложен метод гибкой топологической трассировки (в более поздних зарубежных публикациях - river routing). Однако в рамках топологического подхода рассматривался только ситез пленарных укладок графа схемы, то есть последовательная укладка на плоскости фрагментов графа без пересечений. Предполагается, что до этого уже решена весьма непростая задача распределения соединений по слоям. Поскольку существующие методы решения задачи плана-ризации не позволяют учесть в полной мере конструктивно-технологические oi-раничения, а также осуществлять оптимизацию полученных решений, подход не получил широкого распространения в промышленных САПР.

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

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

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

новлять процесс ошимизации разводки соединении по

.:^^ёДакт1форатгяг1М|ак'-

Ь'

А

С .

о у и

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

Достижение указанной цели предполагает решение следующих основных задач'

1) Анализ применяемых моделей и алгоритмов трассировки соединений )злов Р'-)С на печатных платах и микросборках;

2) Разработка моделей печатного монтажа, позволяющих эффективно решать задачи оптимизации и редактирования топологии печатного монтажа в системе I покой тополо1 ической трассировки;

3) Разработка алгоритмов синтеза топологической модели печатного монтажа по данным геомефической модели и алгоритмов синтеза Iеометрической модели по данным топологической модели;

4) Разработка метдов локальной коррекции юнологии печатного мон!ажа; Разработка методики отбора вариантов при оптимизации разводки соединений,

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

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

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

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

2) Разработаны алгоритмы синтеза топологической модели печатного монтажа по данным (еометрической модели и синтеза геометрической модели по данным юпо.югической;

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

На шщиту выносятся следующие положения:

1) I (редложенпые топологическая и геометрическая модели печатного монтажа

2) Предложенные алгоритмы синтеза моделей позволяют синтезировать юполо-гическлю модель по данным геометрической, и геометрическую по данным то-1Ю.Ю1 ической.

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

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

программные средства входят в состав САПР "TopoR". Применение разработанных средств обеспечивает существенное сокращение сроков проектирования печатных \ í.ioB РОС. повышение надёжности, улучшение качества, снижение ) ровня перекрёстных электромагнитных помех.

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

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

- III научно-практической конференции "Современные информационные и электронные технологии", г. Одесса, 2002г.;

- VI международной научно-практической конференции "Сис1емы и средства передачи и обработки информации", г. Одесса, 2002г.;

- 9-й международной конференции "Современные технологии обучения", С.-Петербург, 2003 г.;

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

- VII международной научно-практичсской конференции "Сис1емы и средства передачи и обработки информации", i. Одесса, 2003г.;

- Международной научно-технической конференции ИПИ(САЦ5)-2003 "Информационные технологии в управлении жизненным циклом изделий", С -Петербург, 2003г.;

- Всероссийской научно-практической конференции "Информационные технологии в российской промышленности", С.-Пс(ербург, 2004 i.;

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

- III международном симпозиуме "Аэрокосмические приборные техноло-I ни". С.-Петербург, 2004 г.;

- Международной научно-практической конференции "Фундаментальные и прикладные проблемы приборостроения", Сочи, 2004 г.;

- VIII международной научно-практической конференции "Системы и средства передачи и обработки информации", Одесса, 2004 г.;

- 6-й международной НПК "Современные информационные и электронные lexHo.nornn", Одесса. 2005 г.

Публикации По теме диссертации опубликовано 22 на}чные работы, ш них - 1 авторское свидетельство, I статья и тезисы к 20-ти докладам на меж-т\ народных научно-технических конференциях.

Структура и объем диссертации. Диссертационная работа cociohi из введения. пят глав, заключения, списка литерап'ры. включающею I 10 наименований. и одного приложения. Основная часть работы изложена на 93 страницах машинописного текста. Paöoia содержит 40 рисунков и 1 таблиц)

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

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

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

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

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

В качестве альтернативного подхода к решению задачи разводки соединений в 70-х годах прошлого века рядом советских ученных (Р.II. Базилевич, Л.Я. Те-тельбаум, В.А. Селютин) был предложен топологический подход к трассировке. Суть подхода состоит в последовательном снижении неопределённости положения трасс. Рабочее поле разбивается на выпуклые многоугольные области, в углах которых находятся контакты (рис. 1). Трассы назначаются в эти области, внутри которых их положение не конкретизируется. Модель была названа дне-кретпым топологическим рабочим полем, а метод - методом гибкой трассировки. Преимущество метода, прежде всего в том, что он позволяет резко снизить размерность задачи разводки соединений за счёт сокращения пространства решений. так что появляется возможность говорить даже о поиске точного решения за приемлемое время. Кроме того, топологическая трассировка изотропна, то есть не имеет никаких выделенных направлений, проводники идут так, как им ближе.

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

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

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

Топологическая модель коммутационного пространства основывается на триангуляции Делоне рабочего поля. Триангуляция Делоне - эго такое разбиение плоскости на феуюльные грани, что окружность, описанная вокру1 любой фани не содержит внутри себя вершин других граней. Триангуляция Делоне может бьпь получена из любой другой триангуляции с помощью последовательности так называемых фитов Флипом ребра называется замена этого ребра на ребро, соединяющее противолежащие вершины инцидентных этому ребру граней. Триангуляция Делоне обладает многими полезными свойствами, в том числе, и тем свойством, чго любая вершина триангуляции всегда соединена ребром с ближайшей к ней вершиной. А это позволяет использовать такую структуру для быстрою определения рассюяиия между вершиной и ближайшими к ней вершинами. причём, узнать точную величину зтого расстояния, а не только ответить на вопрос "11е меньше ли это расстояние, чем заданная величина Н''". Вершинами фиашуляшш выступают контакты и барьеры. Круглые контакты представляются одной вершиной, некруглые - несколькими. 1 опологическая модель печатного моиIала является совмещённой топологией В качестве вершин триашуляции

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

1\ сожалению, для протяжённых объектов, например ламелей, все преимущества триангуляции Делоне обесцениваются тем простым фактом, что вершины |риангу1яции - точки, а не офезкн. Эю ифудняет её применение на практике. Поэтмч для решения задачи метризации используется структура разбиения птоскосш, предложенная О.Б Полубасовым. Данная сфуктура обладает свойствами фиангуляцин Делоне, но сё вершинами выступают не точки, а произвольно наклонённые отрезки. Строго говоря, это разбиение не является триангуляцией в i еометрическом смысле, то есть разбиением плоскости на треугольные грани, но вполне являе1ся фиангуляцией в топологическом смысле. Принцип построения структуры основан на (мысленной) замене каждого отрезка топологии на множе-ciBO тесно (в пределе - бесконечно близко) расположенных точек и построения для всех этих ючек триангуляции Делоне. Показаны преимущества использования квапприангуляции на Э1апе ручного редактирования, когда необходим ме i -рнческий контроль проводников. В отличие от модели совмещённой топологии, в геометрической модели печажого монтажа для каждого слоя строится своя квазитриангуляция, поэтому модель называется послойной топологией. Это по-зволяе: эффективно рассчитывать оптимальную геометрическую форму проводников о >.дельно на каждом слое.

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

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

Upoóicuu спите и: геометрической модечч печатного монтажа по данным юпологической модели заключается в определении геометрии проводников и месюпо'южения межслойных переходов. При этом не ставится задача получения проводников минимальной длины, то есть представления проводника отрезками и дчгами. uiK как 3ia задача хорошо решается на геометрическом этапе. Для оп-рететения координат проводника достаточно вычислить координаты его пересечений с рёбрами и с другими проводниками. Предложен способ визуализации юпологической трассировки. Сформулированы основные задачи синтеза

1 Расчсч i еометричсской формы проводников.

2 Определение положения межслойных переходов

3 Бо iee равномерное распределение межслойных переходов.

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

совмещённой топологии, деление проводника и подразбиение ребра вершиной для избежания флипа этого ребра.

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

Алгоритм прокладки ребра <АО> в грани <АВС> (рис. 2).

1 Включить в начальный фронт волны хвосты между дугами <АС> и <АВ>, а также хвост дут и <АС>.

2 Распространять волну, пока не достигнута целевая вершина <0>:

• Для каждого узла текущего фрон [а

• Перейти к хвосту по часовой стрелке

• Добавить узел к новому фронту

• 11ока не достигнут хвост узла или не достигнута вершина <0>

о Найти смежный хвост о Перейти к хвосту по часовой стрелке

о Бели хвоста и смежного с ним хвоста не было в предыдущих фронтах, и это не хвост дуги, то добавить узел к новому фронту,

• Перейти к новому фронту.

3. Расставить кресты.

• Для каждою узла найденного пути

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

4. Сформировать циклы хвостов вокруг вершин <0> и <А>( хвост, по которому была достигнута вершина <0>, является предыдущим для дуги <ОА>. Хвост дуги <АС>. который является родительским для узла, откуда была достигнута вершина <0>. - предыдущий хвост для дуги <А0>).

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

Рис. 2. Прокладки ребра АО.

а) Стрелками отмечены хвосты, принимающие участие в распространении волны, серым цветом отмечены узлы волны, цифра рядом с узлом означает номер фронта. Пунктиром обозначен найденный путь, на нём показаны хвосты одного из крестов \¥А на новом ребре.

6) Топология после прокладки ребра.

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

когда одно из таких рёбер не удовлетворяет круговому критерию триангуляции Делоне, и необходим флил этого ребра, для избежания этого флипа на ребре добавляется новая вершина. Эта вершина делит ребро на два таким образом, что ни одному из двух рёбер флил не нужен.

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

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

Задачи синтеза топологической модели.

1. Построение триангуляции, вершины которой расположены на контактах и барьерах.

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

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

4. Обнаружение и разрыв циклов в цепях.

5. Прокладка недотрассированных связей.

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

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

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

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

Алгоритм определения топологического пути проводника.

1 Определить текущую грань (это грань, в которую выходит проводник из

вершины)

2 Для каждого отрезка проводника

о Для каждого ребра грани

■ Если ребро пересекается с отрезком

• Рели это последнее пересечённое проводником ребро

о удалить ребро из пути, о перейти к проверке предыдущей грани.

• иначе

о Если это ребро, представляющее контакт цепи проводника

■ перейти к пункту 3. о Добавить пересечённое ребро в путь, о Перейти в грань, смежную с пересечённым ребром.

3 Удалит ь из пути дуги, инцидентные концам проводника.

Алгоршм имеет сложность 0(п + т), где п - количество изломов проводника. т - количество пересечённых проводником граней триангуляции.

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

Алгоритм удаления вершин, представляющих точки ветвления проводников и мсжслоиные переходы.

• Для каждой добавленной вершимы, начиная с последней

1) Взять очередное ребро из стека флипов для текущей вершины

2) Выполнить флип ребра.

Если стек не пуст, перейти к пункту I.

4) Гели вершина - точка ветвления или межслойный переход • Определить степень вершины.

• Если степень больше двух, io добавить точку ветвления STAR

Иначе объединить два проводника.

• Удали гь вершину и з триангуляции.

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

В среднем, сложность алгоритма удаления вершины - О(п), где п - кошче-ciBo кресюв WW в mhoi oyi ольнике, образованном вершинами, смежными с удаляемой

Четвёртая г.ииш посвящена вопросам оптимизации юпологии печатного монтажа. Предложена методика отбора вариантов при mhoiокритериальной оптимизации и процедуры локальной коррекции топологии печатного монтажа, используемые в CAI IP "TopoR".

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

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

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

- в процессе трассировки осуществляется переназначение функционально эквивалентных контактов;

- каждый найденный вариант топологии оценивается но совокупности параметров (суммарная длина проводников, число переходных ошерешй, число нарушений, число сужений проводников, число пересечений на совмещенной юпологии и i .д.);

- реализована методика о i бора вариантов при mhoi окритериальной оптимизации

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

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

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

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

Предложены процедуры локальной коррекции топологии печатного монтажа. Существуют ситуации, в которых обычная последовательная перекладка проводников оказывается беспомощной. К таким ситуациям относится «клинч» проводников (рис. 4), когда перекладка любого из двух неоптимально проложенных проводников не приведёт к улучшению из-за того, что они мешают друг другу.

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

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

Рис.3. Варианты, оптимальные для всевозможных ко ¡ффициенпнм ин-тегрсиьного функционала от двух оцениваемых параметров

Рис. 4. «Клинч» двух проводников

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

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

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

Описываются средства и способы отладки разработанных алгоритмов, приведён пример отладки.

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

Табтца 1. Сравнение резутыпапюв проектирования.

ИРИМЬР 1 ПРИМ! Р 2 ПРИМРР 3 ПРИМГР 4

1ороК ре л» ТориЯ Ргою1 ОХР 1 ороИ Я|ххс1и ТороЯ Ро\\ег РСВ

Цечп 2И золч 54 X 243 2<зхх 1094 1 131 Ч70Х 891 471 4040

Коммомешы Котики.!

11ерс\о 1ы ХМ) 1 1 14 2014 2832 3932 1800 .3301

С юп 4 13 2 X 4 4 4 4

Д ммм ЗГ>М1 60м1 47т 4Хт 73т 86т 83т 97т

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

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

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

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

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

^ Р.ирабо1аны алгоритмы синтеза топологической модели печатного монтажа по тайным геометрической модели и синтеза I еометричсской модели по данным топочо! ической

4 Разрабошна методика отбора вариантов при многокритериальной оптимизации развозки соединений, показано преимущество этой методики по сравнению с

традиционным подходом.

5. Разработана и интегрирована в САПР "TopoR" система отладки работы алгоритмов. включающая пошаговую отладку с визуализацией.

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

По материалам диссертации опубликованы следующие работы.

1. Петросян Г.С. и др. Система автоматизированного проектирования FrecStyle 2.0. // Труды второй международной научно-практической конференции "Современные информационные и электронные технологии". - Одесса. - 2001. -С.210.

2. Петросян Г.С. и др. Интегрированная система автоматизированного проектирования "FreeSlyle EDA" II Труды V международной научно-практической конференции "Системы и средства передачи и обработки информации". -Одесса. - 2001.-С. 105-106.

3 Петросян Г.С., Зудин C.B. Интегрированная САПР печатных плат. // 8-я международная научно-техническая конференция студентов и аспирантов "Радиоэлектроника, электротехника и энергетика". Тезисы докладов - Т. 1. - Москва -2002. - С.76-77

4. Петросян Г.С. и др. Учебная САПР тонкопленочных микросборок // Материалы 9-й международной конференции "Современные технологии обучения" - С.-Петербург.-2003.-T. 1.-С. 196-197.

5 Петросян Г С., Полубасов О.Б. Интеграция процессов оптимизации и редактирования топологии. // Труды 4-й международной научно-практической конференции "Современные информационные и электронные технологии". - Одесса. - 2003. - С.208.

6 Петросян Г.С., Соколов В.Е., Лузин С.Ю. Декомпозиция задачи выделения в графе наибольшего полного подграфа. // Труды 4-й международной научно-практической конференции "Современные информационные и электронные технологии". - Одесса. - 2003. - С.212.

7 Петросян Г.С. и др. TopoR - система автоматизированной трассировки печатных плат. // Труды VII международной научно-практической конференции "Системы и средства передачи и обработки информации". - Одесса. - 2003. -С. 137.

8 Петросян Г.С. и др Система топологической трассировки печатных плат. // Труды международной научно-технической конференции ИПИ(СА1.5)-20()3 "Информационные технологии в управлении жизненным циклом изделий" -С -Петербург. - 2003 - С.38.

9 Петросян Г.С. и др Интегрированная САПР юнкопленочных гибридных митральных схем "Авангард". // Труды международной научно-технической

конференции ИПИ(САЦ5)-2003 "Информационные технологии в управлении жизненным циклом изделий". С.-Петербург. - 2003, с.39-40.

10 Пе1 росян ГС и др Автоматизация синтеза топологии печатного монтажа. // Груды 5-й международной НПК "Современные информационные и электронные технологии". - Одесса. - 2004. - С. 166.

11 Пет росян Г.С.. Дюдин М.В.. Полубасов О.Б. Использование функциональной эквивалентности на этапе пробной трассировки. // Труды 5-й международной 11ПК "Современные информационные и электронные технологии". - Одесса. -2004. - С. 164.

12 Петросян ГС и др. Преимущества неортогональной топологии печатного монтажа // I руды 5-й международной 11ПК "Современные информационные и электронные технологии". - Одесса. - 2004. - С. 167.

Н Петросян ГС и др. Обеспечение электромагнитной совместимости на этапе размещения компонентов. // Труды 5-й международной НПК "Современные информационные и электронные технологии". - Одесса. - 2004. - С. 163.

14 Петросян Г.С и др. Система автоматизации синтеза топологии печатного монтажа. // I руды Всероссийской научно-практической конференции "Информационные технологии в российской промышленности". - С.-Петербург. - 2004. - С.91-92.

15 Петросян Г.С Воротынцев В.Ю., Лузин М.С., К оценке качес1ва топологии печатного монтажа // Груды III международного симпозиума "Аэрокосмические приборные технологии". - С.-Петербург. - 2004. - С. 175.

16 Петросян I С Воротынцев В.Ю.. Лузин М.С . Пути повышении плотности печатного монтажа. // Труды Международной научно-практической конференции "Фундаментальные и прикладные проблемы приборостроения" - Сочи. -2004 - С. 29-30

17 Петросян ГС. и др. Обеспечение заданного качества топологии печатного монтажа // Труды VIII международной научно-практической конференции "Системы и средства передачи и обработки информации". - Одесса. - 2004. -С. 119-120.

18 Петросян Г.С и др. Способ повышения плотности печатного монтажа. И Груды VIII международной научно-практической конференции "Системы и сред-с i ва передачи и обработки информации". - Одесса. - 2004 - С. 123-124.

19 Петросян ГС и др. Контроль констуктивно-технологических нарушений в системе TopoR // Труды 6-й международной НПК "Современные информационные и электронные технологии" - Одесса. - 2005. - С.212.

20 Петросян ГС, Полубасов О.Б. Многовариантная оптимизация разводки соединений // Труды 6-й международной ППК "Современные информационные и электронные технологии" - Одесса. - 2005. - С.211.

21 Петросян ГС и др Система топологической трассировки печатного монтажа "TopoR" // Свидетельство об официальной регистрации программы для ЭВМ № 2005611893 - М Российское агентство по патентам и товарным знакам (РОСПАГННТ) -2005

22 1 lei росян Г С . Полубасов О Б Методика отбора вариантов при оптимизации ра зводки соединений // Технологии приборостроения. - 2005. - №3. - С. 16-19.

Подписано в печать 24 11.05 Формат 60 84 1/16 Бумага офсетная Печать офсетная Печ д. 10 Тираж 100 экз. Заказ 72

Отпечакшо с готового оригинал-макета в типографии Издательства С116ГУ1У "ЮНГ

Издательство СГ16Г0 IУ "Ю1 И" 197376. С -Петербург, ул. проф Попова. 5

е ^ хП У # -О

РНБ Русский фонд

2007-4 8136

I ь

(I

1-г V

■а

► е*. а »

\ ? 5 > У

2 9 Щ 2005

ВВЕДЕНИЕ

I. СРАВНЕНИЕ ТОПОЛОГИЧЕСКОЙ ТРАССИРОВКИ С ДРУГИМИ МЕТОДАМИ

1.1. Чисто топологические методы

1.2. Метод гибкой трассировки.

1.3. Технология Shape-based

1.4. Признак топологического трассировщика

1.5. Недостатки метода гибкой трассировки

1.6. Выводы

II. МОДЕЛИ ПЕЧАТНОГО МОНТАЖА

2.1. Диаграммы «сущность - связь».

2.2. Топологическая модель печатного монтажа

2.3. Геометрическая модель печатного монтажа

2.4. Выводы.

III. СИНТЕЗ ГЕОМЕТРИЧЕСКОЙ МОДЕЛИ ПО ДАННЫМ ТОПОЛОГИЧЕСКОЙ И СИНТЕЗ ТОПОЛОГИЧЕСКОЙ МОДЕЛИ ПО ДАННЫМ ГЕОМЕТРИЧЕСКОЙ

3.1. Синтез геометрической модели печатного монтажа по данным топологической.

3.1.1. Постановка задачи

3.1.2. Прокладка ребра

3.1.3. Добавление в триангуляцию межслойных переходов

3.2. Синтез топологической модели печатного монтажа по данным геометрической.

3.2.1. Постановка задачи

3.2.2. Построение триангуляции рабочего поля

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

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

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

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

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

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

На защиту выносятся следующие новые научные результаты:

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

2. Методика синтеза топологической модели печатного монтажа по данным геометрической модели.

3. Методика синтеза геометрической модели печатного монтажа по данным топологической модели.

4. Методика отбора вариантов при многокритериальной оптимизации разводки соединений.

По мнению автора, основная практическая ценность работы заключается в создании системы автоматизированного проектирования топологии печатного монтажа "TopoR", зарегистрированной в

Российском агентстве по патентам и товарным знакам (РОСПАТЕНТ) под номером 2005611893 от 29.07.2005 г.

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

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

- III научно-практической конференции "Современные информационные и электронные технологии", г. Одесса, 2002г.;

- VI международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 2002 г.;

- 9-й международной конференции "Современные технологии обучения", С.-Петербург, 2003 г.;

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

- VII международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 2003 г.;

- Международной научно-технической конференции MTIH(CALS)

2003 "Информационные технологии в управлении жизненным циклом изделий", С.-Петербург, 2003 г.;

- Всероссийской научно-практической конференции "Информационные технологии в российской промышленности", С.-Петербург, 2004 г.;

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

- III международном симпозиуме "Аэрокосмические приборные технологии", С.-Петербург, 2004 г.;

- Международной научно-практической конференции "Фундаментальные и прикладные проблемы приборостроения", Сочи, 2004 г.;

- VIII международной научно-практической конференции "Системы и средства передачи и обработки информации", Одесса,

2004 г.;

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

По теме диссертации опубликовано 22 научные работы, из них -1 авторское свидетельство, 1 статья и тезисы к 20-ти докладам на международных научно-технических и научно-практических конференциях.

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

5.4. Выводы

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

2. Отладочная система интегрирована в САПР "TopoR".

3. Проведён сравнительный анализ результатов разводки, полученных с помощью систем автоматизированного проектирования печатного монтажа ("TopoR", "PCAD", "Protel DXP", "SPECCTRA", "Power PCB"). Показано несомненное преимущество системы "TopoR".

ЗАКЛЮЧЕНИЕ

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

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

3. Разработаны алгоритмы синтеза топологической модели печатного монтажа по данным геометрической модели и синтеза геометрической модели по данным топологической.

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

5. Разработана и интегрирована в САПР "TopoR" система отладки работы алгоритмов, включающая пошаговую отладку с визуализацией.

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

ГЛОССАРИЙ

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

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

1. Абакумов В.Г., Сербии С.А. Сравнительный анализ методов конструирования печатных плат. Управляющие системы и машины. 1981, Вып.5. С. 43-47.

2. Абрайтис Л.Б. Лучевой алгоритм для проведения печатных соединений. Вопросы радиоэлектроники. Сер.ЭВТ, 1968. Вып.З. С.35-45.

3. Абрайтис Л. Б., Гирнюс А. П. Канальная трассировка с учетом контактов разъемов и меняющейся ширины канала. Управляющие системы и машины, 1983. №6. С. 24-27.

4. Абрайтис Л.Б., Лянкявичус А.Н. Алгоритм параллельной глобальной трассировки двухслойных печатных плат. В сб.: Автоматизация конструкторского проектирования в радиоэлектронике и вычислительной технике // КПИ. Вильнюс, 1983. Т.З., С. 12-20.

5. Абрайтис Л.Б., Шнейкаускас Р.И., Жилявичус В.А. Автоматизация проектирования ЭВМ. М.: Сов. радио, 1978, 272с.

6. Абрайтис Л.Б., Автоматизация проектирования топологии цифровых, интегральных микросхем. М.: Радио и связь, 1985, 197с.

7. Авенье Е.П. Обзор методов проектирования топологии. ТИИЭР, 1983. т.71. №1. с.60-70.

8. Автоматизация поискового конструирования (искусственный интеллект в машинном проектировали::). Под ред. А.И. Половинкина - М.: Радио и связь, 1981, - 344с.

9. Автоматизация проектирования цифровых устройств./ Под ред. С.С.Бадулина. М.: Радио и связь, 1981. - 240с.Базилевич Р.П.

10. Некоторые задачи синтеза планарных топологий. В кн.: Вычислительная техника. Вильнюс, 1979, Т. 12, с. 16-23.

11. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного метода конструирования электронных устройств. Львов.: Вища школа, 1981. - 168с.

12. Базилевич Р.П. Обобщённый подход к формализации задачи машинной трассировки межсоединений на плоскости. Изв. вузов СССР. Радиоэлектроника, 1974, N6, с. 98-103.

13. Балтрушайтис Р.И, Алгоритм снижения загруженности перегруженных областей монтажного пространства. В сб.: Вычислительная техника // КПИ, Вильнюс, 1982, т. 16, с. 15-17.

14. Баранов С.И., Майоров С.А. Сахаров Э.П., Селютин В.А. Автоматизация проектирования цифровых устройств. Л.: Судостроение, 1979. - 264с.

15. Бахтин Б.И. Автоматизация в проектировании и производстве печатных плат радиоэлектронной аппаратуры. Л.: Энергия, 1979. - 120с.

16. Бершадский A.M. Применение графов и гиперграфов для автоматизации проектирования РЭА и ЭВА. Изд-во Саратовского ун-та, 1983. - 120с.

17. Берштейн Л.С., Сапрыкин А.А. Минимизация наиболее длинных связей при линейном размещении элементов схемы. Изв. АН СССР, Техн. кибернетика, 1981, № 6, с.91-99.

18. Берштейн Л.С. Селянкин В.В. Линейное размещение гиперграфов. -Изв. АН СССР, Техн. кибернетика, 1973. № 3, с.128 —135.

19. Теория и методы автоматизации проектирования вычислительных систем // Под ред. Бреуера М. М.: Мир, 1977. -284с.

20. Вичес С.А. Асимптотический оптимальный алгоритм перечисления пересечений ребер двудольного графа. Авт. и телемеханика, вып.12. 1984, с.133-137.

21. Гель П.П., Иванов-Есипович Н.К. Конструирование радиоэлектронной аппаратуры. JL: Энергия, 1982, 232с.

22. Глушков В.М., Мясников В.А., Половинкин А.И. Автоматизация поискового конструирования. Вестник АН СССР, 1979, № 7. С.42-48.

23. Гндоян А.К. Об одном подходе к задаче трассировки. Вопросы радиоэлектроники, сер. ЭВТ, 1980, Вып. 14, С. 43-47.

24. Гндоян А.К. Об одном алгоритме покрытия внешних связей печатных плат. Вопросы радиоэлектроники, сер. ЭВТ, 1979, Вып.9, С. 52-53.

25. Горощенко А.Г. Сравнение критериев оптимизации межсоединений в радиоэлектронной аппаратуре. УСиМ, 1984, № 3, с.48-51.

26. Горощенко А.Г. Матричный метод проектирования межсоединений на типовых печатных платах. УСиМ, 1975, № 5, с.128-132.

27. Деньдобренко Е.Н., Малика А.С. Автоматизация проектирования радиоэлектронной аппаратуры. М.: Высшая школа, 1980. -384с.

28. Жилинскас А., Шалтянис В. Поиск оптимума: компьютер расширяет возможности. // М.: Наука. 1989. - 128 С.

29. Зудин С.В., Петросян Г.С., Полубасов О.Б., Лузин С.Ю. Система автоматизированного проектирования «FreeStyle 2.0». Труды II международной НПК "Современные информационные и электронные технологии", Одесса, 2001, с. 198.

30. Зыков А. А. Основы теории графов. М.: Наука, 1987. - 384 с.

31. Карапетян А. М. Автоматизация оптимального конструирования ЭВМ. М.: Сов. радио, 1973.

32. Картер Б. Техника разводки печатных плат. Часть 1. // Chip News. 2004. - №7. - С.63-70.

33. Картер Б. Техника разводки печатных плат. Часть 2. // Chip News.-2004.- №10.- С.46-51.

34. Кристофидес Н. Теория графов. -М.: Мир, 1978. 423 с.

35. Литвинов З.Н. Об одном подходе к решению задачи минимизации длины связывающей сети при размещении геометрических объектов. В сб.: Размещение геометрических объектов и вопросы оптимального проектирования. ИК АН УССР, Киев, 1977. —48с.

36. Лузин С.Ю., Полубасов О.Б. САПР печатных плат "FreeStyle Route". Материалы международной конференции "Современные технологии обучения", С.-Петербург, 1997, с. 178180.

37. Лузин С.Ю., Полубасов О.Б. Трассировка печатных плат. Новые методы решения старых проблем. "САПР и графика", 1997, №11, с. 58-59.

38. Лузин С.Ю., Полубасов О.Б. Визуализация алгоритмов трассировки. Материалы международной конференции "Современные технологии обучения", С.-Петербург, 1998, с. 127.

39. Лузин С.Ю., Полубасов О.Б. Пакет гибкой топологической трассировки "FreeStyle Route". Материалы международной НПК 41. "Системы и средства передачи и обработки информации" («ССПОИ»), Одесса, 1997, с. 35.

40. Медведев А. Печатные платы. Конструкции и материалы. М.: Техносфера. - 2005. - 302 С.

41. Мелихов A.M., Берштейн J1.C., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974.-304с.

42. Мелихов А.К., Берштейн Л.С., Селянкин В.В. Минимизация пересечений проводников в канале с помощью гиперграфов. -АиВТ, 1977, № 4. С.77-82.

43. Мельничук И.Г., Толстун A.M., Горощенко Л.Г. Базовая программа оптимизации распределения связей и модулей. -Управляющие системы и машины, 1983. №5. С.31-33.

44. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование радиоэлектронной аппаратуры. М.: Радио и связь, 1983.- 280с.

45. Морозов К.К. к др. Проектирование монтажных плат на ЭВМ. -М.: Советское радио, 1979. 224с.

46. Петренко А.И., Тетельбаум А.Я. Формальное конструирование электронно-вычислительной аппаратуры. М.: Советское радио, 1979.-253с.

47. Петренко А.П., Тетельбаум А.Я., Забалуев Н.Н. Топологические алгоритмы трассировки многослойных печатных плат. М.: Радио и связь, 1983. - 152с.

48. Петросян Г.С. и др. Система автоматизированного проектирования FreeStyle 2.0. // Труды второй международной научно-практической конференции "Современные информационные и электронные технологии". — Одесса. — 2001. -С.210.

49. Петросян Г.С. и др. Интегрированная система автоматизированного проектирования "FreeStyle EDA" // Труды V международной научно-практической конференции "Системыи средства передачи и обработки информации". Одесса. - 2001. -С.105-106.

50. Петросян Г.С., Зудин С.В. Интегрированная САПР печатных плат. // 8-я международная научно-техническая конференция студентов и аспирантов "Радиоэлектроника, электротехника и энергетика". Тезисы докладов. Т.1. - Москва. -2002. - С.76-77.

51. Петросян Г.С. и др. Учебная САПР тонкопленочных микросборок. // Материалы 9-й международной конференции "Современные технологии обучения". С.-Петербург. - 2003. -Т. 1.-С. 196-197.

52. Петросян Г.С., Полубасов О.Б. Интеграция процессов оптимизации и редактирования топологии. // Труды 4-й международной научно-практической конференции "Современные информационные и электронные технологии". -Одесса.-2003.-С.208.

53. Петросян Г.С., Соколов В.Е., Лузин С.Ю. Декомпозиция задачи выделения в графе наибольшего полного подграфа. // Труды 4-й международной научно-практической конференции "Современные информационные и электронные технологии". -Одесса.-2003.-С.212.

54. Петросян Г.С. и др. TopoR система автоматизированной трассировки печатных плат. // Труды VII международной научно-практической конференции "Системы и средства передачи и обработки информации". - Одесса. - 2003. - С. 137.

55. Петросян Г.С. и др. Система топологической трассировки печатных плат. // Труды международной научно-технической конференции ИПИ(САЬ8)-2003 "Информационные технологии в управлении жизненным циклом изделий". С.-Петербург. — 2003.-С.38.

56. Петросян Г.С. и др. Автоматизация синтеза топологии печатного монтажа. // Труды 5-й международной НПК "Современные информационные и электронные технологии". Одесса. - 2004. -С.166.

57. Петросян Г.С., Дюдин М.В., Полубасов О.Б. Использование функциональной эквивалентности на этапе пробной трассировки. // Труды 5-й международной НПК "Современные информационные и электронные технологии". Одесса. - 2004. -С.164.

58. Петросян Г.С. и др. Преимущества неортогональной топологии печатного монтажа. // Труды 5-й международной НПК "Современные информационные и электронные технологии". -Одесса.-2004.-С. 167.

59. Петросян Г.С. и др. Обеспечение электромагнитной совместимости на этапе размещения компонентов. // Труды 5-й международной НПК "Современные информационные и электронные технологии". Одесса. - 2004. — С. 163.

60. Петросян Г.С. и др. Система автоматизации синтеза топологии печатного монтажа. // Труды Всероссийской научно-практической конференции "Информационные технологии в российской промышленности". С.-Петербург. - 2004. - С.91-92.

61. Петросян Г.С. Воротынцев В.Ю., Лузин М.С., К оценке качества топологии печатного монтажа. // Труды III международногосимпозиума "Аэрокосмические приборные технологии". С.Петербург. - 2004. - С. 175.

62. Петросян Г.С. Воротынцев В.Ю., Лузин М.С., Пути повышении плотности печатного монтажа. // Труды Международной научно-практической конференции "Фундаментальные и прикладные проблемы приборостроения". Сочи. - 2004. - С. 29-30.

63. Петросян Г.С. и др. Обеспечение заданного качества топологии печатного монтажа. // Труды VIII международной научно-практической конференции "Системы и средства передачи и обработки информации". Одесса. - 2004. - С. 119-120.

64. Петросян Г.С. и др. Способ повышения плотности печатного монтажа. // Труды VIII международной научно-практической конференции "Системы и средства передачи и обработки информации". Одесса. - 2004. - С. 123-124.

65. Петросян Г.С. и др. Контроль констуктивно-технологических нарушений в системе TopoR. // Труды 6-й международной НПК "Современные информационные и электронные технологии". -Одесса. 2005.-С.212.

66. Петросян Г.С., Полубасов О.Б. Многовариантная оптимизация разводки соединений. // Труды 6-й международной НПК "Современные информационные и электронные технологии". Одесса. - 2005. - С.211.

67. Петросян Г.С. и др. Система топологической трассировки печатного монтажа "TopoR" // Свидетельство об официальной регистрации программы для ЭВМ № 2005611893. М. Российское агентство по патентам и товарным знакам (РОСПАТЕНТ).-2005.

68. Петросян Г.С., Полубасов О.Б. Методика отбора вариантов при оптимизации разводки соединений // Технологии приборостроения. 2005. - №3 С. 16-19

69. Полубасов О.Б. Гибкий метод трассировки печатных плат. -Всесоюзная НТК "Совершенствование технических средств связи для решения проблем информатизации общества в новых условиях хозяйствования", Тез. докладов, Ленинград, 1991, С. 87-88.

70. Полубасов О.Б. Локальное редактирование топологии печатной платы. Всесоюзная НТК "Совершенствование технических средств связи для решения проблем информатизации общества в новых условиях хозяйствования", Тез. докладов, Ленинград,1991, С. 89-90.

71. Полу басов О.Б. Алгоритмы локальной оптимизации расслоения на этапе макротрассировки. // Технологии приборостроения. — 2004.-№3(11).-С. 23-36.

72. Полубасов О.Б. Глобальная минимизация количества межслойных переходов. Технология и конструирование в электронной аппаратуре. 2001. - №2. - С. 3-9.

73. Полубасов О.Б., Стекольщиков А.В. Модель платы для автоматического редактирования печатного монтажа. В сб.: Автоматизация проектирования РЭА и ЭВА. - Пенза, ПДНТП,1992, С. 30-32.

74. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. М.: Мир, 1980. - 476с.

75. Рябов Л.П., Темницкий Ю.Н. Деформация лабиринта при автоматической доразводке проводников печатных плат. Обмен опытом в радиопромышленности, 1978, вып. 4-5, С.88-89.

76. Селютин В.А. Машинное конструирование электронных устройств. М.: Советское радио, 1977, - 384с.

77. Смолич Г.Г., Смолич Л.И. Минимизация числа переходных отверстий при проектировании двухсторонних печатных плат. -Обмен опытом в радиопромышленности, 1984, вып.11. с.54-56.

78. Соколов В.А., Фридман М.Г., Шеин П.,Д. Состояние и перспективы развития систем автоматизированного проектирования двухсторонних печатных плат. Изв.АН СССР, Техническая кибернетика, 1982, №2, с. 171-178.

79. Сухарев А.В., Золотое А.И. Модели и процедуры оптимизации в автоматизации проектирования. (Программный комплекс FreeStyle Router): Учеб. пособие. СПб.: СЗТУ, 2001. - 165с.

80. Тетельбаум А .Я., Шрамченко Б.Л. Применение гиперграфов при исследовании планарности электронных схем. Изв. АН СССР, Техн. кибернетика, 1975. №5. с. 127-136.

81. Фейнберг В.З., Рабинович Е.Б. Организация баз данных в геометрических задачах проектирования больших интегральных схем. Докл. АН БССР, 1986, Т. XXX. №5. с. 406-409.

82. Фейнберг В.З. Геометрические задачи машинной графики больших интегральных схем. М.: Радио и связь, 1987, - 176 с.

83. Финкелыитейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1973, - 231с.

84. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966, - с.

85. Харари Ф. Теория графов. М.: Мир, 1973. - 300с. 1978.

86. Хигстон Д., Логхид Ф., Ирвин Р. Новый топологический автотрассировщик. — www.altium.com,www.electrade.ru.

87. Целочисленное программирование и потоки в сетях. М.: Мир, 1974, - 520 с.

88. Шрамченко Б. Л., Абакумов В. Г. Об определении матрицы смежности модулей. В кн.: Автоматизация проектирования в электронике. Вып.11., Киев.: Техника, 1975, с. 95-98.

89. С. J. Alpcrt : "A direct combination of the Prim and Dijkstra constructions for improved performance-driven global routing." Proc. Of ISCAD93. pp. 1869-1872 (1993).

90. J. Cong. A. Kahng, G. Robins. M. Sarrafzadeh, and С. K. Wong, "Provably good performance-driven global routing," IEEE Trans. Computer-Aided Design, Vol. 11, No. 6, June 1992.

91. D. N. Deutsch, "A Dogleg Channel Router," in Proc. 13th IEEE Design Automation Conf., pp. 425-433, 1976.

92. F.F. Dragan, A.B. Kahng, I. Mondoiu, S. Muddu, A. Zelikovsky "Provably Good Global Buffering Using an Aviable Buffer Block Plan", Proc. of ICC AD 2001, pp. 104-109.

93. M. Edahiro and T. Yoshiroura: "New placement and global routing algorithm for standard cell layouts," Proc. of 27th DAC, pp. 642-645 (1990).

94. A. Fallah and J. Rose, Timing-driven routing segment assignment in FPGAs," Canadian Conf. on VLSI, 1992.

95. Hongbing Fan, Jiping Liu, Yu-Liang Wu "General Models for Optimum Arbitrary-Dimention FPGA Switch Box Designs", Proc. 1С CAD 2001, pp.93-98.

96. R. С Garden and C.K. Cheng: "A global rooter using an efficient approximate multicommodity multitennmal flow algorithm," Proc. of 28th DAC. pp. 316-321 (1991).

97. Toshiyuki Hama and Hiroaki Etoh "Single-layer automatic router" http://www.trl.ibm.com/proiects/optsim/opt/SLR/index e.htm

98. S. E. Hambrusch, "Using overlap and minimizing contact points in channel routing" in Proc. 21st Ann. Atlerton Conf. on Comm., Contr., and Сотр., 1983.

99. Hambrusch S. E. Channel Routing Algorithm for Overlap Models. -IEEE Trans. Computer-Aided Des., Vol. CAD-4, No.l, JANUARY 1985, p.23-40.

100. J. Huang. "An efficient timing-driven global routing algorithm," Proc. of 30th DAC pp. 596-600 (1993).

101. Jiang Hu, Sachin S. Sapatnekar "A Timing-constrained Algorithm for Simultaneous Global Routing of Multiple Nets", Proc. of ICC AD 2001, pp.99-103.

102. R.Kastner, E. Bozorgzadeh, M. Sarafzadeh "Predictable Routing", Proc. of ICC AD 2001, pp. 110-114.

103. M. Khellah. S. Brown, and Z. Vraneaic, "Modelling Routing Delays in SRAM-based FPGAs," Canadian Conf. on VLSI, 1993.

104. Leigthon F.T., Rosenberg A.L. Tree-Dimentional Circuit Layouts. SIAM J. Comput. Vol.15, No. 3, August 1986, p. 793-813.

105. R. Lin : "Channel density reduction by routing over the cells." Proc. of 28th DAC. pp. 120-125 (1992).

106. Sarafzadeh M. Channel-Routing Problem in the Knock-Knee Mode is NP-Complete. IEEE Trans. Computer-Aided Des., Vol. CAD-6, No.4, JULY 1987, p.503-506.

107. M. Sarrafzadeh and F. P. Preparata, "Compact channel routing of multiterminal nets," Ann. Discrete Math., no. 25, pp. 255-279, Apr. 1985.

108. A. Sechen and A. Sangiovanni-Vincentelli. "A New Standard Cell Placement and Global Routing Package". In Design Automation Conference, pp. 432-439. IEEE/ACM, 1986.

109. A. Srimvasan, et aL: "RITUAL: A performance driven placement algorithm for small cell ICs," Proc. of ICCAD91. pp. 4851 (1991).

110. W. Swaitz and С Sechen: "A new generalized row-based global router," Proc. of 1С CAD93. pp. 491-498 (1993).