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

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

ЗУДИН Станислав Владимирович

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

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

АВТОРЕФЕРАТ

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

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

Работа выполнена в открытом акционерном обществе "Авангард" (Санкт-Петербург).

Научный руководитель -доктор технических наук Лузин СЮ.

Официальные оппоненты: доктор технических наук, профессор Дмитревич Г.Д. кандидат технических наук, старший научный сотрудник Глинских А.А.

Ведущая организация - Федеральное государственное унитарное

предприятие "НИИ "Вектор".

Защита диссертации состоится 2004 года в часов 3 О

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

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

Автореферат разослан года.

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

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

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

- существенный рост размерности задач в связи с использованием крупноформатных подложек-оснований и установкой на них многовыводных (до 1500 контактов) компонентов;

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

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

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

- необходимость ориентации создаваемых САПР на автоматизированное производство;

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

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

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

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

гибридно-интегральной технологии. В соответствии с этим в работе ставились и решались следующие задачи:

- анализ применяемых моделей объектов и критериев МКП узлов РЭС на печатных платах, микросборках и СБИС; формирование эффективной оценки качества размещения электрорадиоэлементов (ЭРЭ) в монтажном пространстве;

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

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

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

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

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

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

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

- в разработке моделей электрических схем, адекватных требованиям топологического синтеза РЭС;

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

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

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

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

также в учебном процессе СПбГУТ им. проф. МА.Бонч-Бруевича и СПбГЭТУ (ЛЭТИ). Акты, подтверждающие внедрение, приведены в приложении.

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

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

- П-ой международной научно-технической конференции студентов, аспирантов и молодых специалистов стран СНГ, г. Санкт-Петербург, 2000г. (2 доклада);

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

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

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

- 8-й международной научно-технической конференции студентов и аспирантов "Радиоэлектроника, электротехника и энергетика", Москва, 2002г.;

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

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

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

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

- Научно-технических конференциях профессорско-преподавательского состава СП6ТУТ им. проф. МА.Бонч-Бруевича, г. Санкт-Петербург, 1998г., 1999г.

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

Структура и объем - диссертации. Диссертация состоит из введения, пяти глав, заключения, одного приложения и списка литературы, включающего 87 наименований. Основная часть работы изложена на 125 страницах машинописного текста. Работа содержит 43 рисунка и 10 таблиц.

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

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

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

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

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

где п, - число элементов, связанных i -й цепью.

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

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

Из (2), в частности следует причем К- 1 (ЛМ)) соответствует

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

Пусть П - среднее количество звеньев в цепи или иначе число звеньев в

1 т

Подставляя (3) в (2), имеем

брос количества контактов в цепях.

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

Показано, что суммарная длина ребер полного графа является кубической функцией числа вершин с коэффициентом меньшим 1/6, зависящим от расположения вершин (элементов). Этот коэффициент будет минимален, если элементы занимают смежные позиции и вписываются в квадрат. Полупериметр охватываютттего цепь прямоугольника в этом случае будет также минимален и равен 2(рп"|—1), апри линейном размещении вершин - максимален.

Представление многозвенных (п,> 2) цепей полными подграфами приводит также к существенно завышенным оценкам длины трасс и неадекватным оценкам количества пересечений.

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

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

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

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

1. Пусть для пары цепей I и у

тогда в графе все решения, содержащие по одному дереву для

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

2. Пусть для пары цепей / и у

тогда минимальное дерево в будет содержать одно

(произвольное) дерево из по одному (произвольному) дереву из

и , а также два произвольных ребра, доставляющих

связность трех указанных подграфов.

3. "Поглощение"

а) если для пары цепей и у

то одну из цепей можно исключить из рассмотрения;

б) если для некоторой цепи т

и при этом

3 |<?,ПС7,|£1 и ,

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

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

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

B:=B\Gl.

