Курейчик Владимир Владимирович Биоинспирированные методы и средства автоматизированного размещения фрагментов СБИС

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

Курейчик Владимир Владимирович Биоинспирированные методы и средства автоматизированного размещения фрагментов СБИС
ОГЛАВЛЕНИЕ ДИССЕРТАЦИИ
кандидат наук Курейчик Владимир Владимирович
Введение_3

1. АНАЛИЗ ПРОБЛЕМ И ПЕРСПЕКТИВ МЕТОДОВ РАЗМЕЩЕНИЯ_14

1.1. Анализ процессов проектирования СБИС _14

1.2. Постановка задачи размещения фрагментов СБИС_20

1.3. Классификация и анализ методов размещения фрагментов СБИС_24

1.4. Краткие выводы_29

2. ПОСТРОЕНИЕ МНОГОУРОВНЕВЫХ АРХИТЕКТУР ПОИСКА_31

2.1. Графовые и гиперграфовые модели СБИС_31

2.2. Стратегии автоматизированного размещения_44

2.3. Построение трехуровневой архитектуры гибридного поиска_48

2.4. Многоуровневые архитектуры поиска_51

2.5. Краткие выводы_59

3. РАЗРАБОТКА БИОИНСПИРИРОВАННЫХ МЕТОДОВ И СРЕДСТВ ПОИСКА

3.1. Разработка методов и средств эволюционного моделирования_60

3.2. Общие положения теории биоинспирированного поиска_67

3.3. Разработка метода муравьинной оптимизации_70

3.4. Разработка метода пчелиной оптимизации_75

3.5. Разработка метода светлячковой оптимизации_79

3.6. Разработка метода обезьяньей оптимизации _85

3.7. Разработка трехуровневого гибридного алгоритма размещения_91

3.8. Краткие выводы_98

4. РАЗРАБОТКА ПРОГРАММНЫХ СРЕДСТВ И ПРОВЕДЕНИЕ ВЫЧИСЛИТЕЛЬНОГО ЭКСПЕРИМЕНТА_100

4.1. Цель и основные задачи построения программных средств_100

4.2.Описание интерфейса программной подсистемы_103

4.3. Вычислительный эксперимент_111

4.5. Краткие выводы_122

Заключение_124

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

Приложение №1_141

Приложение №2_151

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

Заключение
В ходе выполнения диссертационной работы получены следующие основные результаты:
1. Рассмотрены этапы и проведен анализ процессов проектирования СБИС, выявлены основные проблемы, обоснована актуальность разработки. Сформулирована постановка оптимизационной задачи размещения фрагментов СБИС в решетке.
2. Разработаны комбинированные стратегии, позволяющие реализовать эффективный поиск при решении задач конструкторского проектирования.
3. Разработан гибридный подход и на его основе создан трехуровневый алгоритм к решению задачи размещения фрагментов СБИС основанный на агрегации фракталов и методах биоинспирированной оптимизации, позволяющий в несколько раз сокращать размерность решаемой задачи, за счет чего уменьшается время получения набора квазиоптимальных решений.
4. Построены многоуровневые архитектуры, состоящие из методов эволюционного моделирования, методов и алгоритмов бионспирированной оптимизации, позволяющие частично решать проблемы предварительной сходимости, а также использовать иерархическую динамическую стратегию управления.
5. Описаны основные положения теории эволюционного моделирования и биоинспирированного поиска. На их основе разработаны модифицированные методы биоинспирированного поиска, ориентированные на решение задач конструкторского проектирования.
6. Разработаны модифицированные генетический, эволюционный, муравьиный, пчелиный, светлячковый и обезьяньий алгоритмы поиска оптимальных решений автоматизированного размещения фрагментов СБИС, позволяющие получать наборы квазиоптимальных решений за полиномиальное время и частично решать проблемму преждевременной сходимости.
7. Разработана программная подсистема, позволяющая проводить сравнительный анализ предложенного алгоритма с существующими аналогами на основе выполнения тестовых задач.
8. Выполнены тестирование и обработка экспериментальных данных, что позволило улучшить качество размещения в среднем до 10%, а время решения -до 5%.