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

Проектирование — итерационный процесс, в котором чередуются процедуры синтеза и анализа. Синтез — это создание проектного решения в виде описания внешнего вида изделия, его конструктивных особенностей, структурной, функциональной или принципиальной схемы. Анализ — это оценка результатов синтеза [1].

В настоящее время наибольшее распространение при создании сложных объектов получили методы машинного (автоматизированного) проектирования. Поскольку компьютеры перестали быть редкостью, методы автоматизированного проектирования переходят в разряд инструментов, пользоваться которыми может каждый. В таких условиях технической оснащенности инженер должен обладать навыками математического и программного моделирования, а также решения задач разработки и эксплуатации аппаратуры с помощью ЭВМ. В связи с этим в промышленности широко используются различные системы автоматизированного проектирования (САПР), осуществляющие проектирование печатных плат (lili), гибридных интегральных схем (ГИС), микросборок (МБС) и других подобных конструктивов.

На этапе синтеза взаимодействие человека и ЭВМ происходит в интерактивном режиме. Основные недостатки такого подхода:

1) получение далёких от оптимальных решений;

2) возможности человека в решении задач синтеза сужаются в связи с усложнением проектируемых изделий;

3) возрастают затраты вычислительных ресурсов.

При разработке новых средств автоматизированного проектирования необходимо располагать, во-первых, критериями оценки эффективности предлагаемых методов, во-вторых, тестовыми задачами, отражающими особенности широких классов проектных задач.

К основным критериям эффективности моделей, методов и алгоритмов автоматизированного проектирования относятся:

1) точность решения задач;

2) затраты вычислительных ресурсов на решение задач, причём основной дефицит при решении задач обычно представляют затраты машинного времени.

Одним из важнейших этапов в САПР является конструкторское проектирование. На этапе конструкторского проектирования осуществляется поиск оптимального варианта конструкции, учитывающего как возможности технологической базы производства, так и удовлетворяющего требованиям технического задания. Поэтому математическое обеспечение САПР должно развиваться в направлении поиска новых более эффективных методов структурного синтеза проектных решений. Синтез — процедура, которую трудно формализовать. Формализация применяется лишь для некоторых задач в отдельных приложениях. Приведем задачу разбиения в качестве примера формализуемых процедур и, следовательно, решаемых в САПР задач. Спроектировать топологию всей СБИС целиком представляется невозможным, поскольку она может содержать несколько миллионов транзисторов, поэтому схема разбивается группированием компонентов в блоки. Результатом решения задачи разбиения является формирование множества блоков и множества соединений между блоками. В очень больших схемах используется иерархическая структура разбиения.

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

В результате решения задачи размещения для каждого блока на кристалле определяется конкретное место.

Основной результат решения задачи трассировки — конструктивная реализация связей между элементами.

В связи с трудностями создания общей математической модели, комплексно учитывающей все конструкторско-технологической особенности производства, не представляется возможным предложить алгоритм поиска оптимального конструктивного решения в едином цикле проектирования СБИС. Разработка и реализация алгоритмов и методов решения отдельных задач этапа конструкторского проектирования до сих пор остаётся актуальной проблемой. Решение этой проблемы неотъемлемо связано с развитием систем автоматизации проектирования.

Развитие моделей, методов, стратегий, алгоритмов автоматизированного проектирования СБИС нашло отражение в работах Норенкова И. П., Казеннова Г. Г., Шервани Н., Бершадского A.M., Курейчика В. М., Морозова К. К., Селютина В. А., и др. В большинстве своём разрабатываемые алгоритмы, программы и пакеты направлены на формирования базового плана кристалла (оптимизацию разбиения, размещения разногабаритных объектов) и на оптимизацию этапа трассировки соединений по критерию минимизации длины связей и занимаемой площади [3 — 5]. Из-за тесной взаимосвязи задач конструкторского проектирования и большой размерности каждой из них, а также появления новых направлений в технологии изготовления СБИС, появляется необходимость в разработке новых, методик и алгоритмов для решения данного класса задач. Для решения NP-полных задач, в которых оптимальное решение возможно найти только методами полного перебора непрерывно разрабатываются новые алгоритмы, позволяющие получать эффективные решения за приемлемое время. К таким алгоритмам можно отнести методы эволюционного поиска и генетические алгоритмы (ГА), развитие которых началось в начале 1970 гг., но только сейчас стало приоритетным в отношении других методов. В последние годы широкое распространение также получили алгоритмы, основанные на роевом интеллекте (Swarm-based optimization algorithms (SOAs)).

