Разработка параллельного генетического алгоритма размещения блоков ЭВА

• Автор: Никифоров, Алексей Михайлович
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Таганрог
• Количество страниц: 169 с. : ил

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

1 АНАЛИЗ И ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ И

МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ ПРИ ПРОЕКТИРОВАНИИ ЭВА НА ОСНОВЕ СБИС

1.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.3 ВЫБОР СПОСОБА РАСПРЕДЕЛЕНИЯ БЛОКОВ ПО
МАКРОБЛАСТЯМ
2.4 ОСИОВЫЕ ПОНЯТИЯ И ТЕРМИНЫ ГЕНЕТИЧЕСКИХ
АЛГОРИТМОВ
2.5 СИМВОЛЬНАЯ МОДЕЛЬ ЗАДАЧИ ОПТИМИЗАЦИИ
2.6 ФУНКЦИЯ СТЕПЕНИ ПРИСПОСОБЛЕННОСТИ
2.7 ЦЕЛЬ ЭВОЛЮЦИИ ПОПУЛЯЦИИ В ПРОЦЕССЕ
ЕСТЕСТВЕННОГО ОТБОРА
2.8 ОЦЕНКА ГЕНЕТИЧЕСКОГО РАЗНООБРАЗИЯ ПОПУЛЯЦИИ
2.9 СПОСОБЫ СОЗДАНИЯ СТАРТОВОЙ ПОПУЛЯЦИИ
2. КЛАССИФИКАЦИЯ СПОСОБОВ ОБРАЗОВАНИЯ НОВЫХ ОСОБЕЙ
2. СИСТЕМЫ СКРЕЩИВАНИЯ ОСОБЕЙ
2. КЛАССИФИКАЦИЯ СТРАТЕГИЙ ОТБОРА
2. ОБЩИЕ ТРЕБОВАНИЯ К АЛГОРИТМУ РАЗМЕЩЕНИЯ
2. ПРОЦЕДУРА РАЗМЕЩЕНИЯ МАКРООБЛАСТЕЙ
2. ПРОЦЕДУРА РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ МАКРООБЛАСТЕЙ
2. АНАЛИЗ ЭТАПА МАКРОЭВОЛЮЦИИ
2. ВЫБОР СТРУКТУРЫ ЛОКАЛЬНОЙ СЕТИ
2. ВЫБОР ОПЕРАЦИ1НОЙ СИСТЕМЫ
2. СТРУКТУРА ПОИСКА РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ
2. ВЫВОДЫ И РЕКОМЕНДАЦИИ
3 РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА ПАРАЛЛЕЛЬНОГО РАЗМЕЩЕНИЯ
3.1 АНАЛИЗ ЭТАПОВ РАЗМЕЩЕНИЯ
3.2 РАЗРАБОТКА МЕХАНИЗМА ОБМЕНА ДАННЫМИ В ЛОКАЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СЕТИ
3.2.1 МЕХАНИЗМ, РЕАЛИЗУЮЩИЙ ИСКУССТВЕННЫЙ ОТБОР
3.2.2 МЕХАНИЗМ, РЕАЛИЗУЮЩИЙ ЕСТЕСТВЕННЫЙ ОТБОР
3.2.3 ОБМЕН ДАННЫМИ ПА ЭТАПЕ МАКРОЭВОЛЮЦИИ
3.3 РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА РАСПРЕДЕЛЕНИЯ БЛОКОВ ЭВА ПО МАКРООБЛАСТЯМ
3.3.1 ВХОДНЫЕ ДАННЫЕ
3.3.2 НАЧАЛЬНОЕ НАЗНАЧЕНИЕ ЭЛЕМЕНТОВ МАКРООБЛАСТЕЙ
3.3.3 ВЫБОР КАНДИДАТОВ ДЛЯ ОЧЕРЕДНОГО ЭТАПА СКРЕЩИВАНИЯ
3.3.4 ОПЕРАТОР КРОССИНГОВЕРА
3.3.5 ОПЕРАТОР МУТАЦИИ
3.3.6 ВЫЧИСЛЕНИЕ ЗНАЧЕНИЯ ЦЕЛЕВОЙ ФУНКЦИИ
3.3.7 КРИТЕРИЙ ЗАВЕРШЕНИЯ ПРОЦЕССА.
3.3.8 ВЫХОДНЫЕ ДАННЫЕ
3.4 РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА РАЗМЕЩЕНИЯ
МАКРООБЛАСТЕЙ ПО
3.4.1 ВХОДНЫЕ ДАННЫЕ
3.4.2 НАЧАЛЬНОЕ РАЗМЕЩЕНИЕ МАКРООБЛАСТЕЙ
3.4.3 ВЫБОР КАНДИДАТОВ ДЛЯ ОЧЕРЕДНОГО ЭТАПА
СКРЕЩИВАНИЯ
3.4.4 ОПЕРАТОРЫ КР0ССИ1 ГОВЕРА И МУТАЦИИ
3.4.5 ВЫЧИСЛЕНИЕ ЗНАЧЕНИЯ ЦЕЛЕВОЙ ФУНКЦИИ
3.4.6 КРИТЕРИЙ ЗАВЕРШЕНИЯ ПРОЦЕССА
3.4.7 ВЫХОДНЫЕ ДАННЫЕ
3.5 РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА ОКОНЧАТЕЛЬНОГО РАЗМЕЩЕНИЯ ЭТАП МАКРОЭВОЛЮЦИИ
3.5.1 ВХОДНЫЕ ДАННЫЕ
3.5.2 СОЗДАНИЕ ПОПУЛЯЦИИ ДЛЯ ЭТАПА МАКРОЭВОЛЮЦИИ
3.5.3 ОПЕРАТОРЫ КРОССИНГОВЕРА И МУТАЦИИ
3.5.4 ВЫЧИСЛЕНИЕ ЗНАЧЕНИЯ ЦЕЛЕВОЙ ФУНКЦИИ
3.5.5 ВЫБОР КАНДИДАТОВ ДЛЯ ОЧЕРЕДНОГО ЭТАПА
СКРЕЩИВАНИЯ
3.5.6 ОБМЕН РЕШЕНИЯМИ С ПРОЦЕССАМИ БЛИЗНЕЦАМИ
3.5.7 КРИТЕРИЙ ЗАВЕРШЕНИЯ ПРОЦЕССА
3.5.8 ВЫХОДНЫЕ ДАННЫЕ
3.6 ОЦЕНКА РЕЗУЛЬТАТОВ ПРОЕКТИРОВАНИЯ
3.7 ВЫВОДЫ И РЕКОМЕНДАЦИИ
4 ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ РАЗРАБОТАННОГО АЛГОРИТМА
4.1 ЦЕЛЬ ЭКСПЕРИМЕНТАЛЬНОГО ИССЛЕДОВАНИЯ
4.2 ОПРЕДЕЛЕНИЕ ЗАВИСИМОСТИ КАЧЕСТВА РЕШЕНИЯ ОТ
РАЗМЕРА ПОПУЛЯЦИИ
4.3 ОПРЕДЕЛЕНИЕ ПАРАМЕТРОВ ДЛЯ ЭТАПА РАЗМЕЩЕНИЯ
4.4 ОПРЕДЕЛЕНИЕ ПАРАМЕТРОВ МИГРАЦИИ
4.5 ОПРЕДЕЛЕНИЕ ВРЕМЕННОЙ СЛОЖНОСТИ АЛГОРИТМА
4.6 ВЫВОДЫ И РЕКОМЕНДАЦИИ
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


