Разработка алгоритмов оценки и построения минимальных связывающих деревьев в САПР электронной аппаратуры

• Автор: Рыженко, Николай Владимирович
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 129 с. : ил.

Содержание.
Введение.

Глава 1. Определения и понятия

1.1 Элементы теории графов, используемые в работе.

1.2 Место минимальных связывающих деревьев в задачах САПР электронной аппаратуры.

1.3 Задача КраскалаПрима

1.4 Выводы.

Глава 2. Задача Штейнера.

2.1 Свойства деревьев Штейнера в прямоугольной метрике.

2.2 Точные алгоритмы построения деревьев Штейнера в прямоугольной метрике для задач ограниченной размерности.
2.3 Точные алгоритмы построения деревьев Штейнера в прямоугольной метрике для общего случая
2.4 Приближенные алгоритмы построения деревьев Штейнера в прямоугольной
. метрике .
2.5 Алгоритм выборки перспективных дополнительных точек
2.6 Оптимизация конфигурации дерева Штейнера.
2.7 Выводы.
Глава 3. Глобальная трассировка
3.1 Постановка задачи и стандартная методика глобальной трассировки 1
3.2 Первый этап i. Построение леса деревьев с учетом текущего распределения цепей по ребрам глобального графа.
3.3 Второй этап i. Оптимизация распределения цепей по ребрам глобального графа.
3.4 Третий этап i. Волновая трассировка
3.5 Сравнение результатов i с результатами других программ глобальной трассировки.
3.6 Выводы
Заключение.
Благодарности
Литература


Предлагаются способы устранения указанных недостатков на примере программы глобальной трассировки Pathfinder, разработанной лично автором и входящей в состав экспериментальной версии САПР научно-исследовательского проекта Ariadna. Представлен комплекс алгоритмов построения леса деревьев Штейнера, оценивающих и учитывающих возможное распределения цепей по ребрам глобального графа. Представлен комплексный алгоритм оптимизации укладки цепей по ребрам глобального графа. Приводятся результаты работы Pathfinder на тестовых задачах IBMи их сравнение с результатами работы программы глобальной трассировки Labyrinth на тех же тестовых примерах. В заключении приведены выводы по результатам диссертации. В приложение вынесены результаты различных экспериментов, относящиеся к материалу второй главы, а также описание тестовых задач глобальной трассировки IBM. Глава 1. Определения и понятия. САПР электронной аппаратуры. В третьем разделе приводится обзор и описание алгоритмов построения минимальных связывающих деревьев. Дается оценка временной сложности алгоритмов в зависимости от использования различных структур данных. Формулируется свойство единственности, использование которого позволяет строить в прямоугольной метрике минимальные связывающие деревья для точек на плоскости, с ограничением на максимальную степень точки. Элементы теории графов, используемые в работе. В разделе даются определения базовых понятий теории графов, используемые в данной работе. Приводятся некоторые свойства графов и деревьев [2, ]. Дается описание абстрактной структуры данных на основе сбалансированного бинарного дерева [1]. Формулируются задача Краскала-Прима и задача Штейнера на графе и для точек на плоскости. Оговариваются формальные упрощения, принятые в данной работе, в формулировке некоторых понятий. Графы. Определение 1. Граф есть некоторое множество вершин и некоторое множество ребер, соединяющих пары вершин. Ребра, соединяющие одну и ту же пару вершин, называются параллельными. Ребро, замыкающееся на одну и ту же вершину, называется петлей. Графы, в которых нет параллельных ребер и петель, называют простыми графами. В дальнейшем мы будем рассматривать только простые графы. Это позволяет ограничить число ребер Е заданным числом вершин V. Максимальное число ребер простого графа ? Г.(Г-1)/2. Вершине графа может соответствовать некий объект, который может иметь имя и содержать другую связанную с ним информацию. В зависимости от текущей задачи, для решения которой используются термины теории графов, вершину также будем называть узлом или точкой. Если имеется ребро, соединяющее две вершины, то эти вершины смежные по отношению друг к другу, а ребро инцидентно этим вершинам. Степень вершины есть число ребер, инцидентных этой вершине. Подграф есть некоторое подмножество вершин графа и некоторое подмножество инцидентных с этими вершинами ребер. Ребра графа могут быть ориентированными, тогда они называются дугами, и граф с такими ребрами называется ориентированным графом. Если ребра не имеют ориентации, то граф называется неориентированным. В дальнейшем мы будем рассматривать только неориентированные графы. Пути и циклы. Определение 1. Путь в графе есть последовательность вершин, в которой каждая следующая вершина (после первой), является смежной с предыдущей вершиной на этом пути. Простой путь - это путь, все вершины которого различны. Циклом называется простой путь, у которого первая и последняя вершина одна и та же. Такой путь также называют замкнутый. Простой путь, который соединяет две заданные вершины и проходит через каждую вершину графа, называется гамильтоновым. Замкнутый гамильтонов путь называют гамильтоновым циклом. Определение 1. Граф называется связным графом, если существует путь из каждой вершины в любую другую вершину графа, в противном случае граф называется несвязным. Веса и длина пути. Иногда ребрам графа Є сопоставляются (приписываются) числа, то есть ребру (у,, у,) ставится в соответствие некоторое число с», называемое весом (или мерой) ребра. Тогда граф Є называется графом со взвешенными ребрами.