Пока в В есть G,, для которых [.SoGj^l выбрать |5uG,|=min;

(при равенстве оценок предпочтение В (Л Gt Ф0). B:=BkjGB:=B\Gi.

}

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

Декомпозиция цепей базиса

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

Если ^ , то при критерии минимума ребер графа выбор дерева

произволен.

Если ^ П^У*^, то X, разбивается на классы, соответствующие

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

Метод 2.

Пусть Sj = {Stj,S2j,...,Sy}- множество цепей, которым принадлежат контакты у-го элемента. Кроме того, имеется множество элементов

Xj = {x[j,x'2j.....х'у}, связанных с элементом Xj, и семейство

множеств ; причем

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

s;=S,nSj*0 (ijêïj;

Если для каких-либо q элементов из множества. X'j выполняется усло-

вие

и при этом

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

Метод 3. Для того, чтобы минимизировать суммарную длину звеньев цепей, соединяющих некоторый элемент ЛТ/С другими элементами, следует расположить рядом с этим элементом минимальное множество элементов, содержащих все внешние связи данного элемента.

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

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

где 1г} -длина ] -й цепи (количество элементов, связанных у* -й цепью);

к - количество внешних связей элемента Хг;

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

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

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

При расчете электромагнитных помех учитывается трехмерный характер задачи. Ниже на рисунке показан фрагмент МПП в поперечном разрезе. Сигнальная линия (БЬ) - это линия, по которой передается сигнал. Вокруг нее показаны восемь возможных параллельных линий (0-7).

10 7 Г. Г

Рис.1 Сигнальная линия (БЬ) и возможные связанные с нею линии (0-7).

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

Таким образом, в ячейку цепной схемы может входить трансформатор с 9 обмотками. Учитывая, что нагрузка, создаваемая связанной линией, достаточно мала, можно пренебречь влиянием одной связанной линии на другую линию, связанную с этой же сигнальной линией. Поэтому в рассматриваемом случае можно заменить трансформатор с 9 обмотками 8-ю трансформаторами, каждый из которых имеет только 2 обмотки, что позволяет вместо одной сложной схемы рассматривать 8 значительно более простых схем.

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

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

- коэффициент самоиндукции обратного провода равен нулю;

- токи Фуко в контактных площадках не учитываются;

диэлектрическая проницаемость материала подложки равна диэлектрической проницаемости вакуума;

- магнитная проницаемость окружающей среды равна магнитной проницаемости вакуума;

- электрическое и магнитное поля являются плоскопараллельными.

На рис.2а показаны электрическое и магнитное поля двух связанных линий, одна из которых является сигнальной (по ней передается сигнал), а вторая находится на расстоянии от сигнальной линии меньше заданного и сигнал в ней отсутствует.

Эквивалентные схемы ячеек этих линий показаны на рис.2б. Взаимное влияние линий учитывается с помощью элементов эквивалентной схемы М,

Сш,Яш.

211тП фСг 21?т

2яП ¿а 2*

жИ

1111111111111

а)

и

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

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

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

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

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

где х и у - координатные векторы для п ячеек, а С1у представляет связность

ячеек I и у, имеет единственный минимум, который можно найти, приравняв нулю все частные производные:

ф+ИаМ -у/

и

^-О^ЗХСИ-^-О;

<5Ф

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

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

процессе расчёта не изменяются.

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

3. Силовое размещение минимизирует сумму квадратов длин и не обеспечивает глобального минимума суммарной длины проводников.

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

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

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

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

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

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

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

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

Проведенный сравнительный анализ продемонстрировал несомненное преимущество программы АиТОР по сравнению с аналогами (Брессйн, РСАБ) в части быстродействия и качества получаемых решений (сокращение длины проводников на 30-50%). Кроме того, использование АиТОР в комплексе с программой расчета электромагнитных помех и программой пробной

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

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

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

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

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

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

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

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

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

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

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

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

9. Разработана программная подсистема автоматизированного размещения компонентов.

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

1. Алексеев М.И., Зудин СВ.; Полубасов О.Б., Стекольщиков А.В. "FreeStyle Router" // A.c. № 980492 от 14.08.1998 г.

2. Полубасов О.Б., Зудин СВ. К вопросу о квадратичном размещении ячеек БИС. // Технология и конструирование в электронной аппаратуре. - 1999 -№ 5-6. - С. 10-13.

3. Зудин СВ., Лузин М.С, Лузин СЮ. Использование функциональной эквивалентности при проектировании печатных плат. // Труды международной НТК "Системы и средства передачи и обработки информации". - Одесса. - 1999. - С. 68.

