Неупокоева Наталия Викторовна. Разработка и исследование интегрированных квантовых и генетических алгоритмов размещения компонентов СБИС

Краткое описание

Неупокоева Наталия Викторовна. Разработка и исследование интегрированных квантовых и генетических алгоритмов размещения компонентов СБИС : Дис. ... канд. техн. наук : 05.13.12 Таганрог, 2005 163 с. РГБ ОД, 61:06-5/1025

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ
ФЕДЕРАЦИИ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО
ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
На :рукописи
НЕУПОКОЕВА НАТАЛИЯ ВИКТОРОВНА
«Разработка и исследование интегрированных квантовых
и генетических алгоритмов размещения компонентов
СБИС»
Специальность: 05.13.12 - системы автоматизации проектирования
Диссертация иа соискание ученой степени
кандидата технических паук
Научный руководитель: д.т.н., профессор Божич В.И
Таганрог-2005
Оглавление 2
Введение 3
1. ПРОБЛЕМЫ, ПЕРСПЕКТИВЫ И АНАЛИЗ ЗАДАЧ
РАЗМЕЩЕНИЯ ПРИ КОНСТРУКТОРСКОМ ПРОЕКТИРОВАНИИ 8
ЕЕ Анализ задач размещения компонентов СБИС 8
Е2, Постановка задачи размещения 20
ЕЗ. Выводы 35
2. ИСПОЛЬЗОВАНИЕ КВАНТОВОГО И ГЕНЕТИЧЕСКОГО ПОИСКА
ДЛЯ РЕШЕНИЯ ЗАДАЧ РАЗМЕЩЕНИЯ 36
2.1. Модель задачи размещения 36
2.2. Анализ квантового и генетического поиска
при размещении элементов 44
2.3. Модифицированная архитектура генетического поиска
для размещения элементов 61
2.4. Алгоритмы анализа квантовых алгоритмов при исследовании
графовых моделей 68
2.5. Выводы 76
3. ПОСТРОЕНИЕ КОМБИНИРОВАННЫХ АЛГОРИТМОВ РАЗМЕЩЕНИЯ НА ОСНОВЕ МОДЕЛИРОВАНИЯ ОТЖИГА,
КВАНТОВОГО И ГЕНЕТИЧЕСКОГО ПОИСКА 77
3.1. Модифицированный алгоритм размещения на основе
моделирования отжига 77
3.3. Модифицированные генетические операторы для размещения 1 1 I
3.4. Выводы 119
4. АНАЛИЗ РЕЗУЛЬТАТОВ ВЫЧИСЛИТЕЛЬНОГО ЭКСПЕРИМЕНТА
ПРИ РАЗМЕЩЕНИИ ЭЛЕМЕНТОВ 120
4.1. Экспериментальные исследования квантового и
генетического алгоритма размещения 120
4.2. Анализ вычислительных экспериментов алгоритма
размещения на основе моделирования отжига 130
4.3. Описание программного комплекса для размещения
разногабаритных элементов 140
4.4 Выводы 148
ЗАКЛЮЧЕНИЕ 149
Список литературы 150
ПРИЛОЖЕНИЕ 160
АКТЫ ИСПОЛЬЗОВАНИЯ И ВНЕДРЕНИЯ РЕЗУЛЬТАТОВ РАБОТЫ 160

Список литературы

ЗАКЛЮЧЕНИЕ
1. Применение комбинированных генетических операторов, структурных моделей и различных методов поиска позволяет повысить качество и уменьшить время размещения коммутационных схем ориентировочно на 15% - 20%.
2. Построен параллельный алгоритм моделирования отжига для размещения одногабаритных и разногабаритных элементов. Предложены новые архитектуры поиска, ориентированные на размещение коммутационных схем большой размерности.
3. Разработаны квантовые и генетические алгоритмы, определения паросочетаний и генетических циклов в графовой модели. Их использование в задачах размещения увеличивает вероятность «выживания» альтернативных решений с лучшим значением целевой функции.
4. Для решения задачи размещения разногабаритных элементов был использован и модифицирован оригинальный метод Польского Выражения. Был предложен способ кодирования Обобщенного Польского Выражения, который дает возможность осуществлять видоизменение решений с помощью простых операций. Была разработана структура алгоритма, учитывая особенности решения задачи размещения разногабаритных элементов. Достоинствами предложенного алгоритма является то, что он позволяет получать качественное решение с небольшими временными затратами. В соответствии с алгоритмом разработан программный модуль.
Проведены серии экспериментов и выполнена обработка экспериментальных данных, что позволило уточнить теоретические оценки, временной сложности алгоритмов размещения. Проведенные исследования показали улучшение работы предложенных алгоритмов по сравнению с известными методами. Улучшение составило по качеству до 20%, а по времени от 10% до 15%.