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

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

Содержание

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

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

1.1 Классификация алгоритмов разбиения

1.2 Построение математической модели для задачи разбиения.

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

1.4 Учт тепловых характеристик.

1.5 Выводы
Глава 2 Применение методов биоинспирированного поиска для решения задачи разбиения схем при проектировании СБИС
2.1 Разработка биоинспирированных методов и принципов разбиения схем при проектировании СБИС
2.2 Методика кодирования информации в биоинспирированном алгоритме
2.3 Отличия биоинспирированных методов поиска от других оптимизационных методов
2.4 Формирование начального множества решений методом колонии пчел.
2.5 Схема биоинспирированного алгоритма разбиения элементов СБИС
2.6 Выводы
Глава 3 Построение биоинспирированного алгоритма поиска оптимальных решений в задаче разбиения
3.1 Разработка эволюционной части биоинспирированного алгоритма поиска оптимальных решений в задаче разбиения.
3.2 Разработка генетической части биоинспирированного алгоритма поиска оптимальных решений в задаче разбиения.
3.3 Разработка эвристического биоинспирированного алгоритма разбиения элементов СБИС.
3.4 Выводы
Глава 4 Разработка программной реализации и экспериментальное исследование биоинспирированного алгоритма поиска оптимальных решений в задаче разбиения.
4.1 Обзор основных пунктов меню разработанной программы разбиения схем
4.2 Цель проведения экспериментальных исследований.
4.3 Формат входного файла
4.4 Формат выходного файла гиперграфа
4.5 Порядок проведения экспериментальных исследований
4.6 Оценка результатов проведенных исследований
4.6.1 Результаты применения генетических операторов.
4.6.2 Результаты экспериментальных исследований АВСалгоритма
4.6.3 Результаты исследований для разработанного алгоритма БАР
4.7. Сравнение разработанного биоинспирированного алгоритма с аналогами
4.8 Выводы.
Заключение.
Список литературы


В связи с трудностями создания общей математической модели, комплексно учитывающей все конструкторско-технологической особенности производства, не представляется возможным предложить алгоритм поиска оптимального конструктивного решения в едином цикле проектирования СБИС. Разработка и реализация алгоритмов и методов решения отдельных задач этапа конструкторского проектирования до сих пор остаётся актуальной проблемой. Решение этой проблемы неотъемлемо связано с развитием систем автоматизации проектирования. Развитие моделей, методов, стратегий, алгоритмов автоматизированного проектирования СБИС нашло отражение в работах Норенкова И. П., Казеннова Г. Г., Шервани Н. Бершадского А. М., Курейчика В. М., Морозова К. К., Селютина В. А., и др. В большинстве своём разрабатываемые алгоритмы, программы и пакеты направлены на формирования базового плана кристалла (оптимизацию разбиения, размещения разногабаритных объектов) и на оптимизацию этапа трассировки соединений по критерию минимизации длины связей и занимаемой площади -5]. Для решения NP-полных задач, в которых оптимальное решение возможно найти только методами полного перебора непрерывно разрабатываются новые алгоритмы, позволяющие получать эффективные решения за приемлемое время. К таким алгоритмам можно отнести методы эволюционного поиска и генетические алгоритмы (I A), развитие которых началось в начале гг. В последние годы широкое распространение также получили алгоритмы, основанные на роевом интеллекте (Swarm-based optimization algorithms (SOAs)). Поскольку данные алгоритмы и методы способны обрабатывать множество решений многокритериальной задачи одновременно, их широко применяют для решения задач в самых различных областях [6 - ], в том числе для решения задач проектирования СБИС. Над развитием стратегий эволюционного поиска работали такие учёные, как: Холланд Д. Х., Гольдберг Д. Е., Батищев Д. И., Букатова И. Курейчик В. М., Норенков И. П., Растригин Л. А. и др. Эволюционные методы, генетические алгоритмы и алгоритмы роевого интеллекта являются одним из фундаментальных направлений научных исследований в области случайнонаправленного поиска. Часто для сложной задачи необходимо найти любое решение, удовлетворяющее заданным ограничениям, поэтому целью биоинспирированных (эволюционно-генетических) алгоритмов является нахождение наилучшего, а не оптимального варианта разбиения. При этом применение других методов становится невозможным, вследствие чрезвычайной сложности решаемой задачи. Таким образом, АКТУАЛЬНОСТЬ работы состоит в разработке новых алгоритмов и методов биоинспирированпого поиска задачи разбиения схем при проектировании СБИС, позволяющих улучшить показатели качества, трудоёмкости и времени работы ЭВМ. ЦЕЛЬ работы состоит в разработке и исследовании биоинспирированных алгоритмов для решения задачи разбиения схем при проектировании СБИС. В качестве МЕТОДОВ ИССЛЕДОВАНИЯ будем использовать законы и правила теории множеств, высшей математики, элементы теории графов и гиперграфов, алгоритмы комбинаторной оптимизации и эволюционного моделирования, элементы теории статистических вычислений. Методика поиска решений, которая позволяет улучшить практические результаты по сходимости алгоритма, в связи с учетом математических и статистических закономерностей при распределении элементов. Новая архитектура биоинспирированного эволюционно-генетического поиска с динамическими параметрами, с помощью которой удалось оптимизировать процесс эволюционно-генетического поиска. Биоинспирированный алгоритм и программа для разбиения СБИС, созданная в среде объектно-ориентированного программирования Borland C++ Builder™ 6. РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Материалы диссертационной работы использованы в Г/б № 4 (1) «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», Г/б № 5 (. Разработка теории и принципов интеллектуального анализа данных при построении систем поддержки принятия решений», грант РФФИ №?