Разработка и исследование моделей и алгоритмов решения Евклидовой задачи Штейнера для трассировки электрических соединений

• Автор: Орлов, Николай Николаевич
• Шифр специальности: 05.13.12, 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Таганрог
• Количество страниц: 139 с. : ил.

ОГЛАВЛЕНИЕ
Оглавление
Введение

1. Анализ методов и алгоритмов решения задачи трассировки

1.1. Постановка задачи трассировки электрических соединений

1.1.1. Г лобальная трассировка

1.1.2. Детальная трассировка

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

1.3. Анализ алгоритмов построения деревьев Штейнера в ортогональной метрике

1.4. Топологическая трассировка и гибкая прокладка соединений

1.5. Анализ топологических методов трассировки.

1.6. Выводы
2. Разработка математического обеспечения для решения задач трассировки
2.1. Разработка архитектуры процесса трассировки.
2.2. Геометрия гибкой трассировки
2.3. Постановка Евклидовой задачи Штейнера.
2.4. Построение кратчайшего соединения трх точек в Евклидовом пространстве
2.5. Вычисление координат точки Штейнера.
2.6. Определение координат точки Штейнера при построении обходов.
2.7. Кратчайшее соединение четырх точек в Евклидовом пространстве.
2.8. Кратчайшее соединение произвольного количества точек в Евклидовом пространстве.
2.9. Примеры решения Евклидовой задачи Штейнера для произвольного количества точек
2 Выводы.
3. Решение Евклидовой задачи Штейнера для неоднородных соединений
3.1. Постановка Евклидовой задачи Штейнера для неоднородных соединений.
3.2. Оптимальное соединение 3х точек в Евклидовом пространстве при условии неоднородности соединений
3.3. Решение задачи соединения источника электрических сигналов с примниками
3.4. Алгоритм решения Евклидовой задачи Штейнера для неоднородных соединений
3.5. Выводы.
4. Экспериментальные исследования и анализ разработанных алгоритмов и программ
4.1. Цель экспериментальных исследований
4.2. Этапы экспериментальных исследований.
4.3. Результаты вычислительных экспериментов и сравнение результатов работы алгоритма.
4.4. Краткое описание программной и аппаратной среды
4.5. Выводы.
Заключение
Литература


Алгоритм и программное обеспечение для решения задачи построения дерева Штейнера на этапе глобальной трассировки СБИС, позволяющие уменьшить длину соединений при проектировании СБИС. Алгоритм и программное обеспечение построения минимального связывающего дерева с учетом различной толщины соединений и наличия направленности соединений. Метод сопряжения построений Евклидовых деревьев Штейнера с построением обходов для гибкой прокладки соединений. РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной НИР «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений», а также х/д НИР по теме «Исследование алгоритмов решения Евклидовой задачи Штейнера для трассировки электрических соединений». Материалы диссертации были использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования». АПРОБАЦИЯ основных теоретических и практических результатов работы проходила на Международных научно-технических конференциях «Интеллектуальные САПР» и «Искусственные интеллектуальные системы» (г. Геленджик, - гг. Всероссийской научной конференции «Управление и информационные технологии» (г. Пятигорск, г. Всероссийской научной конференции аспирантов и студентов (г. Таганрог , - гг. Всероссийской конференции молодых ученых и аспирантов «Новые информационные технологии» (г. Таганрог, - гг. ПУБЛИКАЦИИ. По теме диссертации опубликовано 9 печатных работ. Диссертационная работа состоит из введения, четырёх глав, заключения, и списка использованных источников. Работа содержит 0 стр. СОДЕРЖАНИЕ РАБОТЫ. Во ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, сформулированы цели, дано общее описание выполненной работы. В ПЕРВОЙ ГЛАВЕ сформулирована постановка задачи трассировки электрических соединений, а также двух ее основных подзадач - глобальной и детальной трассировки. Приведена классификация и рассмотрены существующие методы и алгоритмы решения задачи построения минимальных связывающих деревьев. Сформулирована постановка задачи гибкой трассировки электрических соединений СБИС. Выполнен анализ основных преимуществ и недостатков топологических методов трассировки. Показана необходимость разработки новых методов и алгоритмов, а также математического обеспечения и моделей, позволяющих сочетать достоинства традиционных и топологических методов трассировки электрических соединений СБИС, и за счет этого повысить качество трассировки. Во ВТОРОЙ ГЛАВЕ предложена модифицированная архитектура процесса трассировки электрических соединений. Приведена математическая постановка Евклидовой задачи Штейнера. Разработана новая методика и приведены примеры ее успешного применения для решения задач построения кратчайших связывающих деревьев Штейнера в произвольной метрике. В ТРЕТЬЕЙ ГЛАВЕ описано решение задачи построения дерева Штейнера как части задачи глобальной трассировки схем при проектировании СБИС при помощи алгоритма построения минимального связывающего дерева на основе решения Евклидовой задачи Штейнера. Приведена структурная схема разработанного алгоритма. Описан алгоритм построения минимального связывающего дерева с учетом различной толщины соединений и наличия направленности соединений. В ЧЕТВЕРТОЙ ГЛАВЕ дано описание проведенных вычислительных экспериментов разработанного генетического алгоритма. Выполнена статистическая обработка полученных экспериментальных данных. Выполнено сравнение результатов работы разработанного метода с известными аналогами на основе наборов стандартных тестовых задач. Представлено описание программного обеспечения для построения минимального связывающего дерева Штейнера для задачи трассировки схем при проектировании СБИС. В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы. В приложениях приведены копии актов о внедрении и использовании разработанных алгоритмов и программ.