4. Зудин СВ., Полубасов О.Б. Некоторые аспекты оптимизации одного алгоритма размещения. // Доклады 2-й международной НТК студентов, аспирантов и молодых специалистов стран СНГ "Техника и технология связи". - С.-Петербург. - 2000. - С. 329-330.

5. Полубасов О.Б., Зудин СВ. Современное решение задачи размещения. // Труды международной НПК "Современные информационные и электронные технологии". - Одесса. - 2000. - С. 71.

6. Бурцев С.Г., Зудин СВ. Задача начального размещения компонентов. // Труды международной научно-практической конференции "Современные информационные и электронные технологии". - Одесса. - 2000. - С.64.

7. Бурцев С.Г., Зудин СВ. Выбор конфигурации цепей в задаче размещения компонентов. // 2-я Международная НТК "Техника и технология связи". Тез. докладов. - С.-Петербург. -2000. - С. 322-323.

8. Зудин СВ., Лузин С.Ю., Полубасов О.Б. Определение смежности компонентов. // Труды второй международной научно-практической конференции "Современные информационные и электронные технологии". -Одесса.-2001.-С. 198.

9. Зудин СВ., Петросян ГС, Полубасов О.Б., Лузин СЮ. Система автоматизированного проектирования FreeStyle 2.O. // Труды международной научно-практической конференции "Современные информационные и электронные технологии". - Одесса. - 2001. - С. 210.

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

11.Зудин СВ., Лузин С.Ю., Полубасов О.Б. Определение смежности компонентов электронных схем. // Труды V международной научно-практической конференции "Системы и средства передачи и обработки информации". - Одесса. - 2001. - С. 98-99.

12.3удин СВ., Лузин С.Ю., Полубасов О.Б. Выбор конфигурации соединения компонентов электронных схем до этапа размещения. // Технология и

конструирование в электронной аппаратуре. - Одесса. - 2001. - №. - С.39-40.

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

Н.Зудин СВ. Оптимизация алгоритма определения матрицы смежности компонентов. // 8-я международная научно-техническая конференция студентов и аспирантов "Радиоэлектроника, электротехника и энергетика". Тезисы докладов. - Т.1. - Москва. - 2002. - С. 306.

15.Дмитриев П.И., Зудин СВ., Полубасов О.Б. Повышение эффективности "силового" размещения компонентов. // Труды 4-й международной НПК "Современные информационные и электронные технологии". - Одесса. -2003.-С. 209.

16.Дмитриев П.И., Зудин СВ., Лузин М.С., Петросян Г.В., Полубасов О.Б. Учебная САПР тонкопленочных микросборок. // Материалы 9-й международной конференции "Современные технологии обучения". - С.Петербург. - 2003. - Т. 1. - С. 196-197.

17.Дмитриев П.И., Зудин СВ.; Лузин М.С., Лузин С.Ю., Петросян Г.С, Полубасов О.Б. ТороЯ - система автоматизированной трассировки печатных плат. // Труды VII международной научно-практической конференции "Системы и средства передачи и обработки информации". - Одесса. - 2003. -С.137.

18.Дмитриев П.И., Зудин СВ., Лузин М.С., Лузин С.Ю., Петросян Г.С, Полубасов О.Б. Система топологической трассировки печатных плат. // Труды международной научно-технической конференции НГГН(САЬ8)-2003 "Информационные технологии в управлении жизненным циклом изделий". — С.-Петербург. - 2003. - С. 38.

19.Дмитриев П.И., Зудин СВ., Лузин М.С, Лузин СЮ., Петросян Г.С, Полубасов О.Б. Интегрированная САПР тонкопленочных гибридных интегральных схем "Авангард". // Труды международной научно-технической конференции НиН(САЬ8)-2003 "Информационные технологии в управлении жизненным циклом изделий". - С.-Петербург. - 2003. - С. 3940.

Подписано к печати 29 12 03

Тираж 60 экз Заказ № 938

Отпечатано в Центре малой полиграфии

191131, Санкт-Петербург, бульвар Красных зорь, д 5

Р - 36 4 2

ВВЕДЕНИЕ.

I. КРИТЕРИИ КАЧЕСТВА МОНТАЖНО-КОММУТАЦИОННОГО ПРОЕКТИРОВАНИЯ РЭС

