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

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

Содержание

Список иллюстраций.

Введение.

Глава 1. Анализ проблем проектирования СБИС. Задача глобальной трассировки СБИС.

1.1 Современные технологии производства субмикронных СБИС

1.2 Технологические проблемы изготовления СБИС

1.3 Постановка задачи глобальной трассировки

1.4 Два подхода к решению задачи многослойной глобальной

трассировки

1.5 Обзор методов решения задачи глобальной трассировки.

1.6 Выводы
Глава 2. Разработка муравьиных алгоритмов для решения задачи трассировки на плоскости
2.1 Многоуровневый подход к решению задачи трассировки.
Трассировка по всему кристаллу.
2.2 Биоинспирированные методы.
2.3 Муравьиный алгоритм решения задачи глобальной трассировки
простыми формами.
2.4 Муравьиный алгоритм глобальной трассировки для соединений
сложной конфигурации.
2.5 Выводы
Глава 3. Разработка генетического алгоритма распределения соединений по слоям при глобальной трассировке
3.1 Постановка задачи распределения соединений по слоям.
3.2 Генетические алгоритмы
3.3 Генетический алгоритм распределения соединений по слоям.
3.4 Иерархическая структура генетического поиска.
3.5 Дополнительные модификации иерархического генетического
алгоритма.
3.6 Выводы.
Глава 4. Практическая реализация разработанных алгоритмов. Экспериментальные и теоретические исследования.
4.1 Цель экспериментальных исследований
4.2 Теоретические исследованияэазработанных алгоритмов
4.3 Библиотека для использования генетических алгоритмов СЛ1лЬ.
4.4 Библиотека параллельного программирования РРЬ.
4.5 Описание комплекса программных продуктов.
4.6 Экспериментальные исследования с помощью комплекса
программных продуктов.
4.7 Выводы.
Заключение
Список литературы


При трассировке реализуются связи между выводами элементов. Компакция подразумевает уменьшение площади схемы, если это возможно. При уменьшении одного чипа становится возможным размещение большего количество чипов на одной подложке. Кроме того, уменьшается длина связей и временные задержки [5], [9]. На последнем этапе проводится верификация топологии спроектированной схемы. Она заключается в проверке геометрических размеров, ограничений, временных задержек и других параметров, влияющих на работоспособность схемы. Эти тенденции ведут к возрастанию значения трассировки при конструкторском проектировании, требуют разработки новых методов получения более качественных решений на этом этапе [5], [7], []. Сложность задачи трассировки ведет к постоянному поиску новых методов и подходов к ее решению. Перспективным для исследований является научное направление с названием «Природные вычисления» (Natural Computing), объединяющее математические методы, в которых заложены принципы природных механизмов принятия решений. К таким методам можно отнести, прежде всего, методы моделирования отжига, методы эволюционного моделирования, генетические алгоритмы, методы эволюционной адаптации, алгоритмы роевого интеллекта, а также муравьиные (Ant Colony Optimization - АСО) и пчелиные (Bee Colony Optimization - ВСО) алгоритмы [], []. В основе муравьиных алгоритмов лежит имитация самоорганизации муравьиной колонии. Каждый отдельный агент действует по очень простым правилам, в то время как вся многоагентная система способна решать сложные задачи. Эффективность муравьиных алгоритмов сравнима с эффективностью общих метаэвристических методов, а в ряде случаев - и с проблемно-ориентированными методами. Наилучшис результаты муравьиные алгоритмы показывают для задач с большими размерностями областей поиска. Муравьиные алгоритмы хорошо подходят для применения вместе с процедурами локального поиска, позволяя быстро находить начальные точки для них. Первой задачей, успешно решенной с помощью муравьиного алгоритма, была задача коммивояжера. Как показывают опыты, применение муравьиного алгоритма также приводит к положительным результатам при решении задач на различных этапах конструкторского проектирования, в частности, задачи трассировки, позволяя улучшать качество решений. Еще один класс алгоритмов, приводящих к улучшению качества получаемых решений для задач трассировки - это генетические алгоритмы (ГА). ГА это эвристические алгоритмы поиска, используемые для решения задач оптимизации. Они являются разновидностью эволюционных вычислений, моделирующей методы естественной эволюции, такие как наследование, мутацию, кроссинговер. ГА основаны на селекции лучших особей из полученной популяции решений. ГА широко применяются для решения задач в самых различных областях, в том числе для решения задач конструкторского проектирования СБИС [-]. ГА имеют следующие отличия от других оптимизационных и поисковых процедур: осуществляют поиск из множества точек, а не из единственной точки; используют целевую функцию, а не ее различные приращения; для оценки информации используют не детерминированные, а вероятностные правила; дают не одно решение, а целый спектр решений. Гибкость структуры генетических алгоритмов, возможность её настройки и перенастройки дают возможность получения структур, обеспечивающих получение высокого результата []. Стоит отметить, что наилучшие результаты могут быть достигнуты при использовании нескольких различных алгоритмов на различных этапах решения задачи. При разбиении задачи на этапы упрощается процедура поиска для каждой отдельной части, кроме того, есть возможность подобрать оптимальную модификацию алгоритма именно для конкретного этапа, поскольку локализуется каждая из промежуточных задач. Также стоит упомянуть, что популярным в последнее время стало использование гибридных алгоритмов, основанных на совмещении различных теорий. Из вышесказанного видно, что тема работы, связанная с разработкой нового метода решения задачи глобальной трассировки на основе моделирования природных систем, является АКТУАЛЬНОЙ.