Разработка и исследование комбинированного алгоритма генетического поиска и имитации отжига для задачи размещения элементов СБИС

• Автор: Ведерникова, Ольга Геннадьевна
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Ростов-на-Дону
• Количество страниц: 159 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
Г АНАЛИЗ И ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ И МЕТОДОВ ЗАДАЧИ РАЗМЕЩЕНИЯ ПРИ ПРОЕКТИРОВАНИИ
СБИС
1Л. Конструктивные особенности матричных СБИС
1.2. Иерархический подход к проектированию СБИС
1.3. Этапы проектирования СБИС
1.4. Анализ математических моделей схем для задачи размещения
1.5. Классификация критериев задачи размещения
1.6. Анализ методов решения задачи размещения
1.6.1. Классификация традиционных методов размещения
1.6.2. Метод имитации отжига
1.6.3. Метод имитации эволюции
1.6.4. Анализ достоинств и недостатков методов размещения
1.7. Выводы и рекомендации
2. ТЕОРЕТИЧЕСКИЕ ИССЛЕДОВАНИЯ ФАКТОРОВ,. ВЛИЯЮЩИХ
НА КАЧЕСТВО И СХОДИМОСТЬ АЛГОРИТМОВ ГЕНЕТИЧЕСКОГО ПОИСКА И ИМИТАЦИИ ОТЖИГА
2.1. Основные понятия и термины
2.2. Символьная модель задачи оптимизации
2.2.1 Функция степени приспособленности
2.3. Цель эволюции популяции в процессе естественного отбора
2.4. Оценка генетического разнообразия популяции
2.5. Способы создания стартовой популяции
2.6. Классификация способов образования новых особей
2.7. Системы скрещивания особей
2.7.1. Панмиксия (случайное скрещивание)
2.7.2. Инбридинг и аутбридинг
2.7.3. Ассортативное скрещивание
2.8. Классификация стратегий отбора
2.9. Оценка эффективности генетических операторов
2.10. Анализ макроэволюции
2.11. Исследование метода имитации отжига
2.11.1 Марковская модель алгоритма моделирования отжига
2.11.2. Универсальное расписание отжига
2.11.3. Начальная температура
2.11.4. Правило изменения температуры
2.11.5. Ограничивающее окно
2.11.6. Инкрементный способ вычисления значений целевой функции
2.12. Выводы и рекомендации

3. РАЗРАБОТКА КОМБИНИРОВАННОГО АЛГОРИТМА ГЕНЕТИЧЕСКОГО
ПОИСКА И ИМИТАЦИИ ОТЖИГА
ЗЛ. Математическая модель и целевая функция
3.2. Формирование кластеров
3.3. Создание начальной популяции, основанное на методе последовательного размещения по связности
3.4. Модифицированные операторы направленной мутации
3.4.1. Операторы мутации, основанные на методе релаксации
3.4.2. Операторы мутации, основанные на методе Кернигана-Лина, уменьшающие степень загруженности каналов
3.4.3. Динамические нормы случайной и направленной мутаций
3.5. Оператор кроссинговера
3.5.1. Динамическая стратегия скрещивания или подбор особей
для оператора кроссинговера
3.6. Динамический оператор отбора, основанный на методе имитации отжига
3.7. Механизм управления процессом генетического поиска
3.8. Стратегия макроэволюции
3.9. Улучшение решения после разрушения кластеров методом имитации отжига
3.10. Выводы и рекомендации
4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ РАЗРАБОТАННОГО АЛГОРИТМА
4.1. Цель экспериментального исследования
4.2. Теоретическая оценка временной сложности алгоритма
4.3. Определение пространственной и временной сложности алгоритма
4.4. Определение управляющих параметров разработанного генетического алгоритма
4.4.1. Генетические параметры
4.4.2. Параметры кластеризации
4.4.3. Параметры имитации отжига
4.5. Сравнение качества решений, получаемых разработанным алгоритмом задачи размещения элементов на плоскости
4.6. Выводы и рекомендации
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

