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

003064511

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

Думсардт Александр Николаевич

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

Специальность 05 13 12 - Системы автоматизации проектирования

Автореферат диссертации на соискание ученой степени кандидата технических нп\ к

Таганрог - 2007

003064511

Работа выполнена в Южном федеральном университете

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

доктор технических наук, профессор

Лебедев Борис Константинович

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

заслуженный деятель науки РФ доктор технических наук, профессор Чернышев Юрий Олегович (РГАСХМ, г Ростов-на-Дону),

Ведущая организация

кандидат технических наук, доцент Родзин Сергеи Иванович (Технологический институт Южного федерального университета в г Таганроге)

Федеральное государственное унитарное предприятие «Таганрогский научно-исследовательский институт связи», г Таганрог

Защита диссертации состоится 23 августа 2007 г в 1420 на заседании диссертационного совета Д 212 208 22 при Южном федеральном университете по адресу. 347928, Таганрог, пер Некрасовский, 44, ауд Д-406

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу 344000, Ростов-на-Дону, ул Пушкинская, 148

Автореферат разослан « 20 » июня 2007 г

Ученый секретарь

диссертационного совета Д 212 208 22,

доктор технических наук, профессор

Целых А.Н

Общая характеристика работы

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

Применение на этапе проектирования САПР способствует повышению степени интеграции СБИС на уровне узлов, блоков и всей системы в целом Сегодня СБИС способны выполнять сложнейшие наборы функции, а геометрические размеры транзисторов сократились до 0 18 мкм и меньше Неуклонное повышение степени интеграции СБИС привело к тому, что в них более 60% общей временной задержки сигнала приходится на задержки в межсоединениях Рост размера области, отводимой для межсоединений, опережает рост размера области, предназначенной для активных элементов В чипе, содержащем 10 миллионов транзисторов и использующем 4 слоя металлизации, около 40% площади отводится под межсоединения

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

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

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

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

Данная работа является развитием результатов исследований, проводимых на кафедре САПР Таганрогского технологического института Южного федерального университета в рамках приоритетного национального проекта «Образование», а также аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» (2006 - 2008 гг) на тему «Разработка бионических методов и принципов поиска оптимальных решений при проектировании»

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

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

2 Построена архитектура генетического поиска для решения задачи разбиения схем

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

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

5 Построены модифицированные генетические операторы

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

Научная новизна работы заключается в решении задачи разбиения схем с использованием гибридных генетических процедур В работе

1 Построена архитектура генетического поиска для решения задачи разбиения схем

2 Разработаны и теоретически обоснованы новые технологии и механизмы генетического поиска, повышающие его эффективность - распараллеливание

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

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

4 Разработаны механизмы преодоления алгоритмом «локальных ям», и увеличения скорости поиска на основе эвристических методов и метода моделирования отжига

К числу наиболее важных научных результатов диссертации относятся

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

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

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

• новые технологии и средства повышения эффективности выхода из "локальных ям" и снижения общего времени поиска квазионтимальных решений,

• новые и усовершенствованные операторы генетического поиска обеспечивающие снижение времени поиска

Практическая ценность работы заключается в реализации программного комплекса «РагМюптд», использование которого позволяет на 15-20% ускорить процесс решения задачи разбиения схем, при этом получать решения, не уступающие по качеству по сравнению с существующими аналогами, благодаря использованию новых способов представления решений в задаче разбиения, а так же модифицированной архитектуре генетического поиска Данная среда позволяет автоматизировать процесс разбиения, сделать его доступным для специалистов различных областей науки, не обладающих навыками программирования

Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных научно-исследовательских работах Технологического института Южного федерального университета «Разрабогка теории и принципов построения интеллектуальных систем принятия решений при проектировании на

основе квантовых вычислений и бионических методов поиска» и «Разработка бионических методов и принципов поиска оптимальных решений при проектировании», а так же в рамках приоритетного национального проекта «Образование»

Материалы диссертации использованы в учебном процессе на кафедре САПР ТТИ ЮФУ при преподавании следующих дисциплин «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования»

Апробация основных теоретических и практических результатов работы. Результаты диссертации докладывались и обсуждались на Всероссийских и Международных научно-технических конференциях «Интеллектуальные САПР», (г. Таганрог, 2003 - 2005 гг), VII Всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», (г Таганрог, 2004r), II Всероссийская научная конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», (г. Таганрог, 2004 г), III Всероссийская научная конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», (г Таганрог 2005 г), Международная научно-техническая конференция «Интеллектуальные САПР», (г Таганрог, 2006 г )

Получено свидетельство об официальной регистрации программы для

ЭВМ

Публикации. По теме диссертационной работы опубликовано 7 печатных работ, сделано 2 доклада на Всероссийских и Международных научно-технических конференциях

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 139 страницах, содержит 38 рисунок, 17 таблицы, 103 наименований библиографии и приложения

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

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

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

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

Р^р]— + р2—~,где р^рг е[0,1],А + рг =Ь С1)

где р1 и р2 компоненты вектора предпочтения