1.1. Размещение для получения минимальной длины соединений

1.2. Размещение для получения равномерного заполнения монтажного пространства

1.3. Частные оценки размещения

1.4. Формирование эффективного критерия качества размещения.

Выводы

II. ОПТИМИЗАЦИЯ МОДЕЛИ ЭЛЕКТРИЧЕСКОЙ СХЕМЫ

2.1. Минимизация числа ребер графа модели схемы

2.2. Построение модели схемы на основе линейного размещения независимых цепей

2.3. Построение модели схемы на основе решения задачи о кратчайшем покрытии. ф Выводы

III. РАСЧЕТ ЭЛЕКТРОМАГНИТНЫХ ПОМЕХ

В ПЕЧАТНЫХ ПЛАТАХ.

3.1. Допущения, принятые при расчете электромагнитных помех

3.2. Одиночные линии

3.3. Связанные линии линии

3.5. Удельные электрические параметры линий передачи на печатных платах

3.6. Формулы расчета

3.7. Метод расчета сигналов и помех

3.8. Использование подсхем и компактного хранения параметров

3.9. Редукция многополюсников, представленных

Y - параметрами

3.10. Редукция эквивалентных схем путем преобразований «звезда - многоугольник». щ Выводы

IV. СОВМЕСТНОЕ РЕШЕНИЕ ЗАДАЧ РАЗМЕЩЕНИЯ

И ТРАССИРОВКИ

4.1. Создание условий для качественной детальной трассировки

4.2. Начальное размещение

4.3. Выбор конфигурации цепей

4.4. Разбиение областей

4.5. Назначение ячеек на области и установка размеров новых областей. ф 4.6. Предварительная трассировка

Выводы

V. РАЗРАБОТКА И ЭКСПЛУАТАЦИЯ ПРОГРАММНОЙ ПОДСИСТЕМЫ РАЗМЕЩЕНИЯ

5.1. Входные - выходные данные.

5.2. Структура данных.

5.2.1. Сущности.

5.2.2. Конструктив и схема соединений. ф 5.2.3. Принадлежность ячеек областям.

5.2.4. Графы горизонтального и вертикального разбиений.

5.2.5. Лес цепей.

5.2.6. Граф смежности областей для макротрассировки.

5.3. Пользовательский интерфейс.

5.4. Экспериментальная оценка качества машинного размещения.

5.4.1. Сравнительные результаты расчета электромагнитных помех.

5.4.2. Сравнение результатов автоматического размещения компонентов в программах

Бресс^а и АиТОР

Выводы.

Техническое проектирования является важнейшим этапом разработки радиоэлектронных средств (РЭС) различного назначения.

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

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

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

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

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

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

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

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

Заметный вклад в исследование проблемы эффективности автоматизированных методов МКП внесли Л.Б.Абрайтис, Р.П., Базилевич, A.M. Бершадский, В.М. Глушков, Б.Н. Деньдобренко, В.М. Курейчик, С.А. Майоров, Н.Я. Матюхин, А.Н. Мелихов, К.К. Морозов, А.И. Петренко, Г.Г. Рябов, В.А. Селютин, А.Я. Тетельбаум, Г.Р. Фридман, М.Е. Штейн, Г.Э. Широ и многие другие.

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

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

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

- анализ применяемых моделей объектов и критериев МКП узлов РЭС на печатных платах, микросборках и СБИС; формирование эффективной оценки качества размещения ЭРЭ в монтажном пространстве;

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

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

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

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

Научная новизна работы заключается:

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

- в разработке моделей электрических схем, адекватных требованиям топологического синтеза РЭС;

- в разработке эффективного алгоритма размещения компонентов электронных схем в плоском коммутационном пространстве.

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

Результаты диссертационной работы в виде конкретных положений, выводов, методов, алгоритмов, машинных программ и расчетных данных внедрены и инженерную практику и используются на промышленных предприятиях в Санкт-Петербурге и Одессе, а также в учебном процессе .0 СПбГУТ им. проф. М.А.Бонч-Бруевича и СЗПИ. Акты, подтверждающие внедрение, приведены в приложении.

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

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

- Н-ой международной научно-технической конференции студентов, аспирантов и молодых специалистов стран СНГ, г. Санкт-Петербург, 2000г. (2 доклада);

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

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

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