Поскольку данные алгоритмы и методы способны обрабатывать множество решений многокритериальной задачи одновременно, их широко применяют для решения задач в самых различных областях [6 — 25], в том числе для решения задач проектирования СБИС.

Над развитием стратегий эволюционного поиска работали такие учёные, как: Холланд Д. Х., Гольдберг Д. Е., Батищев Д. И., Букатова И. Л., Курейчик В. М., Норенков И. П., Растригин Л. А. и др. Эволюционные методы, генетические алгоритмы и алгоритмы роевого интеллекта являются одним из фундаментальных направлений научных исследований в области случайно-направленного поиска. Часто для сложной задачи необходимо найти любое решение, удовлетворяющее заданным ограничениям, поэтому целью биоинспирированных (эволюционно-генетических) алгоритмов является нахождение наилучшего, а не оптимального варианта разбиения. При этом применение других методов становится невозможным, вследствие чрезвычайной сложности решаемой задачи.

Таким образом, АКТУАЛЬНОСТЬ работы состоит в разработке новых алгоритмов и методов биоинспирированного поиска задачи разбиения схем при проектировании СБИС, позволяющих улучшить показатели качества, трудоёмкости и времени работы ЭВМ.

ЦЕЛЬ работы состоит в разработке и исследовании биоинспирированных алгоритмов для решения задачи разбиения схем при проектировании СБИС.

Для достижения указанной цели предполагается решение следующих основных задач:

1) анализ задачи разбиения при автоматизированном проектировании;

2) обоснование выбора математической модели схем для решения поставленной задачи;

3) теоретические исследования эволюционных, генетических алгоритмов, а также алгоритмов роевого интеллекта, ориентированных на решение задачи разбиения схем при проектировании СБИС;

4) построение модифицированных генетических процедур для решения задачи разбиения схем при проектировании СБИС;

5) построение новых архитектур биоинспирированного поиска ориентированных на решение задачи разбиения схем при проектировании СБИС;

6) экспериментальные исследования разработанных алгоритмов и методов, а также их сравнение с известными аналогами.

В качестве МЕТОДОВ ИССЛЕДОВАНИЯ будем использовать законы и правила теории множеств, высшей математики, элементы теории графов и гиперграфов, алгоритмы комбинаторной оптимизации и эволюционного моделирования, элементы теории статистических вычислений.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в том, что:

1) разработана трёхуровневая архитектура биоинспирированного эволюционно-генетического поиска с динамическими параметрами, оптимизирующая процесс эволюционно-генетического поиска;

2) разработан биоинспирированный алгоритм решения задачи разбиения, основанный на трёхуровневой архитектуре и использующий три алгоритма: алгоритма колонии пчёл, алгоритма генетического поиска и алгоритма эволюционного поиска;

3) на основе методов роевого интеллекта разработан алгоритм колонии пчёл, используемый в качестве методики формирования стартовой популяции хромосом, позволяющий повысить сходимость биоинспирированного алгоритма и сократить время поиска решений;

4) разработан алгоритм генетического поиска с новыми модифицированными процедурами для генетических операторов (кроссинговера, мутации, инверсии), зависящими от значений динамических параметров, повышающих устойчивость генетического поиска и качество получаемых решений;

5) разработан алгоритм эволюционного поиска, в состав которого входят эволюционные процедуры локального улучшения и преодоления преждевременной сходимости алгоритма.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

1) Методика поиска решений, которая позволяет улучшить практические результаты по сходимости алгоритма, в связи с учетом математических и статистических закономерностей при распределении элементов.

2) Новая архитектура биоинспирированного эволюционно-генетического поиска с динамическими параметрами, с помощью которой удалось оптимизировать процесс эволюционно-генетического поиска.

3) Биоинспирированный алгоритм и программа для разбиения СБИС, созданная в среде объектно-ориентированного программирования Borland С++ Builder™ 6.0.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Материалы диссертационной работы использованы в Г/б № 12 354 (1.04.01) «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», Г/б № 12 355 (12.8.08) «Разработка теории и принципов интеллектуального анализа данных при построении систем поддержки принятия решений», грант РФФИ № 12 388 (№ 08 — 01 — 473) «Разработка теории и принципов решения задач проектирования, оптимизации и принятия решений на основе биоинспирированных нечетких генетических и эволюционных методов», грант РФФИ № 12 382 (№ 09- 01 — 492) «Разработка общей теории и когнитивных принципов эволюционных вычислений», грант РФФИ № 12 383 (№ 09 — 07 -318) «Разработка новых принципов извлечения знаний на основе распределенных алгоритмов генетического программирования и роевого интеллекта», грант РФФИ № 12 389 (№ 10−01−115) «Разработка теории и принципов построения интеллектуальных интегрированных подсистем в задачах проектирования и управления», РНП 2.1.2.1652 «Разработка теории и когнитивных принципов принятии решений на основе распределенных алгоритмов, инспирированных природными системами».

