Исследование и разработка алгоритмов канальной трассировки цепей различной ширины в СБИС

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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ ммниниЧимч ммммммммоммчимнмммммимиммммЗ

1. СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ КАНАЛЬНОЙ ТРАССИРОВКИ ЦЕПЕЙ РАЗЛИЧНОЙ ШИРИНЫ В СБИС

1.1. Постановка задачи канальной трассировки цепей в СБИС.

1.2. Исследование бессеточного алгоритма канальной трассировки СБИС.

1.3. Анализ генетических методов

1.4. Применение алгоритмов адаптации в методах генетического поиска.

1.5. Выводы.

2. РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА КАНАЛЬНОЙ ТРАССИРОВКИ ЦЕПЕЙ РАЗЛИЧНОЙ ШИРИНЫ В СБИС

2.1. Постановка задачи

2.2. Целевая функция

2.3. Принципы кодирования и декодирования хромосом
2.4. Принцип создания массивов горизонтальных и вертикальных максимумов 2.5 Создание начальной популяции.
2.6. Структурная схема генетического алгоритма
2.7. Модифицированные генетические операторы
2.8. Теоретические оценки алгоритма.
2.9. Выводы.
3. РАЗРАБОТКА ГЕНЕТИЧЕСКОГО ОПЕРАТОРА НА ОСНОВЕ ПРОЦЕДУР АДАПТАЦИИ.
3.1. Генетический оператор адаптации
3.2. Структурная схема алгоритма адаптации
3.3. Формирование объекта адаптации.
3.4. Целевая функция
3.5. Модель объекта адаптации.
3.6. Методика выработки управляющих сигналов
3.7. Пример работы оператора адаптации
3.8. Теоретические оценки оператора адаптации
3.9. Выводы
4. РАЗРАБОТКА ПРОГРАММНОЙ РЕАЛИЗАЦИИ И ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ.
4.1. Цель экспериментального исследования
4.2. Описание работы с программой
4.3. Формат входного и выходного файла канала СБИС
4.4. Этапы проведения экспериментальных исследований.
4.5. Результаты экспериментальных исследований.
4.6. Сравнение результатов исследования разработанных алгоритмов с результатами аналогов.
4.7. Выводы и рекомендации.
ЗАКЛЮЧЕНИЕ в .
ЛИТЕРАТУРА


АПРОБАЦИЯ основных теоретических и практических результатов работы проходила на Международной научно-технической конференции «Интеллектуальные САПР - », (г. Геленджик, г,) Сорок шестой студенческой научной конференции (г. Таганрог, г. Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (г. Таганрог, г. Четвертой всероссийской научной конференции с международным участием молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (г. Таганрог, г. ПУБЛИКАЦИИ. Результаты диссертации отражены в 7 печатных работах. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 7 стр. СОДЕРЖАНИЕ РАБОТЫ. ВО ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, сформулированы цели, дано общее описание выполненной работы. В ПЕРВОЙ ГЛАВЕ приведена постановка задачи канальной трассировки цепей различной ширины. Рассмотрены основные алгоритмы решения задачи канальной трассировки в СБИС. Выявлены их достоинства и недостатки. Описаны методы генетического поиска, основные генетические операторы, их отличие от других оптимизационных и поисковых методов. Рассмотрен эволюционный алгоритм адаптации. ВО ВТОРОЙ ГЛАВЕ описан комплекс алгоритмов для решения задачи канальной трассировки СБИС. Приведена структурная схема генетического алгоритма. Показана структура и принципы представления информации для генетического алгоритма. Разработаны алгоритм формирования начальной популяции, целевая функция качества получаемых решений, модифицированные генетические операторы, теоретическая оценка алгоритма. В ТРЕТЬЕЙ ГЛАВЕ приведена реализация алгоритма адаптации в общей схеме генетического поиска. Описаны структура и назначения автоматов адаптации, методика выработки управляющих сигналов. Показана структурная схема генетического алгоритма с алгоритмом адаптации в качестве одного из генетических операторов. В ЧЕТВЕРТОЙ ГЛАВЕ описаны основные функции программы генетического алгоритма канальной трассировки. Поставлены цели экспериментального исследования. Определены оптимальные параметры, управляющие генетическим поиском. Произведена экспериментальная оценка пространственной и временной сложности алгоритма. Полученные оценки позволили подтвердить полученные ранее теоретические оценки ВСА и ПСА. Выполнено сравнение результатов работы разработанного алгоритма канальной трассировки СБИС с известными аналогами. СБИС. В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы. В приложении даны копии свидетельства о регистрации программы, актов об использовании, графический интерфейс программного обеспечения, примеры решения задачи канальной трассировки цепей с одинаковой и разной шириной цепи. Трассировка - это процесс соединения выводов в соответствии с налагаемыми ограничениями [3]. Трассировка интегральных схем (ИС) и сверхбольших ИС (СБИС), таких как многокристальные модули (МКМ) разделяются на глобальную (назначение цепей в определенные регионы) и детальную трассировку (прокладка соединений внутри областей). Детальная трассировка разделяется на трассировку коммутационных блоков и трассировку каналов (рис. Канальные алгоритмы базируются на возможности в некоторых случаях регулярного разбиения коммутационного поля на каналы и трассировки внутри каналов с помощью горизонтальных и вертикальных отрезков. Основная задача канальной трассировки формулируется следующим образом: по заданному расположению выводов проложить необходимые проводники, чтобы реализовать заданные электрические соединения с учетом заранее установленных ограничений [1]. Канал - это область трассировки, ограниченная двумя параллельными рядами контактов. Верхний и нижний ряд часто называют верхней и нижней границами канала. Каждому контакту присваивается номер цепи, которая к нему подходит (рисунок 1. Контакты, значение которых равно нулю называют вакантными или незанятыми контактами. Выводы, принадлежащие одной цепи, должны быть соединены в соответствии с налагаемыми ограничениями [4].