автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Исследование и разработка методов разбиения схем на основе адаптивных генетических процедур

На правах рукописи

ПОЛУПАНОВ Алексей Александрович

УДК 681.3

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ РАЗБИЕНИЯ СХЕМ НА ОСНОВЕ АДАПТИВНЫХ ГЕНЕТИЧЕСКИХ ПРОЦЕДУР

Специальность 05.13.12 - « системы автоматизации проектирования »

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

Таганрог 2003

Работа выполнена в Таганрогском Государственном Радиотехническом Университете (ТРТУ)

Научный руководитель:

д-р техн. наук, проф. Б. К. Лебедев

Официальные оппоненты:

д-р техн. наук, проф. В. П. Карелин канд. техн. наук, доц. С. М. Ковалёв

Ведущее предприятие:

Федеральное Государственное

Унитарное Предприятие Таганрогский НИИ Связи (г. Таганрог)

Защита состоится " 27 " июня 2003 г. в 1400 на заседании диссертационного совета Д 212.259.03 по защите диссертаций при Таганрогском Государственном Радиотехническом Университете по адресу: 347928, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406

С диссертацией можно ознакомиться в библиотеке Таганрогского Государственного радиотехнического университета.

Автореферат разослан " {6 " мая 2003 г.

Ученый секретарь диссертационного совета д-р техн. наук, проф.

А. Н. Целых

О?-А

М

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Использование систем автоматизированного проектирования (САПР) разного уровня, способствует повышению степени интеграции СБИС на уровне узлов, блоков и всей системы в целом. Сегодня СБИС способны выполнять сложнейшие наборы функции, а геометрические размеры транзисторов сократились до 0.18 микрона!

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

К таким можно отнести методы эволюционного моделирования, которые были разработаны, как новое направление, в начале 1970 гг., но только сейчас приобрели приоритет в отношении других методов. Значительный вклад в области эволюционного моделирования внесли: Goldberg D.E., Holland J.H., Батищев Д.И., Букатова И.Л., Курейчик В.М. и многие другие учёные. Сравнительно недавно, их начали широко применять для решения задач в самых различных областях, в том числе для решения задач при проектировании СБИС, поскольку эти методы применимы в нелинейных задачах высокой размерности, при отсутствии требований к дифференцируемости оптимизируемой функции или полноты знаний о решаемой проблеме, а также способны обрабатывать множество решений при учёте множества критериев. Данными свойствами обладают генетические

I ,"JC. НАЦИОНАЛЬНАЯ j

j БИБЛИОТЕКА I

