Введение
1 Анализ и исследование математических моделей и методов решения задачи размещения при проектировании эва на основе сбис 12
1.1 Развитие полузаказных матричных сбис 12
1.2 Иерархический подход 13
1.3 Этапы проектирования эв а 14
1.4 Анализ математических моделей схем для задачи размещения 17
1.5 Классификация критериев задачи размещения 25
1.6 Анализ методов решения задачи размещения
1.6.1 Классификация традиционных методов размещения 30
1.6.2 Метод имитации отжига 38
1.6.3 Метод имитации эволюции 41
1.6.4 Анализ достоинств и недостатков методов размещения 42
1.7 Выводы и рекомендации 45
2 Теоретические исследования факторов, влияющих на качество алгоритма размещения блоков эва 46
2.1 Анализ современного уровня проектирования интегральных схем 46
2.2 Процедура сжатия обрабатываемой информации 50
2.3 Выбор способа распределения блоков по макробластям 52
2.4 Основные понятия и термины генетических алгоритмов 56
2.5 Символьная модель задачи оптимизации 57
2.6 Функция степени приспособленности 59
2.7 Цель эволюции популяции в процессе естественного отбора 60
2.8 Оценка генетического разнообразия популяции 61
2.9 Способы создания стартовой популяции
2.10 Классификация способов образования новых особей 65
2.11 Системы скрещивания особей 69
2.12 Классификация стратегий отбора 74
2.13 Общие требования к алгоритму размещения 80
2.14 Процедура размещения макрообластей 81
2.15 Процедура размещения элементов макрообластей 82
2.16 Анализ этапа макроэволюции 85
2.17 Выбор структуры локальной сети 87
2.18 Выбор операционной системы 89
2.19 Структура поиска решения задачи размещения 91
2.20 Выводы и рекомендации 93
3 Разработка генетического алгоритма параллельного размещения 94
3.1 Анализ этапов размещения 94
3.2 Разработка механизма обмена данными в локальной вычислительной сети
3.2.1 Механизм, реализующий искусственный отбор 97
3.2.2 Механизм, реализующий естественный отбор 98
3.2.3 Обмен данными на этапе макроэволюции 99
3.3 Разработка генетического алгоритма распределения блоков эва по макрообластям 102
3.3.1 Входные данные 102
3.3.2 Начальное назначение элементов макрообластей 102
3.3.3 Выбор кандидатов для очередного этапа скрещивания 104
3.3.4 Оператор кроссинговера 106
3.3.5 Оператор мутации 107
3.3.6 Вычисление значения целевой функции 108
3.3.7 Критерий завершения процесса. 109
3.3.8 Выходные данные п0
3.4 Разработка генетического алгоритма размещения макрообластей п0
3.4.1 Входные данные 110
3.4.2 Начальное размещение макрообластей 111
3.4.3 Выбор кандидатов для очередного этапа скрещивания 112
3.4.4 Операторы кроссинговера и мутации 112
3.4.5 Вычисление значения целевой функции 112
3.4.6 Критерий завершения процесса 113
3.4.7 Выходные данные 114
3.5 Разработка генетического алгоритма окончатель ного размещения (этап макроэволюции) 114
3.5.1 Входные данные 114
3.5.2 Создание популяции для этапа макроэволюции 115
3.5.3 Операторы кроссинговера и мутации 117
3.5.4 Вычисление 3начения целевой функции 117
3.5.5 Выбор кандидатов для очередного этапа скрещивания 117
3.5.6 Обмен решениями с процессами близнецами 118
3.5.7 Критерий завершения процесса 118
3.5.8 Выходные данные
3.6 оценка результатов проектирования 119
3.7 Выводы и рекомендации 120
4 Экспериментальные исследования разработан ного алгоритма 121
4.1 Цель экспериментального исследования 121
4.2 Определение зависимости качества решения от размера популяции 122
4.3 Определение параметров для этапа размещения 136
4.4 Определение параметров миграции 137
4.5 Определение временной сложности алгоритма 140
4.6 Выводы и рекомендации 144
Заключение 146
Литература