При электрическом и физическом проектировании сложную ЭВА, содержащую несколько сотен полупроводниковых приборов, очевидно, нельзя рассматривать в качестве одноуровневой структуры, так как при этом постановка и решение задачи структурной оптимизации сталкивается с двумя трудностями: во-первых, слишком большое количество переменных исключает возможность применения ЭВМ с конечной памятью; во-вторых, переменные на разных уровнях имеют неравноценное влияние на обобщённый критерий качества, что заведомо приводит к большому количеству малоэффективных шагов поиска. И с функциональной, и с эксплуатационной точки зрения структура ЭВА может быть разделена на несколько уровней [. Иерархическая структура проектирования, заданная делением всей конструкции на блоки разного ранга, обеспечивает удобство проектирования, изготовления, эксплуатации и является необходимым условием для автоматизации проектирования ЭВА и применения алгоритмических методов проектирования. В проектно-конструкторских задачах применяют двухуровневое или трехуровневое рассмотрение устройства. При двухуровневом представлении элемент (гН)-го уровня рассматривают как некоторое устройство с соответствующим делением на составные элементы (компоненты) 1-го уровня. При трёхуровневом представлении элемент (1+2)-го уровня рассматривают как некоторое устройство (кристалл, чип), состоящее из макроэлементов (Ы-1)-го уровня (слои, линейки, блоки), которые в свою очередь состоят из базовых элементов 1-го уровня. Представление устройства в виде совокупности блоков разного уровня определяет формальную структурную модель, в которой каждый блок содержит блоки нижних уровней. Такой иерархический подход позволяет значительно снизить сложность задач проектирования, разбивая её на несколько подзадач, каждая из которых значительно проще и меньше размерностью. Таким образом, иерархическое деление позволяет организовать описание и хранение данных, при котором ограничение на допустимый объём оперативной памяти не нарушалось. При иерархическом подходе, в процесс проектирования добавляется этап компоновки, при котором происходит декомпозиция, или разбиение ЭВА на блоки. При проектировании ЭВА выполняется последовательность проектных процедур, которые необходимо выполнить при разработке конкретной схемы, начиная от технического задания и кончая получением информации для программно-управляемого технологического оборудования, предназначенного для изготовления фотошаблонов или непосредственно СБИС на пластине. Такая последовательность также называется маршрутом проектирования. Технологический маршрут должен обеспечивать высокое качество проектирования в приемлемые сроки. Технологический маршрут определяет разработчик ЭВА, так как процесс проектирования в значительной мере является творческим процессом. Сама же процедура проектирования не является чем-то стабильным, она изменяется динамически в связи с появлением новых конструктивно-технологических методов изготовления и требований к функциям и параметрам блоков [9]. Процесс проектирования можно разделить на электрическое и физическое проектирование. ЭВА, логическое проектирование, проектирование схем и частично полупроводниковых приборов. Физическое же проектирование имеет целью решение проблем, относящихся к микроструктуре ЭВА; это в основном проектирование топологии, т. При детальном рассмотрении этапа конструкторского проектирования, происходит его разделение на следующие основные подзадачи: планирование, размещение элементов на БМК, трассировка соединений элементов, компакция, верификация топологии. Иногда в качестве предварительного этапа перед размещением решаются вопросы компоновки (распределение элементов по макроячейкам). Конструктивное проектирование чаще всего реализуется интерактивными процедурами, т. Входной информацией для этапа конструкторского проектирования являются электрические схемы и библиотека стандартных ячеек, а выходом является топология схемы, которая состоит в определении позиций всех ячеек и определении конфигурации цепей, проложенных в соответствии с заданной электрической схемой и ограничениями на площадь кристалла. На Рис. На Рис.