- 8-й международной научно-технической конференции студентов и аспирантов "Радиоэлектроника, электротехника и энергетика", Москва, 2002г.;

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

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

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

- Научно-технических конференциях профессорско-преподавательского состава СПбГУТ им. проф. М.А.Бонч-Бруевича, г. Санкт-Петербург, 1998г., 1999г.

По теме диссертации опубликовано 20 работ. Получено авторское свидетельство на программное средство, зарегистрированное в Государственном фонде.

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

Выводы

АиТОР.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

12. Балтрушайтис Р.И. Задача и оценки размещения. В сб.: Вычислительная техника. Каунас, КПИ, 1982, с.65-66.

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

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

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

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

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

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

19. Варшавский А.Д. Универсальный алгоритм размещения связных объектов в двухмерном пространстве. Экспресс-информация, ТС-9, Экономика и технология приборостроения, М.: 1979. Вып.5. - 16с.

20. Васильев 1 O.A., Глаголев В.В. Метрические свойства дизъюнктивных нормальных форм. В ст.: Дискретная матем. и матем. вопр.кибернетики, М. Наука, 1974, с.99-148.

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

22. Гаевенко А.Ю. Критерий качества и алгоритм размещения элементов РЭА. Тез. докл. Всесоюзного совещания "Автоматизация проектирования микроэлектронной аппаратуры", ч.2, 1J1., 1983, с.251-252.

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

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

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

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

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

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

29. Григоровский Л.Ф., Куранов Б.В. Ускоренный последовательный алгоритм размещения конструктивных элементов. Тез. докл. Всесоюзного совещания "Автоматизация проектирования микроэлектронной аппаратуры", ч.2, М., 1983, с.223-224.

30. Деньдобренко E.H., Малика A.C. Автоматизация проектирования радиоэлектронной аппаратуры. М.: Высшая школа, 1980. -384с.

31. Деньдобренко Б.Н., Селютин В.А. Опыт использования ЭВМ при конструировании радиоэлектронной аппаратуры. JL: ЛДНТП, 1977.-32с.

32. Ершов А. П. Введение в теоретическое программирование. М.: Наука. 1977.-288с.

33. Зиман Э.Л., Рябов Г.Г. Волновой алгоритм и электрические соединения. В сб.: Электронные вычислительные машины / HTM и ВТ АН СССР.-М. 1965.- 104с.

34. Казеннов Г. Г., Сердобинцев Е. В. Автоматизация проектирования БИС. Кн. 6. Проектирование топологии матричных БИС. Под ред. Г. Г. Казеннова. М.: Высш. шк., 1990. - 112 с.

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

36. Карапетян М.А. Система алгоритмов многокритериальной оптимизации при размещения элементов регулярных структур. В сб.: Автоматизация проектирования электронной аппаратуры. Межведомственный тематический сборник. - Таганрог.: ТРТИ. 1984. Вып.З. С.115-119.

37. Корбут A.A., Финкелыитейн Ю.Ю. Дискретное программирование. -М.: Наука, 1969.-368с.

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

39. Кузьмин Б.А., Эйдес А.Л., Иругов Б.С. Адаптируемые системы автоматизированного проектирования печатных плат. М.: Радио и связь, 1984. - 140с.

40. Кузьмин Б.А., Эйдес A.A. О критериях качества размещения. Управляющие системы и машины, №13, 1982, с.53-55.

41. Лазарева Т.О., Крапчин Л. И., Покровский А. .И. Алгоритм трассировки печатных соединений на основе представления о каналах. Автоматика и вычислительная техника, № 5, 1969, с. 12-15.

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

43. Лузин С.Ю., Полубасов О.Б. Топологическая трассировка: реальность или миф? // EDA Expert. 5(68). - 2002. - С. 42-46.

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

45. Мелихов Л.П., Берштейн Л.С. к др. Применение гиперграфов для компоновки схем ячейки. Изв. АН СССР, Техн. кибернетика, 1971, № 3, с.202-207.

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

47. Морозов К.К. и др. Методы разбиения схем на конструктивно-законченные части. М.: Радио и связь, 1978. - 134с.

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

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

50. Н.Нильсон, Искусственный интеллект. Методы поиска решений. -М.:"МИР", 1973.-272 с.

