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

• Автор: Калашников, Роман Сергеевич
• Шифр специальности: 05.13.12, 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Таганрог
• Количество страниц: 182 с. : ил.

Содержание
Содержание.
Введение.
1. Обзор и анализ алгоритмов решения задачи Штейнера для этапов трассировки соединений ЭВА

1.1 Постановка задачи глобальной трассировки СБИС.

1.2 Постановка задачи построения дерева Штейнера для этапа глобальной трассировки СБИС

1.3 Обзор и анализ алгоритмов построения дерева Штейнера для этапа

глобальной трассировки

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

2.1 Разработка модифицированной архитектуры стратегии генетического поиска

2.2 Разработка модифицированной схемы блока параллельного эволюционного поиска

2.3 Оценка эффективности генетических операторов для разработанных
алгоритмов эволюционного моделирования
3. Разработка комбинированных генетических алгоритмов построения дерева Штейнера
3.1 Описание комбинированного генетического алгоритма СотЬЮА
3.2 Выбор методики кодирования
3.3 Разработка алгоритма создания начальной популяции.
3.4 Описание алгоритма ускоренного поиска ортогональных деревьев Штейнера РТВвА
3.5 Теоретические оценки разработанных алгоритмов.
4. Экспериментальные исследования комбинированных генетических алгоритмов построения дерева Штейнера.
4.1 Краткое описание программной и аппаратной среды.
4.2 Цель экспериментального исследования
4.3 Этапы экспериментальных исследований
4.4 Результаты экспериментальных исследований разработанного алгоритма СотЫОа
4.5 Результаты экспериментальных исследований разработанного
алгоритма РТВвА.
Заключение
Список использованных источников


Выбран оптимальный метод кодирования, наиболее приемлемый, из всех существующих, для решения ортогональной задачи построения дерева Штейнера. Разработан комбинированный алгоритм создания начальной популяции. Определены теоретические оценки временной и пространственной сложности разработанного алгоритма. В ЧЕТВЕРТОЙ ГЛАВЕ приведено описание экспериментальных исследований разработанного генетического алгоритма. Выполнена статистическая обработка полученных экспериментальных данных. Проделанные расчёты позволили подтвердить полученные ранее теоретические оценки временной и пространственной сложности разработанного алгоритма. Определены диапазоны оптимальных значений параметров генетического поиска. Выполнено сравнение результатов работы разработанного метода с известными аналогами. Представлено описание программного обеспечения для генерации, решения и исследования, различных графовых моделей схем для задачи трассировки схем при проектировании СБИС. В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы. В приложениях приведены копии свидетельства о регистрации программы и актов об использовании тексты программы для ЭВМ. Трассировка соединений является, как правило, заключительным этапом конструкторского проектирования ЭВА и состоит в определении линий, соединяющих эквипотенциальные контакты элементов, и компонентов, составляющих проектируемое устройство. Задача трассировки - одна из наиболее трудоемких в общей проблеме автоматизации проектирования ЭВА. Это связано с несколькими факторами, в частности с многообразием способов конструктивно-технологической реализации соединений, для каждого из которых при алгоритмическом решении задачи применяются специфические критерии оптимизации и ограничения. С математической точки зрения трассировка - сложнейшая задача выбора из огромного числа вариантов оптимального решения. Одновременная оптимизация всех соединений при трассировке за счет перебора всех вариантов в настоящее время невозможна. Известно большое число алгоритмов трассировки, основанных на различных методах построения, как отдельных трасс, так и цепей в целом. Важным вопросом при трассировке является построение минимальных связывающих деревьев цепей электрических схем. Основная задача трассировки формулируется следующим образом: по заданной схеме соединений проложить необходимые проводники на плоскости (плате, кристалле и т. Основными ограничениями являются ширина проводников и минимальные расстояния между ними. Определение перечня соединений. Размещение по слоям. Определение порядка соединений. Трассировка проводников. Исходная информация для первого этапа - это перечень соединений контактов каждого элемента с контактами других элементов. Одиночные контактные соединения записываются непосредственно в перечень соединений (матрицу цепей или список). Трудность при реализации возникает тогда, когда один контакт необходимо соединить с несколькими контактами. Традиционный подход к трассировке разделяют на два этапа. Первый этап называют глобальной трассировкой. На этом этапе трассируются блоки и области СБИС без определения реальной геометрической конфигурации соединений. Второй этап называют детальной трассировкой. В процессе детальной трассировки проводится поиск оптимальной геометрической конфигурации соединений между заданными блоками и областями СБИС. В отличии от глобальной трассировки, которая рассматривает полную схему, детальная трассировка рассматривает каждую область отдельно в одну единицу времени. Рассмотрим этап глобальной трассировки более подробно на примере программируемых пользователем вентильных матриц ППВМ. ППВМ включают в себя три главных программируемых элемента (рисунок 1. ПЛБ), блоки ввода-вывода (БВВ) и внутренние связи. Программируемые логические блоки являются функциональными элементами для построения логики пользователя, блоки ввода-вывода обеспечивают связь между контактами корпуса и внутренними сигнальными линиями. Программируемые ресурсы внутренних связей обеспечивают управление путями соединения входов и выходов ПЛБ и блоков ввода-вывода на соответствующие сети. Конфигурация ! Рис.