Итак, решаемая в диссертационной работе дискретная задача разбиения может быть сформулирована следующим образом

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

Пусть Н = (X, Е) - гиперграфовая модель схемы, где X = {XI 11 = 1, 2, , и} -множество вершин, моделирующие элементы схемы, Е = {е] \ е} сХ,_/ = I, 2, , т) - множество гиперребер, моделирующие электрические цепи Вес вершин задается множеством Ф — {ф, | / = 1,2, , я}, вес ребер — у = {щ |/ = I, 2, ,т\

Необходимо сформировать К-узлов, т е. множество X разбить на К непустых и непересекающихся подмножеств ХУ

X = и\;, (V/, Д X, пХ} = 0, X, * 0 (2)

Одним из параметров целевой функции Г является количество ребер, пересекающих разрез

(3)

Величина оценки задержки I) в выражении (1) выражается комбинацией двух факторов, когорые напрямую влияют на задержку схемы задержка цепей, количество разреюв каждой цепи

л:

я=1>/«,+£лА (4)

■ 1

У

где щ -- вес ребра, е, коэффициент, принимающий значение 1 или 0, в зависимости от того разрезается ребро или нет, |ЕК| - количество ребер в гиперграфе Н, Ц - текущая задержка.]-ой цепи(ребра), к, - число разрезов цепи J

Предлагаемая оценка задержки цепи Ц содержит два компонента Первый — это задержка вентилей Задержка вентилей считается постоянной и в дальнейшем не учитывается Второй компонент - это задержка проводников, которая оценивается, используя модель задержки Эльмора для ребра е (ребро соответствует проводнику) в соответствии со следующей формулой

где - общее сопротивление проводника е, Се - общая емкость проводника е, С, -общая емкость истоков каждой цепи Для вычисления К,иСе нам необходимо длина каждого ребра Средняя длина цепи[116], соединяющая ш элементов определяется по формуле

а *Ъ (б)

« а,+ь, где а, и Ъ, - геометрические размеры узлов между которыми распределены элементы цепи, а, р, у -настроечные параметры, вычисленные как а = 1 1 , Р = 2 0, у = 0 5 Удельное сопротивление на единицу длины проводника считаем г = О 115, удельная емкость на единицу длины проводника с = 0 00015

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

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

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

На основе приведенных рассуждений, в работе была выбрана стратегия поиска «Эволюция - Эволюция» Обобщенная схема приведена на рисунке 1

I Входные рТ м 1; ГГд Вывод

параметры | 1 м 1 и ч | " ММ , решения

Рисунок 1 Обобщенная схема стратегии поиска «Эволюция - Эволюция»

Здесь под входными параметрами понимается

• разбиваемая схема,

• ограничения,

• критерии и цели оптимизации

ГА — генетический алгоритм с элементами альтернативного развития решений, решает задачу разбиения путем назначения гиперребер в узлы

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

ГГА - гибридный генетический алгоритм, производит улучшение полученных решений на предыдущем шаге путем случайных перестановок вершин между узлами

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

Поэтому для первого генетического алгоритма предложен метод кодирования при котором задается размещение гиперребер по узлам Предлагается представлять решение поставленной задачи в виде двух векторов Р1 и Р?

• Р] - последовательность назначения ребер в узлы - определяет, в какой последовательности будут назначаться ребра

• Р2 - последоватечьность формирования узлов - определяет, в какой последовательности будут формироваться узлы

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

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

Рассмотрим принцип кодирования последовательности назначения ребер в узлы - Р, Хромосома Н, состоит из генов, число которых на единицу меньше числа назначаемых ребер т

Н,={&|1=1,2, , (т-1)} Ген gt может принимать значения в интервале 1 < < « - < + ъ то есть чем

больше порядковый номер!, тем меньшее значение он может принять

Для декодирования хромосомы используется опорный вектор номеров ребер 5, = |{ = 1,2, ,т] Процесс декодирования хромосомы Н[ начинается с первого

гена g! В результате декодирования на шаге I гена по вектору В1 определяется номер назначаемого на шаге I ребра После декодирования очередного гена вектор В] уменьшается путем удаления из него номера элемента, определенного при декодировании Кодирование и декодирование последовательности формирования узлов Р2 проводиться аналогичным способом

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

Дихотомическое разбиение вектора у' можно задать с помощью вектора с1„

состоящего из нулей и единиц Размерности еИ, и у' совпадают Если элемент

вектора 4 равен 0, то соответствующий элемент вектора у* принадлежит первому подмножеству, если - 1, то второму Щ=|0 Например,

{ У=<1,3,7,8,9,10,2>, а=<0,1,1,0,0,1,0>}, {У,=<1,8,9,2>, У2=<3,7,10>}

Таким образом, разбиение V на К, можно задать с помощью набора векторов 0= {с11 \г = = 1,2, .,(£-1)}, число (к -1) которых равно числу вершин дерева в, подвергающихся ветвлению, к - число формируемых узлов </,-{¿„17 = 1,2, , д },</„ е{0,1} А НV¡=«,/у, =|р; \= \\\ Каждый