{ С.Петерфгрг j, у |

» 03 700*i акт/* f- [

алгоритмы (ГА) — адаптивные поисковые алгоритмы, основанные на механизмах натуральной селекции и генетики, работающие с популяциями решений методом эволюционного поиска. Основная цель ГА - абстрактно и формально > объяснить адаптацию процессов в естественных системах и спроектировать искусственные программные системы, которые' содержат основные механизмы естественных систем. Основная тема поиска ГА — поиск баланса между эффективностью и качеством для "выживания" в различных условиях. Эффективность ГА определяется способностью преодолевать локальные оптимумы, устойчивостью генетического поиска, временем его работы, которая с возникновением новых тенденций в технологии изготовления СБИС, оставляет желать лучшего.

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

Целью диссертационной работы является исследование и разработка методов разбиения схем при проектировании СБИС на основе модифицированных структур генетического поиска с элементами адаптации. Основная задача состоит в разработке алгоритма разбиения схем при проектировании СБИС по критерию суммарного числа внутренних (внешних) связей, а также тепловой совместимости элементов, позволяющих повысить качество решений для задач большой размерности, оценке качества применяемых методов, генетических алгоритмов и получаемых в результате их работы решений.

Для достижения поставленной цели были выполнены следующие

этапы.

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

2. Разработан новый проблемно-ориентированный генератор стартовой популяции (ГХСВ), использующий знания о решаемой задаче и позволяющий генерировать хромосомы, содержащие группы "сильносвязанных" генов, что позволило повысить качество получаемых решений и сократить время работы алгоритма.

3. Выполнен анализ основных генетических операторов с точки зрения их пригодности и эффективности для решения поставленной задачи.

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

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

6. Разработана структурная схема генетического алгоритма разбиения гиперграфов на подгиперграфы с элементами адаптации (ГАСЭА) для задачи разбиения схем при проектировании СБИС.

7. Выполнены экспериментальные исследования разработанного проблемно-ориентированного генератора стартовой популяции решений (ГХСВ), блока модифицированных процедур генетических операторов, разработанного алгоритма (ГАСЭА), а также сравнение его с известными алгоритмами разбиения.

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

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

1. Предложенном алгоритме формирования стартовой популяции хромосом, содержащих группы "сильносвязанных" генов, что позволяет повысить сходимость алгоритма и сократить время поиска решений.1

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

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

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

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

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

3. Генетический алгоритм с элементами адаптации и программное обеспечение (ПО) для разбиения схем при проектировании СБИС, с полиномиальной временной сложностью, разработанное под наиболее популярное семейство 32-разрядных операционных систем Windows® 9х/МЕ/2000/ХР фирмы Microsoft Corporation, созданное в среде объектно-ориентированного программирования Borland С++ Builderм 5.0.

Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе « Разработка интеллектуальных систем проектирования на основе эволюционной адаптации » (.№ ГР 1.8.96), г/б « Разработка теории и ■ принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений» (№ ГР" 1.04.01), х/д между ТРТУ и Российским научно-исследовательским институтом информационных технологий и систем автоматизированного проектирования (Рос НИИ ИТ и АП) «Разработка эволюционных алгоритмов на графах с динамическими параметрами »(№ 12301).

Научные результаты, представленные в диссертации используются в НИИ ТКБ ТРТУ по договору №710/98-16002-7 «Участие в разработке технических предложений по созданию РИС и алгоритмов её функционирования», а также в учебном процессе на кафедре САПР ТРТУ при чтении лекций по курсу "Методы оптимизации", "Методы генетического поиска" и в цикле лабораторных работ по курсу "Автоматизация конструкторского проектирования СБИС".

Основные положения. выносимые на защиту:

1. Алгоритм формирования стартовой 'популяции, применяемый в генераторе хромосом содержащих группы "сильносвязанных" вершин (ГХСВ) и использующий знания о решаемой задаче.

2. Модифицированная процедура реализации генетических операторов на основе динамических параметров.

3. Подход к решению задачи разбиения схем, основанный на адаптивной архитектуре генетического поиска с динамическими параметрами.

4. Архитектура разработанного генетического алгоритма с элементами адаптации (ГАСЭА), применимая не только для задачи разбиения схем.

Апробация работы и публикации. Основные теоретические и практические результаты работы представлены на научных семинарах (с 2000 по 2003 гг., ТРТУ), V, VI Всероссийской научно-технической конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (г. Таганрог, 2000 г., 2002 г.), XVII Международной научно-технической конференции "Интеллектуальные САПР" (г. Геленджик, 2002 г.), Пятой Всероссийской научной конференции молодых учёных и аспирантов "Новые информационные технологии. Разработка и аспекты применения" (г. Таганрог, 2002 г.).

По теме диссертации опубликовано 8 печатных работ.

Структура и объём диссертационной работы. Диссертация состоит из введения, четырёх глав, списка использованных источников и приложений. Работа содержит 173 страниц, включая 69 рисунков, 18 таблиц, список

использованных источников из 107 наименований, 17-страниц приложений и актов об использовании.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность диссертационной работы, сформулированы цели работы, приведены сведения о полученных научных и практических результатах, реализации и внедрении результатов работы, апробации, а также дано общее описание выполненной работы.

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

Поскольку СБИС может содержать несколько миллионов транзисторов, то невозможно спроектировать топологию всей схемы целиком в связи с ограниченными возможностями вычислительных средств, поэтому схема 'разбивается группированием компонентов в блоки. В результате разбиения формируется множество блоков и множество соединений между блоками. Задача разбиения схемы состоит в нахождении такого разбиения к из множества возможных разбиений К некоторого гиперграфа Н (либо графа в), при котором минимизируется (либо максимизируется) некоторая величина Е, являющаяся весовой функцией разбиения, и учитываются все поставленные в задаче ограничения.

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

Задача разбиения является задачей комбинаторно-логического типа, решаемая полным перебором. Существующие методы её решения базируются на сокращённом переборе некоторого множества допустимых решений, в связи с чем, полученное в итоге разбиение схемы обычно не является оптимальным, а лишь приближено к нему. Рассмотренные алгоритмы обладают временной сложностью (ВСА) от 0(ап2) до Офп4), поэтому разрабатываемый алгоритм должен обладать ВСА не выше, чем

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

Для формализации задачи разбиения схем при проектировании СБИС, производится переход от реальной схемы, к гиперграфовой математической модели Н = (X, Е), где элементам схемы соответствуют вершины гиперграфа X = {х,- | /' = 1, 2, ..., и}, а электрическим цепям - гиперрёбра Е = | с X, у = 1, 2,..., /и}, причём вес вершин задаётся множеством Ф = {<р,-1 / = 1, 2,..., я}, а вес рёбер — множеством \|/ = {щ |у = 1, 2,..., т). Таким образом, постановка задачи разбиения схем ■ в этом случае будет определяться, как задача оптимизации, и выражается формулой:

к т

максимизировать Р = ^ ^ И уЦ/ , (1)

7=1

где Л,-,, - булева переменная равная 1, если гиперребро е} назначено в узел г,, и равная 0 в противном случае.

Учёт тепловой совместимости элементов осуществляется на основе знания тепловой мощности рассеивания каждого элемента и введении последующих ограничений для формируемых блоков:

п

^УпР, - Рг> У=,''2> (2)

1=1

где у ¡у - булева переменная равная 1, если вершина х! назначена в узел г* и равная 0 в противном случае; - максимально допустимый суммарный вес вершин, назначенных в у-й узел; V- количество узлов разбиения.

Кроме того, вводятся дополнительные ограничения:

к

Хя. =1; '=1.2,..., и;

X Уп, - V ■/= 1'2'!'2,..., А,

где ©(е,) - мощность множества т. е. ©(е,) = | е11, а /( = {/1 е е(}.

Основные недостатки существующих алгоритмов разбиения схем заключаются в получении решений, далёких от оптимальных, особенно в задачах большой размерности, а также попадании их в локальные "ямы" из которых зачастую они не могут выйти. Перечисленные недостатки практически отсутствуют у алгоритмов, основанных на методах эволюционного моделирования - генетических алгоритмах (ГА). Тем не менее, анализ показывает, что актуальным является вопрос, связанный с повышением эффективности ГА, в плане повышения устойчивости генетического поиска, времени работы и качестве получаемых решений.

В результате проведённого анализа существующих методов и алгоритмов разбиения схем, выявляется необходимость в повышении

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

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

Основные отличия ГА от других оптимизационных и поисковых методов заключаются в следующем:

а) ГА работают не с параметрами, а закодированным множеством параметров;

б) поиск осуществляется не из одной, а из множества точек;

в) для оценки информации используется целевая функция, а не её приращения; •

г) при работе ГА используют вероятностные, а не детерминированные правила.

ГА работает до тех пор, пока не пройдет заданное число итераций, либо не будет получено решение, удовлетворяющее заданным критериям. В отличие от остальных оптимизационных методов, ГА более приспособлены для нахождения новых решений за счёт объединения квазиоптимальных решений из разный популяций и обладают возможностями для выхода из локальных оптимумов.

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

В ГА для создания стартовой популяции решений используют следующие основные стратегии:

♦ стратегия "одеяла" - исходное множество включает все возможные варианты решений;

♦ стратегия "дробовика" (случайная генерация) - исходное множество включает в себя достаточно много, но не все возможные варианты;

♦ стратегия фокусировки - исходное множество решений состоит из разновидностей одного решения.

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

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

Одним из методов повышения эффективности генетического поиска (ГП) является переход к алгоритмам с динамическими параметрами или элементам адаптации. Эффективность данного подхода объясняется тем, что в природе отсутствуют жёсткие связи. Возможность динамического (т. е. в процессе работы алгоритма) изменения параметров алгоритма, правил репродукции, селекции, процедур генетических операторов, позволяет популяции адаптироваться к изменениям "окружающей среды". Таким образом, ГА получает отклик от "окружающей среды" на основе которого возможно внесение изменений в ход генетического поиска.

Разработанный ГАСЭА (рис.1), основан на архитектуре простого ГА, но отличается от такового проблемно-ориентированным генератором стартовой популяции, введением элементов адаптации, а также нестандартной архитектурой генетического поиска. К элементам адаптации относятся:

• динамически изменяемый параметр п в ходе работы алгоритма,

отвечающий за:

- кратность выполнения каждого генетического оператора (ГО);

- размер подпопуляции хромосом отбираемых для каждого ГО;

• адаптивная архитектура генетического поиска, содержащая блок

адаптации, который управляет процессом ГП и принимает решения о:

- изменении параметра п, с целью получения "хороших" хромосом;

- замене заданного количества хромосом текущей популяции новыми хромосомами.

Устойчивость генетического поиска в ГАСЭА повышается за счёт элементов адаптации и так называемого принципа многодетной семьи, заключающегося в многократном применении ГО к одной и той же выбранной паре родителей, стремящейся получить потомков, лучше своих родителей в смысле ЦФ, используя параметр п.

Рис. 1. Структурная схема генетического алгоритма с элементами адаптации

(ГАСЭА).

Кроме того, разработанный алгоритм легко преодолевает локальные оптимумы, используя метод "встряски", заключающийся в разбавлении

определённой части популяции новыми хромосомами на основе случайной генерации.

Приведём основные особенности разработанных блоков, входящих в структуру ГАСЭД.

Генератор хромосом с группами "сильносвязанных" вершин (ГХСВ) — выполняет генерацию стартового множества (популяции), хромосом, на основе предварительного анализа матрицы инцидентности исходного гиперграфа, с целью повышения целевой функции отдельно взятой хромосомы и, следовательно, повышения средней целевой функции всей популяции. Таким образом, алгоритму требуется меньшее число итераций, т. е. сокращается время решения задачи.

Для нахождения "сильносвязанных" групп вершин необходимо произвести анализ матрицы инцидентности Ин с целью нахождения размера группы и конкретных вершин, принадлежащих искомой группе.

На первом шаге вычисляется суммарное число связей или локальная степень ¡-й вершины как сумма ¡-го элемента с ]-м элементом, по всем ¡-м элементам ряда матрицы инцидентности Км (сумма всех связей):

^ = • (3)

/=1

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

Е^/я, (4)

7=1

где и - количество вершин исходного гиперграфа.

Далее производится выбор всех вершин, локальная степень которых больше либо равна средней локальной степени плюс константа Д:

3Х1>$Хср + /3,гае0=1. (5)

Таким образом, сколько таких вершин будет выбрано, такой и будет размер "сильносвязанной" группы вершин, который изменяется в зависимости от параметра Д. Увеличивая параметр Д уменьшается размер "сильносвязанной" группы и наоборот, уменьшая параметр Д-увеличивается размер "сильносвязанной" группы вершин, что и используется в ГХСВ для генерации "хороших" хромосом.

Таким образом, "сильносвязанная" группа вершин g представляется в виде шаблона Н, который располагается в произвольной части хромосомы (рис.2), а остальная часть хромосомы заполняется недостающими генами на основе случайной генерации.

Группаg = {4, 5, 8} => шаблон Н = {4, 5, 8};

Хромосома:

4 3 * * * * *

Рис. 2. Генерация хромосомы на основе шаблона.

Модифицированные процедуры применяемы в ГО — процедуры для каждого генетического оператора, использующие принцип многодетной * семьи й зависящие от динамических параметров, целью которых является получение "хороших" потомков относительно родителей. .

Локальное улучшение решений — эвристика, выполняемая на каждой итерации алгоритма, вырабатывающая "хорошие" решения, исходя из анализа, текущей популяции, подпопуляции, либо отдельных хромосом. Результатом работы является новое решение, полученное модифицированной процедурой для оператора мутации.

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

Блок адаптации — анализирует ход решения задачи и вносит коррективы в организацию процесса генетического поиска. Например, блок адаптации1 может менять архитектуру самого поиска (включать / отключать какой-либо блок), менять размер подпопуляции, способ получения популяции в нужный момент времени, а также изменять динамические параметры ГА.

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

В четвёртой главе составлен план проведения экспериментов, сформулирована цель исследований, проведено тестирование проблемно-ориентированного генератора стартовой популяции решений, блока ГО, разработанного алгоритма (рис.1), по различным показателям.

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

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

Здесь же приведены сравнительные характеристики с существующими алгоритмами разбиения схем. В качестве тестовых примеров использованы случайно-сгенерированные графовые схемы, размерностью от 50 до 500 вершин и гиперрёбер, а также стандартные бенчмарки (benchmarks) некоторых схем. Основной целью исследований являлось выявление улучшений по качеству получаемых решений, времени работы алгоритма, устойчивости и инертности к локальным оптимумам. Тестирование выполнялось с использованием схем 19ks компании Hughes Aircraft Company (содержащей 2684 элемента и 3282 цепи), PrimGAl и PrimGA2 (из Microelectronics Center of North Carolina), а для адекватного сравнения ПО, использовались стандартные оценки производительности различных систем, представленные фирмой Intel®.

Минимальные системные требования для нормального функционирования ПО - процессор не ниже AMD® 5x86, объём оперативной памяти - 16MB, объём дисковой памяти - 2 MB (желательно 4.3 MB) плюс место на диске под временные файлы и файлы статистики (отчёта), зависящие от размерности поставленной задачи.

Все эксперименты проводились на IBM® совместимом компьютере с процессором Intel® Pentium® II \ 400 MHz и оперативной памятью 320 MB DIMM РС-133. Например, разбиение схемы на компьютере указанной конфигурации, содержащей 20 элементов и 27 цепей, потребовало 6 секунд процессорного времени (для 100 итераций).

Проведённые комплексные исследования показали улучшение работы алгоритма по сравнению с ПГА от 3% до 7%, в зависимости от вида задачи. В задачах с числом элементов более 100, разработанный алгоритм ГАСЭА по качеству получаемых решений, выглядел значительно лучше (в среднем от 5% до 7%).

По сравнению с существующими алгоритмами разбиения, алгоритм ГАСЭА, имеющий практическую реализацию, в некоторых случаях достигал улучшения, позволяющие сократить сроки проектирования СБИС на 3-5%.

В заключении приводятся основные результаты, полученные в диссертационной работе.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

• В результате, выполненных теоретических и í практических" исследований по теме диссертационной работы реализованы следующие научные и практические положения:

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

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

3. Разработан проблемно-ориентированный генератор хромосом стартовой популяции, повышающий качество получаемых решений на начальном этапе работы алгоритма. Созданы модифицированные процедуры для ГО, зависящие от динамических параметров, позволяющие повысить устойчивость ГП и качество получаемых решений. Теоретически определена оценка ПСА, ВСА применяемых генетических операторов и алгоритма в целом. Оценка ПСА составляет 0(ап2) (где а. - коэффициент, зависящий от текущих динамических и дополнительных параметров алгоритма), а ВСА модифицированных процедур для ГО и ГАСЭС не выше 0(Рп2) (где р -коэффициент, зависящий от текущих параметров алгоритма (размера популяции, вероятностей ГО, динамических параметров и т. п.)), что ниже либо равно ВСА многих из существующих равнозначных методов.

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

ÏO£74 1

2.00J-/I

» 1 06 74,,

i6

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

1. Гладков Л.А., Полупанов A.A. Самоорганизующийся генетический алгоритм — эффективный способ достижения оптимума // Тезисы докладов V Всероссийской научной конференции студентов и аспирантов. Таганрог: изд-во ТРТУ, 2000. с. 103

2. Лебедев О.Б., Полупанов A.A. Разбиение графов на основе нейросетевого моделирования // Тезисы докладов. Известия ТРТУ №4(22), Интеллектуальные САПР. Таганрог, 2001. с. 360

3.Лебедев Б.К., Полупанов A.A. Генетический алгоритм компоновки с элементами самоорганизации. Статья. Известия ТРТУ №3(26), Интеллектуальные САПР. Таганрог, 2002. с. 62

4. Полупанов A.A. Повышение эффективности генетического поиска // Тезисы докладов VI Всероссийской научной конференции студентов и аспирантов. Таганрог: изд-во ТРТУ, 2002. с. 89

5. Полупанов A.A. Управление процессом генетического поиска в оптимизационных задачах // Тезисы докладов XVII Международной научно-технической конференции "Интеллектуальные САПР" (CAD 2002). г. Геленджик.

6. Полупанов A.A. Преодоление локальных оптимумов в генетических алгоритмах // Тезисы докладов Пятой Всероссийской научной конференции молодых учёных и аспирантов «Новые информационные технологии. Разработка и аспекты применения». 28 ноября 2002, г. Таганрог, с. 78-79

7. Полупанов A.A. Адаптивная архитектура генетического поиска // Перспективные информационные технологии и интеллектуальные системы. 2002 №3(11), с. 49-55.'

8. Курейчик В.М., Лебедев Б.К., Маргелов A.B., Полупанов A.A. Программа генетического разбиения графа на подграфы с элементами самоорганизации (ГАСЭС). Авторское свидетельство об официальной регистрации программы для ЭВМ №2003610079 от 04.01.2003.

Личный вклад автора в работах, опубликованных в соавторстве: [1] -предложено использование элементов адаптации; [3] - принцип многодетной семьи, разработка структурной схемы адаптивного алгоритма разбиения схем, разработка модифицированных процедур для ГО; [6] - предложен метод "встряски"; [7] - модификация алгоритма разбиения схем, улучшающая его характеристики, за счёт введения дополнительных блоков.

Соискатель Г „ А. А. Полупанов

ВВЕДЕНИЕ.

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

1.1. Анализ и выбор математической модели.

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

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

1.4. Классификация методов и алгоритмов решения поставленной задачи

1.5. Выводы.

2. ПРИМЕНЕНИЕ МЕТОДОВ ГЕНЕТИЧЕСКОГО ПОИСКА ДЛЯ РЕШЕНИЯ ЗАДАЧИ РАЗБИЕНИЯ СХЕМ ПРИ ПРОЕКТИРОВАНИИ СБИС.45 '

2.1. Отличия методов генетического поиска от других оптимизационных методов.

2.2. Элементы генетических алгоритмов.

-2.3. Структура генетического алгоритма.

2.4, Выбор методики кодирования информации. 2.5. Селекция.

2.6. Основные генетические операторы.

2.6.1. Оператор кроссинговера.

2.6.2. Оператор мутации.

2.6.3. Оператор инверсии.

2.7. Выводы.

3. РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА РАЗБИЕНИЯ С ЭЛЕМЕНТАМИ АДАПТАЦИИ (ГАСЭА).

3.1. Структурная схема ГАСЭА для разбиения схем при проектировании

СБЙС.

3.2. Элементы адаптации в ГАСЭА.

3.3. Генератор хромосом содержащих группы вершин (ГХСЯ).

3.4. Модифицированные процедуры, применяемые для ГО.

3.5. Блок локального улучшения решений.

3.6. Блок анализа преждевременной сходимости и критерия остановки алгоритма.

3.7. Блок адаптации алгоритма.

3.8. Теоретические оценки алгоритма.

3.9. Выводы.

4. РАЗРАБОТКА ПРОГРАММНОЙ РЕАЛИЗАЦИИ И ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМА РАЗБИЫ 1И>

СХЕМ ПРИ ПРОЕКТИРОВАНИИ СБИС.

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. Выводы.

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

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

Развитие микроэлектроники происходило поэтапно: малые схемы, средние, большие, сверхбольшие. Первые ИС представляли собой объединение транзистора с набором сопротивлений и выполняли какую-либо логическую функцию. Степень интеграции постоянно возрастает с момента изобретения ИС. В 1965 году сопрезидент фирмы Intel Гордон Мур, предсказал, что число элементов на кристалле ИС должно удваиваться каждый год на протяжении последующих 10 лет. Это предсказание впоследствии было названо законом

Мура [76]. Последующие 25 лет позволили уточнить закон Мура: число элементов на кристалле удваивается в среднем каждые 1,5 года. Применение на этапе проектирования САПР разного уровня способствует повышению степени интеграции СБИС на уровне узлов, блоков и всей системы в целом [4- 10J. Сегодня СБИС способны выполнять сложнейшие наборы функции, а геометрические размеры транзисторов сократились до 0.18 микрона! В настоящее время промышленностью выпускается широкая номенклатура СБИС, суперкристаллов, содержащих миллионы элементов на кристалле 25x25мм. Неуклонное повышение степени интеграции СБИС привело к тому, что в них более 60% общей временной задержки сигнала приходится на задержки в межсоединениях. Рост размера области, отводимой для межсоединений, опережает рост размера области, предназначенной для активных элементов. В чипе, содержащем 10 миллионов транзисторов и использующем 4 слоя металлизации, около 40% площади отводится под межсоединения. Кроме того, рост числа транзисторов на кристалле, увеличивает также и средние размеры кристаллов. Посчитано, что площади кристаллов самых больших ИС возрастают примерно на 13% в год и эта тенденция, согласно прогнозу, сохранится, по крайней мере, на ближайших полтора - два десятилетия.

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

Поскольку СБИС может содержать несколько миллионов транзисторов, то невозможно спроектировать топологию всей схемы целиком в связи с ограниченными возможностями вычислительных средств, поэтому схема разбивается группированием компонентов в блоки. В результате разбиения формируется множество блоков и множество соединений между блоками [4, 11,12]. В очень больших схемах используется иерархическая структура разбиения.

Задача планирования заключается в определении взаимного расположения блоков относительно друг друга.

Задачей размещения является определение конкретного места для каждого блока на кристалле.

• Трассировка заключается в конструктивной реализации связей между элементами.

Задачей компакции является простое сжатие топологии во всех направлениях для уменьшения общей площади кристалла. Компакция позволяет уменьшить длину связей и временные задержки между компонентами кристалла. Уменьшение площади одного кристалла с помощью компакции позволяет размещать большее число кристаллов на площади одной подложки.

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

Большой ,вклад в развитие моделей, методов, стратегий, алгоритмов автоматизированного проектирования СБИС внесли такие учёные, как: Бершадский A.M., Деньдобренко Б.П., Казеннов Г.Г., Курейчик В.М., Морозов К.К., Норенков И.П., Селютин В.А., Шервани Н. и др. В многочисленной своей массе разработанные алгоритмы, программы и пакеты в САПР предназначены для оптимальной компоновки, размещении разногабаритных объектов (формирования базового плана кристалла) и межблочной трассировки межсоединений по критерию минимизации занимаемой площади и длины связей [13 - 16]. В связи с большой сложностью и размерностью задач конструкторского проектирования, а также с возникновением новых тенденций в технологии изготовления СБИС, появляется . необходимость в разработке новых направлений, методик, алгоритмов для решения данного класса задач. Поскольку даже в условиях современного развития информационных технологий, многие алгоритмы не справляются с решением или требуют много процессорного времени для поиска решений. С точки зрения повышения эффективности САПР, представляет интерес разработка новых алгоритмов и методов проектирования, для так называемых NP-полных задач, в которых нахождение оптимального решения возможно только полным перебором и которые являлись бы достаточно эффективными как с точки зрения точности и оптимальности получаемых решений, так и с позиции времени работы. К таким можно отнести методы эволюционного моделирования, которые были разработаны, как новое направление, в начале 1970 гг., но только сейчас приобрели приоритет в отношении других методов. Сравнительно недавно, их начали широко применять для решения задач в самых различных областях [17-23], в том числе для решения задач проектирования СБИС, поскольку эти методы способны обрабатывать множество решений при учёте множества критериев [24-36]. Данными свойствами обладают генетические алгоритмы (ГА) -поисковые алгоритмы, основанные на механизмах натуральной селекции и генетики, работающие с популяциями решений методом эволюционного поиска.

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

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

ЦЕЛЬЮ диссертационной работы является исследование и разработка методов разбиения схем при проектировании СБИС на основе модифицированных структур генетического поиска, с элементами адаптации, по критерию суммарного числа внутренних (внешних) связей, а также тепловой совместимости элементов, позволяющих повысить качество решений для задач большой размерности.

Для достижения поставленной цели были выполнены следующие этапы:

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

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

3. Выполнен анализ основных генетических операторов с точки зрения их пригодности и эффективности для решения поставленной задачи.

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

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

6. Разработана структурная схема генетического алгоритма разбиения гиперграфов на подгиперграфы с элементами адаптации (ГАСЭА) для задачи разбиения схем при проектировании СБИС.

7. Выполнены экспериментальные исследования разработанного проблемно-ориентированного генератора стартовой популяции решений (ГХСЯ), блока модифицированных процедур генетических операторов, разработанного алгоритма (ГАСЭА), а также сравнение его с известными алгоритмами разбиения.

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

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

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

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

3. Разработке новой адаптивной архитектуры генетического поиска с элементами адаптации, позволяющей оптимизировать процесс генетического поиска, представленной в виде общей структурной схемы, которая применима ■ не только для поставленной задачи.

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

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

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

3. Генетический алгоритм с элементами адаптации и программа для разбиения схем при проектировании СБИС, разработанная под наиболее популярное семейство 32-разрядных операционных систем Windows® 9х/МЕ/2000/ХР фирмы Microsoft Corporation, созданная в среде объектно-ориентированного программирования Borland С++ Builder " 5.0.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе « Разработка интеллектуальных систем проектирования на основе эволюционной адаптации » (№ ГР 1.8.96), г/б « Разработка теории и принципов построения интеллектуальных систем автоматизированного - проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений» (№ ГР 1.04.01), х/д между ТРТУ и Российским научно-исследовательским институтом информационных технологий и систем автоматизированного проектирования (Рос НИИ ИТ и АП) «Разработка эволюционных алгоритмов на графах с динамическими параметрами» (№ 12301).

Результаты работы используются в НИИ ТКБ ТРТУ по договору №71-0/98-16002-7 «Участие в разработке технических предложений по созданию РИС и алгоритмов её функционирования». Кроме того, материалы . диссертации использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций по курсу "Методы оптимизации", "Методы генетического поиска", а также в - цикле лабораторных работ по курсу "Автоматизация конструкторского проектирования СБИС".

АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась на научных семинарах (с 2000 по 2003 гг., ТРТУ), V, VI Всероссийских научно-технических конференциях студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (г. Таганрог, 2000 г., 2002 г.), XVII Международной научно-технической конференции "Интеллектуальные САПР" (г. Геленджик, 2002 г.), Пятой Всероссийской научной конференции молодых учёных и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (г. Таганрог, 2002 г.)."

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

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

4.8. Выводы

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

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

3. Выполнено сравнение разработанного алгоритма разбиения схем с ПГА, а также с существующими аналогами. Экспериментально подтверждено, что применение разработанного алгоритма позволяет на 2 - 5% повысить качество решения задачи разбиения схем при проектировании СБИС.

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

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

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

3. Для повышения качества решений, был разработан проблем неориентированный генератор хромосом стартовой популяции (ГХСЯ), повышающий качество получаемых решений на начальном этапе работы алгоритма и функционирующий только в предложенной системе кодирования решений. Созданы модифицированные процедуры, для генетических операторов, зависящие от динамических параметров, позволяющие повысить устойчивость генетического поиска и качество получаемых решений. Теоретически определена оценка пространственной сложности алгоритма, вычислительной сложности применяемых генетических операторов и алгоритма в целом. Оценка ПСА составляет 0(ап2) (где а - коэффициент, зависящий от текущих динамических, а также дополнительных параметров алгоритма), а ВСА модифицированных процедур для генетических операторов и разработанного алгоритма составляет не выше 0(Рп2) (где (3 — коэффициент, зависящий от текущих параметров алгоритма (размер популяции, вероятностей ГО, динамических параметров й т.п.)), что в целом ниже либо равно ВСА многих из существующих равнозначных методов.

4. Проведены серии тестов и экспериментов и выполнена обработка ' экспериментальных данных, что позволило уточнить теоретические оценки

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

5. Разработано программное обеспечение, приведено его описание для изучения характеристик алгоритма (экспериментального тестирования) разбиения схем при проектировании СБИС и утилита для конвертирования форматов данных входных файлов гиперграфов с целью совместимости с известными аналогами. При создании программ использовался пакет Borland С++ Builder™ 5.0 для 32-разрядных ОС семейства Windows® 9х, а

S) отладка, тестирование и эксперименты поводились на IBM совместимом компьютере с процессором Intel® Pentium® II \ 400 MHz и оперативной памятью 320 MB DIMM РС-133.

Для адекватного сравнения программного обеспечения использовались стандартные оценки производительности различных систем (по бенчмаркам iCOMP и др.), представленные фирмой Intel [75].

Проведённые комплексные исследования показали улучшение работы алгоритма по сравнению с ПГА от 3% до 7% в зависимости от вида задачи. В задачах с числом элементов более 100, разработанный алгоритм ГАСЭА по качеству получаемых решений выглядел на 5% - 7% лучше.

По сравнению с существующими алгоритмами, алгоритм ГАСЭА, имеющий практическую реализацию, в некоторых случаях достигал улучшения, позволяющие сократить сроки проектирования на 3-5%.

Более наглядно экспериментальные результаты приведены в приложении №2.

1. Конструирование аппаратуры на БИС и СБИС. Под ред. Высоцкого Б.Ф. и Стерепского В.П. М.: Радио и связь, 1989.

2. Петренко А.И., Лошаков В.Н., Тетельбаум А.Я., Шрамченко Б.Л. Автоматизированное проектирование СБИС на базовых кристаллах. М.: Радио и связь, 1988. 160 е., ил.

3. Савельев А .Я., Овчинников В. А. Конструирование ЭВМ и систем. Москва, Высшая школа, 1989.

4. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры: Учеб. пособие для вузов. М.: Радио и связь, 1983. 280 е.: ил.

5. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР: Учебник для вузов. М.: Энергоатомиздат, 1987. 400 е.: ил.

6. Системы автоматизированного проектирования: В 9-ти кн. Кн. 6.

7. Автоматизация конструкторского и технологического проектирования: Учеб. пособие для втузов/Под ред. Норенкова И.П. М.: Высшая школа, 1986. 160 е.: ил.

8. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. Москва, Радио и связь, 1990. 352 с.: ил.

9. Sherwani N.A. Algorithms for VLSI Physical Design Automation. Norwell, Kluwer Academic Publishers, 1995, 538 p.

10. Деньдобренко Б.П., Малика A.C. Автоматизация проектирования радиоэлектронной аппаратуры. М., Высш. шк., 1980. 384 с.

11. Под редакцией Норенкова И.П. Системы автоматизированногопроектирования в радиоэлектронике. Справочник. Москва, Радио и связь,1986.

12. Под редакцией Морозова К.К. Методы разбиения схем РЭА на конструктивно законченные части. Москва, Советское радио, 1978.

13. Горинштейн Л.Л. О разрезании графа. Известия АН СССР, Техническая кибернетика, 1969, №1.

14. Youssef G. Saab, Vasant В. Rao. "Fast Effective Heuristics for the Graph Bisectioning Problem", IEEE, vol.9 N1, January 1990, Transaction on computer-aided design.

15. Y.C. Wei, C.K. Cheng. "A two-level two-way Partitioning Algorithm", Tech. report CH2924-9, University of California, San Diego, IEEE, 1990.

16. Ching-Wei Yeh, Chung-Kuan Cheng, Ting-Ting Y. Lin. "A general purpose multiple way Partitioning Algorithm", 28th ACM/IEEE Design Automation Conference, paper 25/1, pp.421-425., 1991.

17. C.J. Alpert, A.B. Kahng. "Geometric Embeddings for Faster and Better Multi-Way Netlist Partitioning", in 30th ACM/IEEE Design automation conference, 1993, pp. 743-748.

18. Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company Inc., Massachusetts, 1989. 412- P

19. Davis L.D. Handbook of Genetic Algorithms. Van Nostrand Reinold, New York, 1991.

20. Goldberg D.E., Kalyanmoy D. A comparative analysis of selection schemes used in genetic algorithms. In Rawlings G.(Ed.). Foundations of Genetic Algorithms. Indiana University. Mogan Kaufmann, San Mateo, С A, 1991.

21. Syswerda G. Uniform Crossover in Genetic Algorithms. Proc. of the 3-rd Conf. on Genetic Algorithms, M. Kaufmann Publisher, San Mateo, California, 1989. p. 2-9.

22. Батйщев Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж, 1995. 69 с.

23. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 1992.

24. Kureichik V.M. et all. Some new features in Genetic Solution of the Traveling Salesman Problem. Proc. of the Second Intl. Conf. Adaptive Computing in Engineering, Design and Control, Plymouth, UK, 1996. pp. 294-296.

25. Rahmani, A.T. and Ono N. A Genetic Algorithm for Channel Routing Problem, in Proc. 5th Intl. Conf. on GAs, 1993. pp. 494-498.

26. Lieng J., Thulasiraman K. A Genetic Algorithm for Channel Routing in VLSI Circuits. Evolutionary Computation, 1(4), MIT, 1994. pp. 293-311.

27. Курейчик B.M. Генетические алгоритмы и их применение в САПР. Интеллектуальные САПР, меж. сб., Таганрог, 1995. стр. 7-11.

28. Чернышев Ю.О., Курейчик В.В. Генетические алгоритмы размещения / XXII International School And Conference On Computer Aided Design, CAD-95, Gurzuff; 1995. c. 329-330.

29. Cohoon J.P. and Paris W.D. Genetic placement. IEEE Trans. Computer Aided EJesign Integrated Circuits & Syst., vol.6, № 6, 1987. pp. 956-964.

30. Goodman, E. Tetelbaum, A. and Kureichik, V. (1994). A Genetic Algorithm Approach to Compaction, Bin Packing, and Nesting Problems. Case Center Technical Report #940702, Michigan State University

31. Chan, H.M. and Mazumder, P. A genetic algorithm for macro cell placement. Technical report, Department of Electrical Engineering and Computer Science, University of Michigan, 1989

32. Kureichik, V.M. Genetic Algorithms In CAD. Proc. Russia Conf. AI in CAD, Gelendzhik, September 1993.

33. Лебедев Б.К. Канальная трассировка на основе генетических процедур.• Известия ТРТУ, №3, Таганрог, 1997. 53-60 с.

34. Дебедев Б.К. Планирование СБИС методом генетического поиска. Известия ТРТУ. Интеллектуальные САПР. Таганрог, Изд-во ТРТУ, 1999, №3. 119126 с.

35. Schnecke V., Vornberger O. A Genetic Algorithms for VLSI Design Automation. Proc. of the Second Intl. Conf. Adaptive Computing in Engineering, Design and

36. Control, Plymouth, UK, March 1996. pp. 53-58. .

37. Батищев Д.И., -Власов C.E., Булгаков И.В. Плотное размещение разногабаритных объектов" на плоскости с помощью генетических алгоритмов. XXIII International School and Conference on Computer Aided Design. Yalta-Gurzuff, 1996. 354 c.

38. Мелихов A.H., Берштейн JI.C. Конечные чёткие и расплывчатые множества. Таганрог, ТРТИ. 1980.

39. Мелихов А.Н., Берштейн JI.C., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. 304 с.

40. Мелихов А.Н., Берштейн JI.C. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов-на-Дону: издательство Ростовского университета, 1981. 112 с.

41. Thang Nguyen Bui, Byung-Ro Moon. "GRCA: A Hybrid Genetic Algorithm for Circuit Ratio-Cut Partitioning". IEEE Transactions on computer-aided design of integrated circuits and systems, vol.17, No.3, March 1998, pp.193-204.

42. Курейчик B.M. Генетические алгоритмы. Монография. Таганрог, ТРТУ,1998.• 42. Курейчик В.М. Оптимизация в САПР: Учебное пособие. Таганрог, ТРТУ, 1998.

43. Букатова ИЛ. Эволюционное моделирование: идеи, основы теории,