51. Норенков И.П., Маничев В.Б. Системы автоматизированного проектирования электронной и вычислительной аппаратуры. М.: Высшая школа, 1979. - 272с.

52. Островский В.М. К исследованию свойств кратчайших покрытий. В сб.: Синтез дискретных автоматов и управляющих устройств.

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

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

55. Петренко А.И. Основы автоматизации проектирования. Киев.: Техника, 1982.-295с.

56. Полубасов О.Б. Математические модели и алгоритмы автоматизированной разводки соединений печатных плат и БИС. // Диссертация на соискание ученой степени кандидата технических наук. С.-Пб.: СПбГЭТУ (ЛЭТИ). - 2002.

57. Помазанов В.М. К задаче о размещении ячеек в панели. В кн.: Применение вычислительных машин для проектирования цифровых устройств. Под ред. Н. Я. Матюхина. М., "Сов. радио", 1968.

58. Пузина C.B., Рябов Л.П., Темницкий O.K. Повышение эффективности алгоритма рекапитуляции печатного монтажа. Обмен опытом в радиопромышленности, 1983. № 11, с. 56-57.

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

60. Рощин В.А., Сергиенко И.В. Об одном подходе к решению задачи о покрытии. Кибернетика, 1984, № 6. с.65-69.

61. Рузаев E.H., Канунов А.И., Муравьев C.B. Алгоритмы нахождения минимального покрытия булевой матрицы. Изв. ВУЗов, Радиоэлектроника, 1981, № 8. с.92-94.

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

63. Сачков В.Е. Введение в комбинаторные методы дискретной математики. М.: Наука, 1983. - 384с.

64. Селютин В.А. Машинное конструирование электронных устройств.

65. М.: Советское радио, 1977, 384с.

66. Селютин В.А. Автоматизированное проектирование БИС. М.: Радио и связь, 1982. - 113с.

67. Сергиенко И.В., Рощин В.А. Один метод решения задачи о покрытии. ДАН УССР , 1983, №9, сер.А, с.73-75.

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

69. Соловьев H.A. Тесты (Теория, построение, применение). Новосибирск.: Наука. 1978.- 189с.

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

71. Соукуп И. Компоновка электронных схем. ТИИЭР, 1981. т.69, с.119-145.

72. Тетельбаум Л.Я. Последовательно-параллельный алгоритм размещения электронных компонентов. Управление системы и машины. 1977, №5. с.118-122.

73. Тетельбаум А. Я. Об одном методе оптимального размещения конструктивных единиц и внешних контактных площадок. В сб.: Автоматизация проектирования в электронике, вып. 11, "Техшка", 1975, стр. 98-103.

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

75. Толстун А.И., Мельничук И .Г., Горощенко А.Г. Программа направленной компоновки модулей. УСиМ. 1985, № 2, с. 29-33.

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

77. Фридман А., Менон П. Теория и проектирование переключательныхсхем. М.: Мир, 1978. - 580с.

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

79. Чегис И.А., Яблонский С.В. Логические способы контроля электрических схем. Труды матем. ин-та АН СССР, 1958, т.51. с.270-330.

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

81. Aurenhammer F. On-line sorting of twisted sequences in linear time. BIT28(1978), 194-204.

82. Brown A. D. Automated Placement and Routing. Computer-Aided Design, vol. 20, no. 1, pp. 39-44, January 1988.

83. E. S. David et al, "Meshach: Matrix Computations in C". Proceedings of the Center/or Mathematics and its Applications. Australian National University, vol. 32,1994.

84. Duggal R., Holland Т., Messinger H. P. A comparision of new and existing placement algorithms for auto-print circuit board layout. "Proc. Nat. Electr. Conf.'\ 1968, vol. 29, pp. 694-700.

85. Phiroze N. Parakh, Richard B. Brown, Karem A. Sakallah, "Congestion Driven Quadratic Placement", 35th DAC, 1998, pp.275-278.

86. P. R. Suaris et. al, "A quadrisection-based combined place and route scheme for standard cells". 1989. IEEE TCADICS, vol.8, no.3, pp. 234244.

87. S. Yousef, "Iterative methods for sparse linear systems". PWS Publishing Company.