вектор с11 кодируется и представляется в виде хромосомы Н, Суть кодирования заключается в том, что для каждой единицы задается ее месторасположение относительно нулей в векторе с1, В качестве базы кодирования хромосом используется г, нулей, относительно которых в (3, размещаются единицы

Число генов Н, равно числу единиц в соответствующем векторе <з?„ а значения glJ лежит в интервале l<~g¡<^-z¡+l Восстановление с1, по /7< осуществляется следующим образом Пусть Н,=<2,2,4,1>, е,=4 Имеется база из г,=3 нулей Номера позиций в базе с 1 по 4 Это значит, что в позициях базы, номера которых равняются значениям генов, необходимо поместить единицы В нашем случае

а,=<1,0,1,1,0,0,1>

Необходимо отметить, что в соответствии с процедурой декодирования, порядок расположения генов в хромосоме не имеет значения, важно только, какие значения имеют гены Это приводит к избыточности пространства решений, представленного хромосомами Пусть Р, — число перестановок генов в

хромосоме Н, Тогда одному решению задачи разбиения соответствует

I

наборов хромосом

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

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

В третьей главе разработана структура комплексного гибридного генетического алгоритма (ГАЭАР), которая представлена на рисунке 2 Рассмотрим более подробно блоки входящие в структуру алгоритма

Блок генерации начальной популяции — предназначен для создания начального множества (популяции) особей Применение рассмотренного выше

10

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

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

Блок модифицированных процедур ГО — набор процедур, реализующих различные генетические операторы, использующих динамические параметры и предназначенных для формирования особей-потомков, отличающихся более высоким значением целевой функции по сравнению с родительскими особями

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

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

На каждой итерации выполняется операция преобразования начального решения Рассмотрим операцию преобразования Для каждого узла k, е К выбирается вершина vt е к, Выбор вершины V/ осуществляется по нижеописанному алгоритму

1 Vvj е к, рассчитывается величинаPj и откладывается на отрезке [0,1]

, т =1,2, ] к, | (7)

где noutcr - число внешних связей вершины, nirmer - число внутренних связей вершины, ю - число вершин в узле Если nmner = 0, то принимается, что n]rmtr = 1

("o„^l",mer)j ^(."шег1",^,)»

Величина " определяет вероятность выбора вершины

Vj, при этом если вершина не имеет внешних связей, то noater принимается равным единице Таким обра?ом, достигается отличная от нуля вероятность выбора вершин, не имеющих внешних связей

2 На интервале [0, 1] генерируется число р, подчиняющееся нормальному закону распределения

3 Вершина vie ki выбирается таким образом, чтобы выполнялось условие р е (pl-1, pi]

То есть из каждого узла к, е К выбирается строго по одной вершине, следовательно, количество выбранных вершин равно \К\ Далее происходит перераспределение выбранных вершин по узлам в соответствии со следующим алгоритмом

1 Все выбранные вершины переносятся в «Буфер» - множество В (]В\ = | К\)

2 Выбирается первый не заполненный узел k} е К

Pj=PJ-i

In

outer inner

In )

outer inner Jm

Инициализация переменных и динамических параметров

Блок Генерации--—

популяции • Кодирование решений , Генерация популяции

Блок

Генетического поиска

Репродукция

Блок модифицированных генетических операторов ОК, ОМ

Альтернативного | Декодирование развитая особи | полученных решении

Редукция решений

Блок Анализа Преждевременной

СХОДИМОСТИ чет

Блок

Адаптации

преждевременная сходимость „

\ Адаптация виртуальных I популяций

А

Генетический Алгоритм

критерии останова

Блок [ Миграции |

Выбор лушшх решений

; 13

41 /

12 ' 1 /

Блок I

Генерации | Кодирование решений ' популяции Генерация популяции

Бпол Генетического поиска г

Репродукция

j Блок модифицированных! генетических оператооов j OK, ОМ

Оценка Решений

Локальное улучшение полученных решений

Редукция решений

Ги5р/|дный

Генетический

алгоритм

критерий останова

да I

Вывод лучшего решения

Блек

Адаптации

- нет Адаптация виртуальных |

популяции

____J

Рисунок 2 Структурная схема комплексного гибридного генетического алгоритма

3 И.-, е В рассчитывается количество срязей с узлом Ц - q4

4 V vie В рассчитывается величина ру и откладывается на отрезке [0,1]

(8)

5 На интервале [0, 1] генерируется число р, подчиняющееся нормальному закону распределения

6 вершина V, назначается в узел А, если выполняется условие р е (Pi.ij.PiJ. и удаляется из В

7 Если ВФ-0 то переходим на п 2, в противном случае перераспределение вершин между узлами считается завершенным

После этого производится оценка полученного решения После принятия или отклонения решения начинается новая итерация алгоритма

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

Для имитации развития особи в различных условиях в алгоритм было введено несколько операторов декодирования генетического материала Причем для большего соответствия естественным процессам была введена случайная величина п выбираемая из множества {1, 2}, которая определяет количество используемых операторов декодирования На рисунке 3 приведена структурная схема, отображающая механизм альтернативного развития особи при п = 2 Алгоритм работы блока реализующего предложенный механизм

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

Копирование входящей особи п раз Эта операция названа «Клонированием»

Для каждой копии особи вызывается свой ранее определенный оператор декодирования

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

вход

ОСОБЬ

I

«Клонирование»

1 1

ОСОБЬ 1 ОСОБЬ 2

1

ОД1 ОД2

А 1

Оценка Оценка

А _ 1 _

Выбор лучшего решения

выход

Решение

Рисунок 3 Структурная схема, отображающая механизм альтернативного развития особи при п = 2 14

В разработанном алгоритме используется два оператора декодирования:

1. последонательного назначения гиперребер в узлы;

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

Блок Миграции — После завершения работы первого ГА производит выборку решений для создания популяции для следующего ГА

Елок Адаптации - введен для увеличения скорости генетического поиска. На каждой итерации осуществляется анализ набора популяций и на основе результатов производится адаптация. Суть заключается в смене опорного вектора В], если в течение некоторого числа генераций в виртуальной популяции В = {В)\17} не появляются индивидуальности с лучшим значением целевой функции.

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