ВВЕДЕНИЕ
При создании новой электронной аппаратуры огромное значение приобретают методы автоматизированного проектирования, которые позволяют создавать высоконадежные СБИС в короткие сроки и при сравнительно низких затратах. Стоимость кристаллов СБИС складывается из стоимости их проектирования (постоянные затраты) и стоимости производства (переменные затраты) [1,2,3]. Тенденция к росту степени интеграции СБИС приводит к существенному увеличению трудоемкости их проектирования, что вызывается ростом размерности решаемых при проектировании задач.
Производство интегральных схем разбивается на три этапа: проектирование, изготовление, тестирование. В виду значительной сложности ни один из этих этапов не может быть выполнен без средств автоматизированного проектирования. Одним из этапов проектирования СБИС является этап конструкторского проектирования, который включает в себя следующие стадии [4]: компоновка, размещение, трассировка и т.д.
Разработка методов и алгоритмов для решения задачи размещения осуществляется на протяжении многих лет, но по-прежнему является актуальной. Это связано, в первую очередь, с тем, что эта задача является ПР-полной, и разработать универсальный алгоритм, позволяющий находить точное оптимальное решение за приемлемое время затруднительно. Появление новых более совершенных средств вычислительной техники, дающих мощные вычислительные ресурсы, а также повышенные требования к проектируемым устройствам, все это является побудительной причиной разработки новых алгоритмов решения задачи размещения. Большое значение при разработке новых алгоритмов является использование метода оптимизации. Существует несколько подходов к решению ЭДР - полных задач [4,5].
К первому классу методов относятся, явным или неявным образом предусматривающие возможность экспоненциального времени работы алгоритма, такие методы, как метод ветвей и границ, линейного и нелинейного программирования, отсечения и т.д.
Ко второму классу относятся, так называемые, эвристические алгоритмы, позволяющие получать неплохие решения за приемлемое время.

оптимальным образом. После генерации заданного числа различных независимых подмножеств и их исследования заканчивается очередная итерация и начинается новая.
Алгоритм Штейнберга оперирует не парами элементов, а их группами, Экспериментальные исследования показали эффективность этого алгоритма только для задач большой размерности по сравнению с алгоритмом парных перестановок. Основной недостаток алгоритма в том, что сгенерировать на практике все максимально независимые подмножества невозможно.
В [14] рассматривается модификация алгоритма Штейнберга по критерию, учитывающему равномерное распределение трасс по КП. В основе этого алгоритма лежит утверждение о том, что хотя между элементами входящими в состав независимого подмножества элементов отсутствуют непосредственные электрические связи, но области реализации инцидентных непосредственно им цепей могут перекрываться. В результате рассматривается вид эвристических процедур, позволяющих разрешить возникшие конфликтные ситуации при размещении.
Алгоритмы «орбитального размещения», предложенные в [8], решают проблему отображения электрической схемы и заданный конструктивный базис. Этот подход основан на приведении математической модели электрической схемы к такому виду, который наиболее полно отвечает параметрам конструкции БИС и позволяет проигнорировать возможность ее физической реализации. Алгоритм осуществляет изоморфное вложение произвольного графа С, моделирующего электрическую схему в решетку, служащую моделью регулярной структуры матричной БИС. В результате в графе О выделяются подграфы Сі, изоморфно входящие в решетку. В основе алгоритма лежит теорема о том, что отображение графа О в решетку дает точное решение задачи размещения. Алгоритм строится на проверке следующих условий:
1. Локальная степень вершины искомого графа С;
2. В искомом графе отсутствуют простые циклы нечетной длины;
3. В матрице сложности искомого графа содержится не более двух строк с элементами в одноименных столбцах.
Временная сложность таких алгоритмов равна 0(а2„) - 0(а3п).
Методы случайного поиска основаны на использовании метода Монте-Карло (статических испытаний). На основе датчика случайных чисел выполняют генерацию случайных расположений элементов в позиции плоскости с запомина-