Теоретические и практические результаты работы прошли АПРОБАЦИЮ на научных семинарах (с 2008 по 2011 гг., ТТИ ЮФУ), VI Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «МОЛОДЕЖЬ XXI ВЕКА — БУДУЩЕЕ РОССИЙСКОЙ НАУКИ» (г. Ростов-на-Дону, 2009), Международных научно-технических конференциях «Интеллектуальные системы» (AIS'08) и «Интеллектуальные САПР» (CAD-2008) (Дивноморское, 2008 г.), Молодежной научно-технической конференции «Интеллектуальные системы — 2009» («ИС-2009») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'09» (Дивноморское, 2009 г.), Молодежной научно-технической конференции «Интеллектуальные системы — 2010» («ИС-2010») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'10» (Дивноморское, 2010 г.), Молодежной научно-технической конференции «Интеллектуальные системы — 2011» («ИС-2011») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT' 11» (Дивноморское, 2011 г.).

ПУБЛИКАЦИИ. По теме диссертации опубликовано 14 печатных работ.

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырёх глав, заключения, и.

Заключение

.

В диссертационной работе проведены следующие теоретические и практические исследования:

1) Проведен анализ существующих методов и алгоритмов решения задачи разбиения схем при проектировании СБИС. Приведена их классификация. Выявлены достоинства и недостатки различных подходов к решению поставленной задачи.

2) Показаны основные особенности и преимущества биоинспирированного эволюционно — генетического алгоритма по сравнению со стандартными алгоритмами решения NP-полных задач (методы формирования стартовой популяции решений, способы преодоления преждевременной сходимости, работа одновременно с множеством решений и т. д.). Проведен обзор основных теоретических аспектов генетического поиска, выявлены достоинства и недостатки методов отбора решений в новую популяцию. Составлена схема генетического поиска на основе динамических параметров, используемая в качестве метода оптимизации. На основе анализа эволюционных методик предложено использование эволюционного алгоритма, в качестве процедуры преодоления преждевременной сходимости. Разработанная схема, универсальна, а следовательно, может быть использована для решения любой задачи оптимизации.

3) Для повышения качества решений, на начальном этапе работы биоинспирированного алгоритма, предложено использовать ABC — алгоритм роевого интеллекта. Для отбора решений в стартовую и последующие популяций используется «вариативный метод», состоящий из модифицированных эвристик отбора альтернативных решений: Э1, Э2, ЭЗ.

4) Предложен генетический алгоритм с модифицированными процедурами, для генетических операторов, зависящими от динамических параметров, позволяющих повысить устойчивость генетического поиска и качество получаемых решений. Для преодоления преждевременной сходимости применяется процедура «генетического всплеска». Предложен алгоритм эволюционного поиска, в состав которого входят эволюционные процедуры локального улучшения и преодоления преждевременной сходимости алгоритма (М1 и М2).

5) Проведена серия экспериментальных исследований, а также осуществлена их статистическая оценка, что позволило уточнить теоретические оценки ВСА биоинспирированного алгоритма разбиения и его поведение при разбиении схем различной структуры. Экспериментальные исследования подтверждают, что применение динамических параметров для генетических операторов в процессе биоинспирированного поиска позволяет улучшить показатели качества получаемых решений, а также преодолевать преждевременную сходимость алгоритма.

6) Для изучения характеристик биоинспирированного алгоритма разработана программа разбиения схем, использующая в качестве моделей и методов решения эволюционно-генетические алгоритмы, а также алгоритмы роевого интеллекта. Приведено ее краткое описание. Проведено сравнение результатов разработанного биоинспирированного алгоритма с результатами аналогов.

7) В результате комплексного исследования было выявлено, что улучшение работы биоинспирированного алгоритма разбиения по сравнению с ПГА составляет 3,3%. Предложенный БАР находит оптимальное решение за меньшее число итераций, т. е. эффективнее на 15,3%.

8) В качестве генератора стартовой популяции хромосом БАР использовался АВС-алгоритм. Результаты тестирования, показали, что для различных гиперграфов, среднее увеличение максимальной ЦФ составляет от 5% до 15%, а среднее увеличение минимальной ЦФ от 3%-19%. Таким образом, АВС-алгоритм позволяет повысить качество решений стартовой популяции, получает хорошие решения в задачах большой размерности, сокращая общее время работы БАР.