ЭСА ДЛИ СГрйТвГ ии поиска от числа ааршин

чнтнрикнН

Рисунок 4 Зависимость среднего времени поиска для стратегий поиска

ЦФ ДП* СТ|ДО*ГИ>* ПОИСК? ОТ Ч*СПЛ ййрЩИП

♦ • . Эюггеиря

ЯМ "" ~ ....... '

О --,---,-------г--г----

м 1м> ' 2М зоо ^ ш ¡и

Рисунок 5 Зависимость среднего значения ДФ для стратегий поиска На рисуй как 4, 5 приведены зависимости времени поиска и качества решения от количества вершин для различных стратегий поиска. Проанализировав

графики можно сделать выводы, чю при использовании стратегии «Эволюция -Эволюция» требуется в среднем на 50% больше процессорного времени, но в то же время, при этом алгоритм находит в среднем на 15,5% лучшее решение, чем при использовании поиска на основе стратегии «Эволюция» Приведенные практические результаты доказывают эффективность примененной стратегии поиска и выбор представления решения задачи разбиения

Таблица 1

Описание тестовых схем

Circuit Pl/PO No. of gates

cordic 23/2 881

misex3 14/14 1349

ХЗ 135/99 1369

с6288 32/32 2435

S15850 39/75 4321

firisc 19/16 4400

elliptic 130/112 4711

Таблица 2

Результаты вычислительных экспериментов_

Cordic nnsex3 X3 c6288 sl5850 Fnsc Elliptic

Pure hMetis D. 21,9 67,6 18,78 59,21 81,14 169,33 271,02

Cut 327 543 211 182 617 838 508

CPU (s) 2 5 4 31 28 34 16

Net& Path Based D. 16,41 61,16 16,65 56,26 78,93 150,2 205,25

Cut 278 614 261 216 671 869 619

CPU (s) 5 13 6 80 37 61 22

PPFF D. 20,6 64,3 16,04 59,19 82,1 165,17 231,33

Cut 313 540 228 201 615 851 510

CPU (s) 6 14 8 79 43 66 25

VPR D. 21,5 64,3 17,04 60,01 80,73 167,2 233,02

Cut 319 543 216 204 622 843 513

CPU (s) 10 18 13 85 47 71 27

ГАЭАР D. 15,93 60,7 17,05 56,26 77,01 153,3 204,97

Cut 280 610 253 209 651 842 567

CPU is) 4 14 6 73 31 49 17

Задаржкл сигнала

зда

■ 250 I

200 160 ■ ют ■

50

¿.на

П..1!1!

ЯРигвИЙЙв я Вяма

ПРРРР а урн ■ ГАЗАР

Согйс тиехЗ ХЗ с62ЙЯ 515350 Рг)6С Е111р6с

