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

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

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1 АНАЛИЗ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ ПО СЛОЯМ ТРАССИРУЕМЫХ СОЕДИНЕНИЙ
1.1. Выбор модели исследования
1.2. Классификация подходов к решению задачи расслоения соединений
1.3. Методы дотрассировочного расслоения
1.3.1. Распределение соединений по слоям методом пробного назначения
1.3.2. Методы учета степени “взаимодействия” связывающих деревьев
1.4. Расслоение совмещенной топологии схемы
1.5. Выводы и рекомендации
2. ИССЛЕДОВАНИЕ МЕТОДОВ ГЕНЕТИЧЕСКОГО ПОИСКА
ДЛЯ РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ ТРАССИРУЕМЫХ СОЕДИНЕНИЙ ПО СЛОЯМ
2.1. Анализ эволюционных процессов
2.1.1. Роль популяции в цепи естественного отбора
2.1.2. Стратегии формирования популяции в задачах САПР
2.1.3. Наследственные факторы и их оценка в оптимизационных задачах
2.2. Структура генетического алгоритма
2.3. Структура основных операторов генетического поиска
2.3.1 Селекция
2.3.2 Кроссинговер
2.3.3. Мутация
2.3.4. Отбор
2.4. Выводы и рекомендации

3. РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА РАСПРЕДЕЛЕНИЯ ТРАССИРУЕМЫХ СОЕДИНЕНИЙ ПО СЛОЯМ В СБИС
3.1. Формулировка задачи, основные понятия и определения
3.2. Разработка структурной схемы процесса генетического
ПОИСКА ДЛЯ ЗАДАЧ РАССЛОЕНИЯ ТОПОЛОГИИ СБИС
3.3 Генетический алгоритм распределения трассируемых
СОЕДИНЕНИЙ ПО СЛОЯМ
3.3.1 Представление хромосомы
3.3.2 Разработка процедуры определения пересечений
3.3.3 Целевая функция
3.3.4. Генетические операторы и генетический алгоритм
3.4. Теоретические оценки алгоритма
3.5. Выводы и рекомендации
4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННОГО АЛГОРИТМА РАСПРЕДЕЛЕНИЯ ТРАССИРУЕМЫХ СОЕДИНЕНИЙ ПО СЛОЯМ
4.1. Цель экспериментального исследования
4.2. Определение пространственной и временной сложности АЛГОРИТМА
4.3. Определение управляющих параметров генетического
АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ ТРАССИРУЕМЫХ СОЕДИНЕНИЙ ПО СЛОЯМ
4.4. Сравнение результатов, получаемых представленным генетическим алгоритмом распределения трассируемых СОЕДИНЕНИЙ ПО СЛОЯМ
4.5. Выводы и рекомендации
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

ВВЕДЕНИЕ

Автоматизация проектирования является важным инструментом развития научно-технического прогресса в электронной промышленности и приборостроении.
Быстро растет число успешно функционирующих систем автоматизированного проектирования (САПР). САПР - это человеко-машинная система, и объединенные в этой системе человек и машина достигают таких показателей производительности и качества проектирования, которые недоступны каждому из них порознь. Автоматизация проектирования как научно-техническое направление нацелена на эффективное решение важных и сложных научно-технических задач с меньшими трудовыми затратами, на освобождение человека от выполнения рутинной работы и творческое раскрепощение.
Автоматизация проектирования - это многоаспектная, многоуровневая проблема, охватывающая исследование, разработку, производство и эксплуатацию технических, математических, программных и информационных средств [1].
Одним из важнейших достижений человечества стало создание интегральных схем. Возникшие в 60-х годах нашего века, интегральные схемы развились, за короткое время, от объединения нескольких транзисторов до интеграции миллионов транзисторов в одной схеме. Первые интегральные схемы (ИС) представляли собой объединение одиночного транзистора с набором сопротивлений, предназначенное для выполнения какой-либо логической функции. Сейчас ИС способны выполнять сложнейшие функции, они проникли во все слои человеческого общества, современное общество не смогло бы возникнуть без использования ИС. В настоящее время, геометрические размеры элементов могут иметь размеры до 0.18 микрона (один микрон = 1.0 х 10'6 метра), для сравнения человеческий

Меру “взаимодействия” соединений можно задавать различным образом. При ортогональной прокладке соединений для каждого комплекса 1й вводится минимальный охватывающий прямоугольник ГЪ (рис. 1.13). Два комплекса 1Л и Ц) называются перекрывающимися, если:
п, Ппу*о.
Четырехслойная схема
1-секторы 1-го слоя (“вертикальные соединения”), 3-секторы 2-го слоя (“горизонтальные соединения”), 2,4-секторы 3-го и 4-го слоев (“диагональные соединения”)
Расположение комплексов
Рис.1.13.