Рисунок 6 Результать! сравнений по критерию ((временная задержка»

Ребер ыразрезе

СопЯе ггим»3

сбзев 515850 Рпве Е1||рй=

Рисунок 7 Результаты сравнений по критерию «число межмодульна

соединений»

Время работы

№ №

70 И

М ■

а;

10 : ! ¿11 -оЗ.

Рисунок 8 Результаты сравнений по времени выполнения

Из приведенных данных можно сделать вывод, что разработанный алгоритм позволяет находить решения не уступающие по качеству, а иногда и превосходящие результаты полученные с использованием других алгоритмов При этом время, затраченное на поиск решения, меньше в среднем на 15%

В заключении сформулированы основные выводы и результаты диссертационной работы

В приложении приведены акты об использовании результатов диссертационной работы и приведено описание программного продукта

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

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

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

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

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

4 Предложены новые и модифицированные генетические операторы, обеспечивающие уменьшение времени поиска

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

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

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

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

с использованием других алгоритмов При этом время, затраченное на поиск решения, меньше в среднем на 15%

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

1 Дуккардт А Н, «Методы Генетического поиска для мультихромосомных представлений», VII Всеросийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника, и системы управления», Таганрог, 2004, с 108

2 Дуккардт А Н, Лебедев Б К «Подход к решению задачи разбиения на основе квантовых алгоритмов», XI МНПК студентов и молодых ученых «Современные техника и технологии СТТ'2005» г Томск

3 Дуккардт А Н, Лебедев Б К, «Разбиение на основе комбинированных генетических процедур», Известия ТРТУ Тематический выпуск "Интеллектуальные САПР" Таганрог Изд-во ТРТУ, 2006 №8 С 46-51

4 Дуккардт А Н, «Решение задачи разбиения на основе процедуры «Выбивания»», Известия ТРТУ Тематический выпуск "Интеллектуальные САПР" Таганрог Изд-во ТРТУ, 2006 №6 С 63-66

5 Дуккардт А Н, «Разбиение на основе процедуры «Выбивания»», VIII всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» Таганрог Изд-во ТРТУ, 2006 С 89-90

6 Дуккардт АН, , «Разбиение на основе процедур «Выбивания» и «Дублирования»», IV Всероссийская научная конференция молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» Таганрог Изд-во ТРТУ, 2006 С 199-201

7 Дуккардт А Н, Лебедев Б К, «Гибридный генетический алгоритм с элементами антимонопольного развития», Известия ТРТУ Тематический выпуск "Интеллектуальные САПР" Таганрог Изд-во ТРТУ, 2007 №1 С 86-91

В работах [2,3, 7J, опубликованных в соавторстве, лично автору принадлежат следующие результаты - разработка методов альтернативного развития решений, модификация аддитивного критерия оценки качества разбиения с учетом временных задержек и числа межмодульных связей

Соискатель

Дуккардт А Н

Подписано в печать|^ОЭ- 2006 г Заказ Формат 60x84 1/16 Печать офсетная __Печ л 1,0 Тираж 100 экз

Издательство Таганрогского государственного радиотехнического университета

ГСП 17А, Таганрог, 28, Некрасовский, 44 Типография Таганрогского государственного радиотехнического университета ГСП 17А, Таганрог, 28, Некрасовский, 44

ВВЕДЕНИЕ.

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

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

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

J .3 Анализ существующих алгоритмов разбиения.

1.4 Выводы.

2 РАЗРАБОТКА БАЗОВЫХ МЕТОДОВ ГЕНЕТИЧЕСКОГО ПОИСКА

ДЛЯ ЗАДАЧИ РАЗБИЕНИЯ СХЕМ.

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

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

2.3 Кодирование информации для задачи разбиения схем.

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

2.3.2 Структура хромосом и принципы декодирования на основе рекурсивного применения процедуры дихотомического разбиения.

2.4 Генетические операторы.

2.5 Выводы.

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

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

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

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

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

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

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

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

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

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

В своей многочисленной массе разработанные алгоритмы, программы и пакеты в САПР предназначены для оптимального решения задач разбиения, размещения разногабаритных объектов (формирования базового плана кристалла) и межблочной трассировки межсоединений по критерию минимизации занимаемой площади и длины связей [13, 14, 15, 16]. В связи с большой сложностью и размерностью задач конструкторского проектирования, а также с возникновением новых тенденций в технологии изготовления СБИС, появляется необходимость в разработке новых направлений, методик, алгоритмов для решения данного класса задач. Поскольку даже в условиях современного развития информационных технологий, многие алгоритмы не справляются с решением или требуют много процессорного времени для поиска решений. С точки зрения повышения эффективности САПР, представляет интерес разработка новых алгоритмов и методов проектирования, для -так называемых NP-полных задач, в которых нахождение оптимального решения возможно только полным перебором и которые являлись бы достаточно эффективными как с точки зрения точности и оптимальности получаемых решений, так и с позиции времени работы. К таким можно отнести методы эволюционного моделирования, которые были разработаны, как новое направление, в начале 1970 гг., но только сейчас приобрели приоритет в отношении других методов. Сравнительно недавно, их начали широко применять для решения задач в самых различных областях [17, 18, 19, 20], в том числе для решения задач проектирования СБИС, поскольку эти методы способны обрабатывать множество решений при учёте множества критериев [21-29]. Данными свойствами обладают генетические алгоритмы (ГА) - поисковые алгоритмы, основанные на механизмах натуральной селекции и генетики, работающие с популяциями решений методом эволюционного поиска. Основная цель ГА - абстрактно и формально объяснить адаптацию процессов в естественных системах и спроектировать искусственные программные системы, которые содержат основные механизмы естественных систем. Основная тема поиска ГА - поиск баланса между эффективностью и качеством для "выживания" в различных условиях. Главные отличия ГА от других оптимизационных и поисковых процедур следующие: осуществляют поиск из множества точек, а не из единственной точки; используют целевую функцию, а не её различные приращения; для оценки получаемой информации используют не детерминированные, а вероятностные правила; дают не одно решение, а целый спектр решений, из которых возможно выбрать наилучшее, с точки зрения поставленной задачи. Пожалуй, одним из главных свойств ГА является, то что, они достаточно легко преодолевают локальные оптимумы в силу своей "природы". Гибкость структуры ГА, возможность её настройки и перенастройки дают возможность создания структур, обеспечивающих получение наилучшего результата за приемлемое время. Это, в свою очередь, предоставляет исследователям широчайшие возможности, для поиска альтернативных решений в этом направлении.

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

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

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

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

2. Построена архитектура генетического поиска для решения задачи разбиения схем.

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

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

5. Построены модифицированные генетические операторы.

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

1. Построена архитектура генетического поиска для решения задачи разбиения схем.

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

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

4. Разработаны механизмы преодоления алгоритмом «локальных ям», и увеличения скорости поиска на основе эвристических методов и метода моделирования отжига.

НАУЧНЫЕ РЕЗУЛЬТАТЫ работы представляют:

1. новая архитектура комплексного гибридного генетического алгоритма для решения задачи разбиения схем;

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

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

4. новые технологии и средства повышения эффективности выхода из "локальных ям" и снижения общего времени поиска квазиоптимальных решений;

5. новые и усовершенствованные операторы генетического поиска обеспечивающие снижение времени поиска.

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

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

3. Комплексный Гибридный Генетический алгоритм и программа для разбиения схем.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных научно-исследовательских работах Технологического института Южного федерального университета «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска» и «Разработка бионических методов и принципов поиска оптимальных решений при проектировании».

Материалы диссертации использованы в учебном процессе на кафедре САПР ТТИ ЮФУ при преподавании следующих дисциплин: «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».

Работа выполнена в рамках приоритетного национального проекта «Образование».

АПРОБАЦИЯ основных теоретических и практических результатов работы. Результаты диссертации докладывались и обсуждались на Всероссийских и Международных научно-технических конференциях: «Интеллектуальные САПР», (г. Таганрог, 2003 - 2005 гг.); VII Всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», (г. Таганрог, 2004г.); II Всероссийская научная конференции молодых ученых, аспирантов и студентов

Информационные технологии, системный анализ и управление», (г.

Таганрог, 2004 г.); Ш Всероссийская научная конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», (г. Таганрог, 2005 г.); Международная научно-техническая конференция «Интеллектуальные САПР», (г. Таганрог, 2006 г.).

ПУБЛИКАЦИИ. По теме диссертации опубликовано 6 печатных работ. СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырёх глав, заключения, и списка использованных источников. Работа содержит 139 стр., включая 38 рис., 17 табл., список использованных источников из 103 наименований, 12 стр. приложений и актов об использовании. СОДЕРЖАНИЕ РАБОТЫ.

4.4 Выводы

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

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

3. Проведены серии тестов и экспериментов и выполнена обработка экспериментальных данных.'

4. Подтверждена гипотеза использования стратегии «Эволюция - Эволюция» для задачи разбиения схем с учетом временных задержек и числа межмодульных связей. При использовании данной стратегии поиска требуется в среднем на 50% больше процессорного времени, но в то же время, при этом алгоритм находит в среднем на 15,5% лучшее решение, чем при использовании поиска на основе стратегии «Эволюция».

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

6. Разработано программное обеспечение, приведено его описание для изучения характеристик алгоритма (экспериментального тестирования), разбиения схем. При создании программ использовался пакет Visual Studio 2005 для 32-разрядных ОС семейства Windows® 9х, а отладка, тестирование и эксперименты поводились на IBM® совместимом компьютере с процессором AMD Athlon-64® 3000+ и оперативной памятью 512 MB DIMM РС-3200.

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

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

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

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

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

4. Dominic A. Antonelli, Danny Z. Chen, Timothy J. Dysart, Xiaobo S. Hundrew, B. Kahng Peter, M. Kogge Richard, C., Murphy Michael, T. Niemier, "Quantum-Dot Cellular Automata (QCA) Circuit Partitioning: Problem Modeling and Solutions", DAC, 2004 .

5. Гладков Л.А., Курейчик В.В., Курейчик В.М. .Дискретная математика. Часть 2. Теория алгоритмов и алгебра логики: Учебное пособие. Под ред. В.М. Курейчика. Таганрог: Изд-во ТРТУ, 2006. -152 с.

6. Норенков И.П. Основы автоматизированного проектирования. М.: Изд-во МГТУ имени Н.Э.Баумана, 2006.-360с.

7. Schaller Robert R. MOORE IS LAW: past, present, and future. IEEE SPECTRUM JUNE, 1997, pp. 53-59.

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

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

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

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

12. Курейчик В.М., Курейчик В.В. Генетический алгоритм разбиения графа. Известия Академии наук. Теория и системы управления, №4, 1999.

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

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

15. 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.

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

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

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

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

20. 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.

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

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

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

24. Schnecke V., Vornberger O. A Genetic Algorithms for VLSI Design Automation. Proc. of the Second Intl. Conf. Adaptive Computing in Engineering, Design and Control, Plymouth, UK, March 1996. pp. 53-58.

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

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

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

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

29. Мелихов A.H., Берштейн Л.С., Курейчик B.M. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. 3 04 с.

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

31. Харари Ф. Теория графов. М.: Мир, 1973. 300 е., ил.

32. Уилсон Р. Введение в теорию графов. М.: Мир, 1977. 208 с.

33. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.432 с.

34. Оре О. Теория графов. М.: Наука, 1980. 356 с.

35. Гатчин Ю.А., Коробейников А.Г. Методы представления математических моделей в САПР при концептуальном и инфологическом моделировании. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 35-41.

36. Марченко А. «Современные проблемы автоматизации проектирования топологии СБИС», МЭС 2006

37. J. Cong, С. Wu, 'Global Clustering-Based Performance-Driven Circuit Partitioning', Proc. ISPD, 2002.

38. W.E. Donath et al, 'Timing Driven Placement Using Complete Path Delays', Proc. ACM/IEEE DAC, 1990.

39. J. Minami, T. Koide, S. Wakabayashi, 'An Iterative Improvement Circuit Partitioning Algorithm under Path Delay Constraints', IEICE Trans. Fundamentals, Dec. 2000.

40. S.-L Ou, M. Pedram, 'Timing-driven Partitioning Using Iterative Quadratic Programming', at http://atrak.usc.edu/~massoud/, see "Coming Attractions!", 2001.

41. P. Zarkesh-Ha, J.A. Davis, J.D. Meindl, 'Prediction of Net-Length Distribution for Global Interconnects in a Heterogeneous System-on-a-Chip', IEEE Trans. VLSI Systems, Dec. 2000.

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

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

44. 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.

45. Shihliang Ou and Massoud Pedram, "Timing-Driven Bipartitioning with Replication Using Iterative Quadratic Programming", ASPDAC, 2001.

46. Dominic A. Antonelli, Danny Z. Chen, Timothy J. Dysart, Xiaobo S. Hundrew, B. Kahng Peter, M. Kogge Richard, C., Murphy Michael, T. Niemier, "Quantum-Dot Cellular Automata (QCA) Circuit Partitioning: Problem Modeling and Solutions", DAC, 2004

47. Курейчик В.М. Оптимизация в САПР: Учебное пособие. Таганрог, ТРТУ, 1998.

48. Лебедев Б.К. Интеллектуальные процедуры синтеза топологии СБИС, Таганрог: Изд-во ТРТУ, 2003. 108 с.

49. S. Kirkpatrick, C.D. Gelatt, and М.Р. Vecchi. Optimization by simulated annealing. Science, 220(4598):671 680, 1983

50. Емельянов B.B, Курейчик В.М., Курейчик B.B. Теория и практика эволюционного моделирования. М.: Физматлит,2003.

51. Курейчик В.М. Генетические алгоритмы и их применение: Монография. Таганрог: Изд-во ТРТУ, 2002.

52. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. / под ред. В.М. Курейчика. Учебное пособие. Ростов на - Дону: Ростиздат, 2006.

53. Букатова И.Л. Эволюционное моделирование: идеи, основы теории, приложения. Москва, Знание, выпуск 10, 1981

54. Cristinel Ababei, Kia Bazargan, "Statistical Timing Driven Partitioning for VLSI Circuits", 2002

55. C.M. Fiduccia, R.M. Mattheyses, 'A Linear-Time Heuristic for Improving Network Partitions', Proc. ACM/IEEE DAC, 1982.

56. Yongseok Cheon, Seokjin Lee, Martin D. F. Wong, "Stable Multiway Circuit Partitioning for ECO", 2003

57. C. J. Alpert and S.-Z. Yao, "Spectral Partitioning: The More Eigenvectors, The Better," Proc. ACM/IEEE Design Automation Conf., 1995, pp. 195200.

58. P. K. Chan, M. D. F. Schlag and J. Zien, "Spectral K-Way Ratio Cut Partitioning and Clustering," IEEE Trans, on CAD 13(9), 1997, pp. 10881096.

59. L. Hagen and A. B. Kahng, "Fast Spectral Methods for Ratio Cut Partitioning and Clustering," Proc. IEEE Intl. Conf. on Computer-Aided Design, 2001, pp. 10-13.

60. Jan-Yang Chang, Yu-Chen Liu, and Ting-Chi Wang "Faster and Better Spectral Algorithms for Multi-Way Partitioning", ASPDAC 1999

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

62. 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.

63. G. Karypis. Multilevel hypergraph partitioning. In J. Cong and J. Shinnerl, editors, Multilevel Optimization Methods for VLSI, chapter 6. Kluwer Academic Publishers, Boston, MA, 2002.

64. С. Alpert and A. Kahng. A hybrid multilevel/genetic approach for circuit partitioning. In Proceedings of the Fifth ACM/SIGDA Physical Design Workshop, pages 100-105, 2002.

65. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel hypergraph partitioning: Application in vlsi domain. IEEE Transactions on VLSI Systems, 20(1), 1999. A short ersion appears in the proceedings ofDAC1997.

66. Youssef Saab. A new effected and efficient multi-level partitioning algorithm: DATE, 2000.

67. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel hypergraph partitioning: Application in VLSI domain. Design Automation Conference, pages 526-529,1997

68. Navaratnasothie Selvakkumaran and George Karypis, "Multi-Objective Hypergraph Partitioning Algorithms for Cut and Maximum Subdomain Degree Minimization", ICCAD 2003

69. Cristinel Ababei, Navaratnasothie Selvakkumaran, Kia Bazargan, George Karypis, "Multi-objective Circuit Partitioning for Cutsize and Path-Based Delay Minimization", ICCAD 2002

70. Курейчик В.В., Курейчик В.М. Об управлении на основе генетического поиска. Автоматика и телемеханика. РАН, №10, Москва, 2001,-с.174-187.

71. Kureichik V.V., Kureichik V.M., Genetic Algorithms. HG Verlag, Konstans, 2004

72. Курейчик B.M., Лебедев Б.К., Гладков Л.А. и др. Разработка интеллектуальных систем проектирования на основе эволюционной адаптации // Отчёт по НИР (промежуточный). Депонир. в ВНТИ № ГР 01.9.60004346, М: 1998,43 стр.

73. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография. Таганрог: изд-во ТРТУ, 2000. 192 с.

74. Дуккардт А.Н., Лебедев Б.К. «Подход к решению задачи разбиения на основе квантовых алгоритмов», XI МНПК студентов и молодых ученых «Современные техника и технологии СТТ'2005» г. Томск

75. Дуккардт А.Н., «Методы Генетического поиска для мультихромосомных представлений», VII Всеросийскавя научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника, и системы управления», Таганрог, 2004, с. 108

76. Лебедев Б.К., Дуккардт А.Н., «Разбиение на основе комбинированных генетических процедур», Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 2006. №8(63). С. 46-51

77. Дуккардт А.Н., «Решение задачи разбиения на основе процедуры «Выбивания»», Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 2006. №6. С. 6366

78. Дуккардт А.Н., «Разбиение на основе процедуры «Выбивания»», VIII всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» Таганрог: Изд-во ТРТУ, 2006. С. 89-90

79. Дуккардт А.Н., Лебедев Б.К. «Гибридный генетический алгоритм с элементами антимонопольного развития», Известия ТРТУ.

80. Тематический выпуск "Интеллектуальные САПР".

81. Таганрог: Изд-во ТРТУ, 2007. №1. С. 86-91

82. Хедрик Ф. Генетика популяций. М.: Техносфера, 2003.

83. Редько В.Г. Эволюционная кибернетика. М.: Наука, 2001.

84. Practical Handbook of Genetic Algorithms. Editor I. Chambers. T.l, Washington, USA, CRC Press, 1995.

85. Practical Handbook of Genetic Algorithms. Editor I. Chambers. T.2, Washington, USA, CRC Press, 1995.

86. Practical Handbook of Genetic Algorithms. Editor I. Chambers. T.3, Washington, USA, CRC Press, 1999.

87. Касьянов B.H., Евстигнеев B.A. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003.

88. Holland, John Н., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan, 1975.

89. Wolfe G., Wong J.L. and Potkonjak M.Watermarking Graph Partitioning Solutions. IEEE Transactions on CAD of Integrated Circuits and systems, V. 21, № 10, October 2002, pp. 1196 1204.

90. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. -М.: Мир, 1985. 512 с.

91. Применение математических методов и ЭВМ. Планирование и обработка результатов эксперимента: Учеб. пособие / Под общ. ред. Останина А.Н. -Минск: Вышэйшая школа., 1989. 218 е.: ил.

92. Адлер Ю.П. Планирование эксперимента при поиске оптимальных условий. М.: Наука, 1971. 283 е.: ил.

93. Митропольский А.К. Техника статистических исследований. М., "Наука", 1971.576 е.: ил

94. Navaratnasothie, Selvakkumaran, Kia Bazargan, George Karypis. Multi-objective Circuit Partitioning for Cutsize and Path-Based Delay Minimization. ICCAD 2002.

95. Yongseok Cheon Seokjin Lee Martin D. F. Wong. Stable Multiway Circuit Partitioning for ECO. ICCAD 2003.

96. Alpert C.J. et all. Hypergraph Partitioning with Fixed Vertices. //V.19, №2, February 2002, pp. 267 271.

97. Мищенко M. H. Операторы мутации в эволюционных алгоритмах размещения. Перспективные информационные технологии интеллектуальные системы, №4 (16), 2003. с.130-135.

98. Глушань В.М. Графовые модели представления вычислительных алгоритмов. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2. М.: Физматлит, 2003, с. 133 - 138.

99. Мак W.K. Mic Cut Partitioning With Functional Replication for Technology - Mapped Circuits Using Minimum Area Over hed. //V.21, №4, april 2002, - pp. 491 - 496

100. Курейчик B.B. Эволюционные, синергетические и гомеостатические методы принятия решений. Монография. Таганрог: Изд-во ТРТУ, 2001.

101. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.М.: МЦНМО, 2000.

102. Батищев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа. Нижний Новгород, Нижегородский госуниверситет, 1994.