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

15

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

Баринов Сергей Владимирович

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Таганрог-2008

Ь 1 15

003445115

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

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

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

заслуженный деятель науки РФ, доктор технических наук, профессор Курейчик В.М

доктор технических наук, профессор Витиска Николай Иванович (Таганрогский государственный педагогический институт, г Таганрог)

доктор технических наук, профессор Ковалев Сергей Михайлович (Ростовский государственный университет путей сообщения, г Ростов-на-Дону)

Ведущая организация- Федеральное государственное

унитарное предприятие Таганрогский НИИ Связи

Защита состоится «28» августа 2008 г в 14 20 на заседании диссертационного совета Д 212.208 22 при Южном федеральном университете по адресу 347928, Таганрог, пер Некрасовский, 44, ауд Д-406

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

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

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

диссертационного совета Д 212 208 22, доктор технических наук, профессор

Целых А Н

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

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

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

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

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

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

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

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

2 Новые и усовершенствованные механизмы генетического поиска: учет «времени жизни» хромосом в популяции, применение принципов Парето оптимизации и распараллеливание процесса поиска

3. Новые и усовершенствованные методы свертки гиперграфа на основе алгоритмов сжатия гиперребер, агрегации фракталов, применяемые с целью

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

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

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

6. Новый проблемно-ориентированный генератор начальной популяции на основе получения оптимальных строительных блоков

7. Усовершенствованные операторы генетического поиска на основе фигурных чисел, обеспечивающие уменьшение времени поиска.

Научная новизна работы.

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

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

3. Предложен модифицированный генетический алгоритм на основе модели эволюции Ч Дарвина, использующий принципы Парето оптимизации.

4. Представлены новые и усовершенствованные алгоритмы свертки гиперграфа на основе нахождения сжатия гиперребер, агрегации фракталов.

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

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

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

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

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

3. Программный комплекс «РОАСотркх» решения задачи разбиения схем с учетом временных задержек.

Реализация результатов работы. Результаты работы внедрены в научно-исследовательских работах, выполняемых на кафедре САПР ГШ ЮФУ.

Апробация работы. Основные результаты диссертационной работы обсуждались и были одобрены на Всероссийских научно-технических конференциях «Проблемы разработки перспективных микроэлектронных систем»

(2005-2006 гг.), Международных научно-технических конференциях «Интеллектуальные САПР» (п Дивноморское, 2005 - 2007 гт), международной конференции «Интеллектуальные системы (IEEE AIS'06)» (п Дивноморское, 2005г ), международной молодежной научно-технической конференции "Интеллектуальные системы в науке, технике, образовании, бизнесе" (п Дивноморское, 2007 г ), IV-й Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте»(г Коломна, 2007 г.)

Публикации. Результаты диссертации отражены в 9 печатных работах

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы Работа содержит 155 страниц, включая 55 рисунков, 15 таблиц, список литературы из 106 наименований, 5 страниц приложений с актами об использовании работы

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

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

В ПЕРВОЙ ГЛАВЕ приводится общая постановка задачи разбиения схем на фрагменты по критерию суммарного количества межблочных связей и анализ существующих алгоритмов разбиения схем

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

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

При представлении схемы гиперграфом вершинам ставятся в соответствие элементы схемы, а ребрам- межэлементные соединения Задача разбиения схем состоит в отыскании такого разбиения р,р С Р некоторого гиперграфа

H(X,U), представляющего модель схемы, при котором минимизируется

целевая функция F и учитываются все поставленные в задаче ограничения.

Необходимо разбить множество вершин X на к непустых и непересекающихся подмножеств Xz

р = {Хг\2 = \,...,к};Х = {]Х2,(У1,ЛХ,глХ;=0,Х2*0

На каждое подмножестве Х2 накладывается следующее ограничение.

ч>{Х) / ск < м;(Х1) < сх^Х) I к, где м(Х) - суммарный вес всех вершин гиперграфа, М?(Х2) - вес вершин подмножества Xж, С - коэффициент отклонения веса, 1 < С < 2 .

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

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

ВО ВТОРОЙ ГЛАВЕ проанализированы основные положения теории генетического поиска, показаны преимущества методов эволюционного моделирования по сравнению с традиционными эвристическими методами решения № - полных задач Выделены принципы эволюционного поиска, ориентированные на решение задачи разбиения схем на фрагменты.

Предложена модифицированная форма представления и кодирования исходных данных В данном случае альтернативное решение(хромосома) представляется в виде последовательности размера П + к — 1 Позиции {1,..., п} представляют исходное множество объектов разбиения Дополнительные позиции {п + 1,..., п + к — 1} служат для кодирования разделителей Например, разбиение 7 элементов на 3 куска кодируется следующим образом. (1,2,8,3,4,5,9,6,7) Множество {8, 9} представляет разделители полученного разбиения Предложенный метод кодирования позволяет избежать нелегальных решений, в частности отсутствия некоторых кусков разбиения Однако, возможно дублирование объектов разбиения после применения генетических операторов Это может оказаться полезным в случае решения задачи разбиения схем с дублированием элементов

Рассмотрены и предложены модифицированные модели эволюций Ч Дарвина и Ж Ламарка

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

Алгоритм стартует с начальной популяцией N и пустой популяцией

Парето Ыа, а < п Для всех хромосом вычисляется ЦФ и недоминантные решения помещаются в популяцию Парето. Хромосомы, которые уже содержатся

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

Величина ЦФ хромосом определяется следующим образом. Для

недоминантных хромосом значение ЦФ умножается на коэффициент S.,

S = . S, < 1, где ' N +1 '

nt - число хромосом в текущей популяции Парето, над которыми доминирует хромосома /, N - общее число хромосом в популяции Значение ЦФ

доминантной хромосомы умножается на параметр К j

ТД - сумма значений устойчивости Парето-оптимальных хромосом, 1

которые доминируют над хромосомой j

После этапа определения ЦФ хромосом, обе популяции объединяются для применения проблемно-ориентированных генетических операторов

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

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

p{P{t +1)) = p(P{t)) + p{P0{t)) - D(t), где

p(P(t +1)) - размер популяции поколения / +1, p(P(t)) - размер популяции

поколения t, р(Р0 (V)) -популяция потомков поколения t, D(t)- число

хромосом, которые «умирают» в течение генерации t

В разработанном алгоритме используется следующее выражение для подсчета «времени жизни» хромосомы l.

Javg J mm , ГДе

Il f( f

T ((A,,n + (L^ -£mJ JfKl) _ Jp ), favg<f(i) (b)

J max J avg

L{i) - «время жизни» хромосомы i, Lmm и Lmax - соответственно минимальное и максимальное заданное «время жизни», fi - ЦФ хромосомы, fmm, fmax и

- соответственно минимальное, максимальное и среднее значение ЦФ

популяции Если среднее значение ЦФ популяции больше ЦФ хромосомы, то «время жизни» вычисляется согласно выражению а) В противном случае вычисляется выражение Ь)

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

Р{Х1) = е~^'\где

Р(АГ|) - вероятность выбора хромосомы в «турнир» индивидов, /{Х^ -

значение ЦФ хромосомы, параметр Т определяет толерантность ГА, как и температура в моделировании отжига

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

Разработана многопопуляционная архитектура эволюционного поиска для получения оптимальных решений задачи разбиения схем. В предлагаемой архитектуре из исходной популяции хромосом выделяется четыре подпопуляции В качестве структуры взаимодействия между подпопуляциями(топологии) выбрана структура тетраэдра Миграция хромосом происходит по закону «утечки мозгов», т е. когда популяцию покидают хромосомы с лучшими значениями ЦФ Кроме качественных характеристик, эффективность миграции зависит от количества хромосом, участвующих в обмене, а также частоты возникновения миграции. Оптимальная частота миграции в данном случае определяется выражением р = \ 18 + \, где 8 - степень топологии (степень предложенной топологии равна 3)

Общая разработанная архитектура генетического алгоритма разбиения схем показана на рис I

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

Начато

Конструирование популяции с помощью разработанного гимртора хромосом

Ракямроааиие популяции на основа определения значения ЦФ фомосом

С

Разбиение популяции н8 части Вмбор модели Эволюции ДЛЯ каждой из лодлолуляций

Рис 1 Архитектура генетического алгоритма разбиения схем

В ТРЕТЬЕЙ ГЛАВЕ описана многоуровневая архитектура поиска, позволяющая эффективно использовать разработанные генетические алгоритмы.

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

Дня этапа свертки гиперграфа разработаны два алгоритма метод свертки на основе сжатия гиперребер, а также алгоритм свертки гиперграфа на основе агрегации фракталов

Рассмотрим метод свертки гиперграфа на основе сжатия гиперребер. Вначале все гиперребра сортируются по возрастанию количества вершин в них, а при равном значении этого показателя - по убыванию суммарного веса содержащихся в ребре вершин. Затем выбирается гиперребро и из всех вершин, входящих в него, формируется новое подмножество Сформированное

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

Кроме метода на основе сжатия гиперребер, предлагается алгоритм кластеризации на основе агрегации фракталов Используются идеи построения минимальных массивов в гиперграфе Кластер - это часть графа ФсС Кластер Фк называется минимальным, если для любого другого кластера Фу С Ф^ выполняется условие /к < / , то есть удаление произвольных

вершин из Ф^ (Ф^ \ X 2 ) приводит к новому кластеру с большим числом

внешних ребер Структурная схема алгоритма представлена ниже.

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

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

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

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

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

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

В общей модели временной задержки, каждая вершина графа имеет задержку с1(\>), и каждое ребро имеет задержку, определяемую следующим образом

[Десли е = (м,у)еЕ,иеВ„уеВ I*] а(е) = < >1ДС

(О,если е = (и,у)еЕ,и,увВ,

О - максимальная временная задержка, возникающая на межблочных соединениях

Для определения Э в работе используется формула задержки Эльмора

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

2=1

СС,Р - веса целевой функции, СС + /? = 1, С2 -число ребер куска Xг, попавших в разрез, ) - вес вершин подмножества Xг, <3 - величина

оценки текущей временной задержки, с/тах - верхняя оценка величины

временной задержки

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

треугольных чисел. Последовательность треугольных чисел Тп задается

следующей формулой ^ = 0 5г^„ + !),„ = 1,2,3,..

Если длина " хромосомы равна 10, то

последнее фигурное чисто для выполнения ГО равно 6 Число точек разрыва выбирается случайно на основе полученного множества фигурных чисел. Для примера, число точек разрыва может быть 1, 3, или 6 После определения точек разрыва хромосомы-потомки, получаются путем чередования строительных блоков родителей В случае возникновения нелегальных решений применяется механизм коррекции ошибок

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

При L = 13 ряд фигурных чисел для выполнения ГО имеет вид 1, 3, 6, 10. Случайным образом выбираем число точек мутации из отрезка [1;4] Выберем 4 точки мутации Тогда ОМ будут подвержены гены в позициях 1, 3, 6, 10, согласно ряду фигурных чисел.

Pi I ' I Ч" h I < 1 ' I « I ' 14 '1

р\ [Т I | 12 13 | 10 | 2 II | 4 | 7 [ 5 8 | й | 9 |

Рис 4 Пример выполнения оператора мутации

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

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

Нк-1' Нх .

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

На текущем уровне дерева свертки мы имеем некоторый гиперграф Нк

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

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

В ЧЕТВЕРТОЙ ГЛАВЕ определены теоретические оценки пространственной и временной сложности разработанных алгоритмов Экспериментальные исследования проводились на 18 тестовых схемах ISPD98 Первая из них имеет 12506 элементов, последняя - 210341 элемент Тестирование и экспериментальные исследования проводились с помощью специализированного программного обеспечения (ПО), разработанною на объектно-ориентированном языке программирования Java версии 1 6 в среде

I» ||з||2{|0|||[2 |4 |, |, I | 12 "Гз | 10 | 2 I I | 4 | 7 [ Т

NetBeans IDE 6 0 Для тестирования использовалась операционная система Microsoft Windows ХР Professional™ Service Pack 2 Для экспериментов использовались следующие аппаратные средства- AMD Sempron™ 3500+ (2.16 ГГц), 512 Mb оперативной памяти

Для хранения в памяти схемы ibmOl потребовалось 3904 кб, для ibml8 -61424 кб. По результатам проведенного исследования выявлено, что для

хранения в памяти исходной схемы требуется Sl = OcNM кб памяти, где N •

число элементов, М - число соединений схемы

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

его временная сложность составляет 0(п2). В то же время, метод свертки на основе сжатия является более предпочтительным, поскольку его временная сложность пропорциональна линейной зависимости

Определена оптимальная вероятность применения генетических операторов на этапе начального разбиения, оператор кроссинговера - 80%, оператор мутации - 6%; на этапе развертки схемы оптимальная вероятность генетических операторов составляет* оператор кроссинговера - 90%, оператор мутации - 4%.

Проведены исследования по определению оптимального числа поколений на этапах начального разбиения и развертки схемы. Время работы алгоритма линейно зависит от числа поколений на этапе начального разбиения и резко возрастает с увеличением числа поколений на этапе развертки схемы Оптимальные значения числа поколений составляют- число поколений генетического алгоритма на этапе начального разбиения - 230; число поколений генетического алгоритма на этапе развертки схемы - 90

Проведены серии экспериментов по определению эффективности разработанного программного комплекса по сравнению со стандартным алгоритмом разбиения hMetis.

500 1000 1500 ZOOO 2500 3000 3500 4000 4900 5000 0 500 1000 1500 2000 »00 |__________■ __ар— рЛт!.вп_

[■ ЬМац«) Q РОДСодук^) ] [а ЬМЫЩ«) D РСАСсттрМ«)!

Рис 5 Качество решений Рис б Время работы алгоритмов

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

На рис 6 представлена диаграмма, показывающая время работы сравниваемых алгоритмов на тестовых схемах По горизонтальной оси отмечается время работы алгоритмов, по вертикальной - тестовые примеры Например, для разбиения тестовой схемы lbmOl, содержащей 12506 элементов и 14111 соединений, время работы разработанного алгоритма составляет 93 сек

Судя по результатам экспериментов, разработанный алгоритм получает оптимальные результаты, которые в среднем превосходят результаты аналога на 5-10%

Для оценки эффективности разработанного программного комплекса PGAComplex с точки зрения величины временной задержки были проведены исследования на тестовом наборе схем ISCAS На рис 7 представлена гистограмма для определения качества решений по оценке временной задержки По горизонтальной оси представлены тестовые схемы, по вертикальной - оценка временной задержки для тестовой схемы.

Рис 7 Качество решений по оценке временной задержки

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

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

что временная сложность разработанного комплекса близка к 0{п2 )

В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы.

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

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

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

задачи разбиения СБИС на фрагменты

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

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

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

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

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

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

6 Предложен гибридный генетический алгоритм разбиения схем на фрагменты для этапа развертки схемы Применение «жадной» эвристики в сочетании с генетическим поиском позволяет избежать преждевременной сходимости алгоритма

7 Создан программный комплекс на объектно-ориентированном языке программирования Java в среде NetBeans IDE 6 0, реализующий разработанные алгоритмы С помощью проведенных экспериментальных исследований определены оптимальные числовые значения для управляющих параметров

8 На этапе исследований разработанных алгоритмов экспериментально определена временная сложность алгоритма Временная сложность алгоритма в худшем случае пропорциональна 0(/3N2), где N - количество элементов схемы.

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

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

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

1. Баринов С В , Гладков Л. А. Анализ разработанной структуры данных для решения задач схемной компоновки на основе многоуровневого подхода -Известия ТРТУ Таганрог Изд-во ТРТУ, 2005, №3(47) С 141-144

2. Баринов С В, Гладков Л А Компоновка МЭС на основе многоуровневого подхода. Проблемы разработки перспективных микроэлектронных систем -2005. Сборник научных трудов /под общ. ред A JI. Стемпковского - М.-ИППМ РАН, 2005. С. 136-141

3 Баринов С В, Иванько А.В, Щеглов С.Н. Основные средства автоматизированного проектирования печатных плат компании CADENCE DESIGN SYSTEMS Перспективные информационные технологии и интеллектуальные системы, №1(25)/ 2006, -с 52-57

4 Баринов С.В , Курейчик В М , Гладков Л А Компоновка МЭС на основе итерационной кластеризации с учетом временных задержек Известия ТРТУ Таганрог: Изд-во ТРТУ, 2006 №8(63). С 120-127

5. Баринов С В, Курейчик В М., Гладков Л А Компоновка МЭС на основе итерационной кластеризации с учетом временных задержек II Всероссийская научно-техническая конференция «Проблемы разработки перспективных микроэлектронных систем - 2006». Сборник научных трудов/ под общ ред А Л. Стемпковского - М.. ИППМ РАН, 2006. С. 130-135

6. Баринов С В , Курейчик В М. Обзор методов учета временных задержек при логическом синтезе Известия ТРТУ.-Таганрог. Изд-во ТРТУ,2007,№ 1 (73),с.75-77.

7 Баринов С В, Курейчик В М, Гладков Л А. Развитие технологии производства печатных плат Разработка алгоритма трехмерной компоновки СБИС на основе итерационной кластеризации с учетом временных задержек Известия ЮФУ -Таганрог. Изд-во ТТИ ЮФУ, 2007, №2(77) С. 47-53 8. Баринов С.В, Гладков Л А Компоновка МЭС на основе многоуровневого подхода. Материалы IV-й Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» М- Изд-во Физматлит 2007 С 300-305 9 Баринов С В., Гладков Л А Компоновка МЭС на основе многоуровневого подхода «Нано- и микросистемная техника», №2/2007 с. 33-39

Личный вклад автора в работах, опубликованных в соавторстве [1] -разработка эффективной структуры данных для решения задачи схемной компоновки,[2,4,5] - разработка алгоритмов разбиения схем на фрагменты с учетом временных задержек; [3] - обзор средств автоматизированного проектирования фирмы Cadence для этапа конструкторского проектирования, [6] - анализ различных моделей оценки временной задержки для задачи разбиения схем, [7-9] - программная реализация разработанного алгоритма разбиения схем на основе многоуровневого подхода

Соискатель Баринов С В.

Тип ТТИ ЮФУ Заказ тир /¿'¿'экз

Содержание

Введение

1. Анализ и состояние проблемы компоновки СБИС

1.1. Состояние и тенденции развития полупроводниковой отрасли

1.2.Графовые и гиперграфовые модели СБИС

1.3.Анализ алгоритмов разбиения графовых моделей для задачи разбиения схем

1.4. Выводы

2. Разработка архитектуры, стратегии и выбор модели эволюционного поиска для этапа компоновки СБИС

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

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

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

2.4.Эволюционные модели для задачи разбиения СБИС.

2.5.Этапы проектирования архитектуры эволюционного моделирования для задачи разбиения СБИС.

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

2.7.Выводы

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

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

3.2.Алгоритм разбиения схем на основе кластеризации с учетом временных задержек.

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

3.4.Этап начального разбиения. Определение оптимальности особей популяции. Алгоритм вычисления целевой функции на этапе начального разбиения

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

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

3.7.Выводы 109 4. Экспериментальные исследования разработанного программного комплекса разбиения СБИС.

4.1. Теоретическая оценка разработанного комплекса генетических алгоритмов разбиения схем на фрагменты

4.2.Краткое описание программной и аппаратной среды

4.3.Цель экспериментальных исследований

4.4.Этапы экспериментальных исследований

4.5.Результаты экспериментальных исследований

4.6.Выводы 140 Заключение 142 Список использованной литературы 144 ПРИЛОЖЕНИЕ

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

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

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

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

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

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

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

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

• Разработка поисковых методов разбиения схем с учетом временных задержек.

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

• Разработка параллельных и гибридных генетических алгоритмов разбиения схем на фрагменты с учетом временных задержек.

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

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

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

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

3. Предложен модифицированный генетический алгоритм на основе модели эволюции Ч. Дарвина, использующий принципы Парето оптимизации.

4. Представлены новые и усовершенствованные алгоритмы свертки гиперграфа на основе нахождения сжатия гиперребер, агрегации фракталов.

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

6. Предложен новый гибридный генетический алгоритм разбиения схем, включающий в себя «жадную» эвристику улучшения разбиения.

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

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

Решение поставленных задач позволяет автору защищать следующие новые научные результаты:

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

2. Стратегии взаимодействия поисковых методов и генетических алгоритмов для решения задачи разбиения схем на фрагменты.

3. Генетические алгоритмы, использующие принципы Парето оптимизации, а также механизм варьирования размера популяции на основе учета «времени жизни» хромосом.

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

5. Модифицированные генетические операторы на основе фигурных чисел.

Практическая ценность результатов диссертационной работы определяется созданием комплекса алгоритмов разбиения схем с учетом временных задержек, позволяющих использовать разработанные математические модели, стратегии, концепции, принципы, методы и эвристики. Разработана программный комплекс «PGAComplex» для решения поставленной задачи на основе объектно-ориентированного языка Java 1.6 в среде NetBeans IDE 6.0. Отладка и тестирование проводились на ЭВМ типа IBM PC с процессором AMD Sempron 3500+ с ОЗУ объемом 512Мб. Проведенные экспериментальные исследования показали преимущество разработанных методов для решения задачи разбиения схем с учетом временных задержек. Время получения лучших результатов разбиения схем соответствует полиномиальному времени и лежит в пределах от O(nlogn) до 0(п2).

Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных и хоздоговорных работах, проводимых в Таганрогском Технологическом Институте Южного Федерального Университета: грант РФФИ № 01-01-00044 «Эволюционное проектирование с адаптацией»; грант РФФИ на проведение фундаментальных исследований в области технических наук № 02-01-01275 «Разработка теории и принципов эволюционного проектирования на основе многоагентных подходов»; госбюджетная работа по заказу Минобразования РФ «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений».

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

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

Международной научно-технической конференции «Интеллектуальные САПР» (г. Дивноморск, 2005 - 2007 гг.), IV-й Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте»(г. Коломна, 2007г.).

Публикации. Результаты диссертации отражены в 9 печатных работах.

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

4.6. Выводы.

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

2. Проведены экспериментальные исследования на тестовых примерах ISPD98[96] и ISCAS. Определены сочетания динамических параметров, которые позволяют повысить качество решений. По результатам экспериментов, для каждого параметра даны рекомендации диапазона оптимальных значений, обеспечивающих возможность получения локальнооптимальных решений

3. Комплекс генетических алгоритмов при разбиении СБИС с учетом временных задержек показали преимущество по сравнению с аналогичным алгоритмом разбиения hMetis. Качество получаемых решений удалось повысить ориентировочно на 5%-10%.

Заключение

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

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

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

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

4. Предложен модифицированный генетический алгоритм на основе модели эволюции Ч. Дарвина, использующий принципы Парето оптимизации.

5. Представлены новые и усовершенствованные алгоритмы свертки гиперграфа на основе нахождения сжатия гиперребер, агрегации фракталов.

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

7. Предложен новый гибридный генетический алгоритм разбиения схем, включающий в себя «жадную» эвристику улучшения разбиения.

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

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

10.Разработана инструментальная среда по исследованию характеристик комплекса генетических алгоритмов компоновки СБИС, обладающая лучшими характеристиками по сравнению с известными аналогами в области разбиения СБИС. При создании программы использовалась среда разработки NetBeans IDE 6.0, что позволило обеспечить удобный интерфейс пользователя и визуализацию работы алгоритма.

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

•л близка к 0(п ), а объем требуемой памяти линейно зависит от размерности задачи.

12.Иерархический комплекс генетических алгоритмов при разбиении СБИС с учетом временных задержек показали преимущество по сравнению с аналогичным алгоритмом разбиения hMetis. Качество получаемых решений удалось повысить ориентировочно на 5%-10%.

1. Норенков И.П. Принципы построения и структура САПР. М.: Высшая школа, 1986.

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

3. IBM Moves Moore's Law into the Third-Dimension. http.Y/www-03 .ibm.com/press/us/en/21350.wss.

4. Шаг в новое измерение: IBM совершает переворот в полупроводниковой отрасли, http://www.ixbt.eom/news/all/index.shtml705/44/l 0.

5. Сергей Шашлов. Закону Мура — 40 лет!. 20.04.2005, http://www.ixbt.com/editorial/moorelaw40th.shtml.

6. В. Немудров, Г. Мартин. Системы-на-кристалле. Проектирование и развитие. Москва: 2001.

7. В. А. Овчинников. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем. Москва: Изд-во МГТУ им. Баумана, 2001.

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

9. Фридман А. Д., Менон П. Р. Теория и проектирование переключательных схем.-М.: Мир, 1978.

10. Charles J. Alpert, Andrew В. Kahng. Recent directions in netlist partitioning. Integration, the VLSI Journal, 19(1-2):1-81,1995.

11. Баринов С. В., Иванько А.В., Щеглов С.Н. Основные средства автоматизированного проектирования печатных плат компании CADENCE DESIGN SYSTEMS. Перспективные информационные технологии и интеллектуальные системы, №1(25)/ 2006, -с. 52-57.

12. Т. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Wiley-Teubner, 1990.

13. J. Cong, L. Hagen, A. B. Kahng. Net partitions yield better module partitions. In Proc. ACM/IEEE Design Automation Conf. Computer-Aided Design, p. 56-62,1994.

14. C. W. Yeh, C.-K. Cheng, T.-T. Y. Lin. A general purpose, multiple-way partitioning algorithm. IEEE Trans. Computer-Aided Design, 13(12), p. 14801487, 1994.

15. J. Cong, Z. Li, R. Bagrodia. Acyclic multi-way partitioning of Boolean networks. In Proc. ACM/IEEE Design Automation Conf., p. 47-52, 1992.

16. S. Iman, M. Pedram, C. Fabian, J. Cong. Finding uni-directional cuts based on physical partitioning and logic restructuring. Zin Proc. ACM/SIGDA Physical Design Workshop, p. 187-198, Los Angeles, 1993.

17. P. K. Chan, M. D. F. Schlag, J. Y. Zien. Spectral k-way ratio-cut partitioning and clustering. IEEE Trans. Computer-Aided Design, 13(8), p. 1088-1096, 1994.

18. C. W. Yeh, C.-K. Cheng, T.-T. Y. Lin. A probabilistic multi-commodity flow solution to circuit clustering problems. In Proc. IEEE Intl. Conf. Computer-Aided Design, p. 428-431, 1992.

19. W. Sun, C. Sechen. Efficient and effective placements for very large circuits. In Proc. IEEE Intl. Conf. Computer-Aided Design, p. 170-177, 1993.

20. D. J.-Huang, A. B. Kahng. When clusters meet partitions: New density-based methods for circuit decomposition. In Proc. European Design and Test Conf,1995.

21. Автоматизация проектирования БИС. В 6 кн. Под ред. Г.Г. Казеннова. М.: Высшая школа, 1990.

22. N.-C. Chou, L.-T. Liu, C.-K. Cheng, W.-J. Dai, R. Lindelof. Circuit partitioning for huge logic emulation systems. In Proc. ACM/IEEE Design Automation Conf., p. 244-249,1994.

23. D. J.-Huang, A. B. Kahng. Multi-way system partitioning into single or multiple type FPGAs. In Proc. ACM/SIGDA International Workshop on Filed-Programmable Gate Arrays, p. 140-145, 1995.

24. R. Kuznar, F. Brglez, K. Kozminski. Cost minimization of partitions into multiple devices. In Proc. ACM/IEEE Design Automation Conf, p. 315-320, 1993.

25. B. W. Kemigan, S. Lin. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. Journal, 49(2), p. 291-307,.1970.

26. С. M. Fidduccia, R. M. Mattheyses. A linear time heuristic for improving network partitions. In Proceedings ACM/IEEE Design Automation Conference, p. 175-181, 1982.

27. S. Dutt. New faster kernigan-lin-type graph-partitioning algorithms. In Proc. IEEE International Conference Computer-Aided Design, p. 370-377, 1993.

28. B. Krishnamurthy. An improved min-cut algorithm for partitioning VLSI networks. IEEE Trans. Computers, 33(5), p. 438-446,1984.

29. S. Kirkpatrick, C. D. Gellat, Jr., M.P. Vecchi. Optimization by simulated annealing. Science, 220, p. 671-680, 1983.

30. S. Geman, D. Geman. Stochastic relaxation, gibbs distribution, and the Bayesian restoration of images. IEEE Trans. Pattern Analysis and Machine Intelligence^, p. 721-741, 1984.

31. B. Hajek. Cooling schedules for optimal annealing. Mathematics of Operations Research, 13(2), p. 311-329, 1988.

32. P. J. M. Laarhoven, E. H. L. Aarts. Simulated Annealing: Theory and Applications. D. Reidel, Boston, 1987.

33. D. S. Johnson, C. R. Aragon, L. A. McGeoch, C. Shevon. Optimization by simulated annealing: An experimental evaluation part i, graph partitioning. Operations Research, 37, p. 865-892, 1989.

34. F. Glover. Tabu search part i. ORSA Journal on Computing, 1, p. 190-206, 1989.

35. P. E. Gill, W. Murray, M. H. Wright. Practical Optimization. Academic Press, 1981.

36. M. Shih, E. Kuh. Quadratic Boolean programming for performance-driven system partitioning. In Proc. ACM/IEEE Design Automation Conf., p. 761-765, 1993.

37. L. T. Liu, M. Shih, С. K. Chen, N>-C. Chou, W. Ku. Perfomance driven partitioning using retiming and replication. In Proc. IEEE International Conference Computer-Aided Design, o. 296-299, 1993.

38. C. Kring, A. R. Newton. A cell-replicating approach to mincut-based circuit partitioning. In Proc. IEEE Intl. Conf. Computer-Aided Design, p. 2-5, 1991.

39. J. Hwang, A. El Gamal. Optimal replication for min-cut partitioning. In ICC AD, p. 432-435,1992.

40. R. Kuznar, F. Brglez, B. Zajc. Multi-way netlist partitioning into heterogeneous fpgas and minimization of total device cost and interconnect. In Proc. ACM/IEEE Design Automation Conf., p. 238-243, 1994.

41. D. Karger. Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm. In Proc. ACM/SLAM Symposium Discrete Algorithms, p. 21-30, 1993.

42. T. Bui, S. Chaudhuri, T. Leighton, M. Sipser. Graph bisection algorithms with good average case behavior. Combinatorica, 7(2), p. 171-191, 1987.

43. T. Bui, C. Heigham, C. Jones, T. Leighton. Improving the performance of the Kernigan-lim and simulated annealing graph bisection algorithms. In Proc. ACM/IEEE Design Automation Conf., p. 775-778, 1989.

44. K. Roy, C. Sechen. A timing-driven n-way chip and multi-chip paititioner. In Proc. IEEE Intl. Conf. Computer-Aided Design, p. 240-247, 1993.

45. S. Hauck, G. Borriello. An evaluation of bipartitioning techniques. In Proc. Chapel Hill Conference on Advance Research in VLSI, 1995.

46. G. Karypis and V. Kumar. Analysis of multilevel graph partitioning. Technical Report TR 95-037, Department of Computer Science, University of Minnesota, 1995. http://www.cs.umn.edu/lcarypis/papers/mlevel analysis.ps.

47. Karypis, G. and Kumar, V. (1999b). Multilevel k-way hypergraph partitioning. In Proceedings of the Design and Automation Conference http://www.cs.umn.edu/Tcarypis.

48. Karypis, G. Multilevel algorithms for multiconstraint hypergraph partitioning. Technical Report TR 99-034, Department of Computer Science, University of Minnesota, 1999.

49. Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. Multilevel hypergraph partitioning: Application in vlsi domain. IEEE Transactions on VLSI Systems, 20(1), 1999.

50. J. Cong, H. Li, C. Wu. Simultaneous circuit partitioning/clustering with retiming for performance optimization. In Proc. ACM Design Automation Conference, 1999.

51. J. Cong, S. K. Lim. Perfomance driven multiway paertitioning. In Proc. IEEE/ASM Asia South Pacific Design Automation Conference, 2000.

52. C. N. Sze, T.-C. Wang, L.-C. Wang. Multilevel circuit clustering for delay minimization, In Proc. IEEE Trans. On Computer-Aided Design, 23, p. 10731085.'

53. R. Rajaraman, D. F. Wong. Optimal clustering for delay minimization. In Proc. ACM/IEEE Design Automation Conference, p. 309-314,1993.

54. E. L. Lawler, K. N. Levitt, J. Turner. Module clustering to minimize delay in digital networks. IEEE Transactions Computers, 18, p. 47-57, 1969.

55. R. Murgai, R. K. Bray ton, A. Sangiovanni-Vincentelli. On clustering for minimum delay/area. In Proc. IEEE Intl. Conf. Computer-Aided Design, p. 6-9, 1991.

56. J. Cong, Y. Ding. An optimal technology mapping algorithm for delay optimization in lookup-table based fpga designs. In Proc. IEEE Itl. Conf. Computer-Aided Design, p. 48-53, 1992.

57. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. —М.: ФИЗМАТЛИТ, 2003. 432 с.

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

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

60. Курейчик В.В.,Сороколетов П.В. Эволюционные алгоритмы разбиения графов и гиперграфов. Известия ТРТУ,№3, 2004, с.23-32.

61. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. -М.: Эдиториал УРСС, 2002. -352с.

62. Хакен Г. Тайны природы. М.: Институт компьютерных исследований, 2003.

63. Курейчик В. В., Полупанов А.А. Эволюционные методы разбиения схем на основе адаптивных генетических процедур.- Таганрог: Изд-во Технологического института ЮФУ, 2007 160 с.

64. Дубинин Н.П. Избранные труды, Т.1. Проблемы гена и эволюции. М.: Наука, 2000.

65. Zbigniew Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs, Third, Revised and Extended Edition, Springer- Verlag Berlin Heidelberg New York, 1996, 388p.

66. Andreas Rummler, Adriana Apetrei. Graph Partitioning Revised a Multiobjective Perspective, In Proc. IEEE Itl. Conf. Computer-Aided Design, p. 45-51,2001.

67. Grefenstette, J.J., Optimization of Control Parameters for Genetic Algorithms, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 16, No.l, pp. 122128, 1986.

68. Goldberg, D.E., Optimal Initial Population Size for Binary-Coded Genetic Algorithms, TCGA Report No.85001, Tuscaloosa, University of Alabama, 1985.

69. Goldberg, D.E., Sizing Populations for Serial and Parallel Genetic Algorithms, in Proceedings of the Third International Conference on Genetic Algorithms (edited by Schaffer J.), Morgan Kaufmann Publishers, San Mateo, CA, 1989, pp.70-79.

70. Holland, J.H., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.

71. Lance Chambers. Practical handbook of genetic algorithms : new frontiers. Volume 2, 1996, 421 p.

72. Brindle, A., Genetic Algorithms for Function Optimization, Doctoral Dissertation, University of Alberta, Edmonton, 1981.

73. Baker, J.E., Adaptive Selection Methods for Genetic Algorithms, in Proceedings of the First International Conference on Genetic Algorithms, Lawrence Erlbaum Associates, Hillsdale, NJ, 1985., pp.101-111.

74. Рутковская Д., Пилиньский M., Рутковский JI. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И. Д. Рудинского. М.: Горячая линия - Телеком, 2006. -452с.

75. Schwefel, H.-P., Numerical Optimization for Computer Models, John Wiley, Chichester, UK, 1981.

76. Muhlenbein, H. and Schlierkamp-Vosen, D., Predictive Models for the Breeder Genetic Algorithm, Evolutionary Computation, Vol.1, No.l, pp.25-49, 1993.

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

78. Erick Cantu-Paz. Efficient and accurate parallel genetic algorithms, Kluwer Academic Publishers. Second Printing 2001, 167 p.

79. Erick Cantu-Paz. Migration Policies, Selection Pressure, and Parallel Evolutionary Algorithms, 24 p., 1999.

80. Haupt R. L., Haupt S. E. Practical Genetic Algorithms, Second edition, Wiley publishers, 2004, 26 lp.

81. Гладков JI. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы,-М: Физматлит, 2006.

82. Hendrickson, В. and Leland, R. A multilevel algorithm for partitioning graphs. Technical Report SAND93-1301, Sandia National Laboratories, 1993.

83. Баринов C.B., Гладков JI.A. Компоновка МЭС на основе многоуровневого подхода. Проблемы разработки перспективных микроэлектронных систем 2005. Сборник научных трудов /под общ. ред. А.Л. Стемпковского. - М.: ИППМ РАН, 2005. С. 136-141.

84. Баринов С.В., Курейчик В.М., Гладков Л.А. Компоновка МЭС на основе итерационной кластеризации с учетом временных задержек. Известия ТРТУ. Таганрог: Изд-во ТРТУ, 2006. №8(63). С. 120-127.

85. Баринов С.В., Гладков Л.А. Компоновка МЭС на основе многоуровневого подхода. Материалы IV-й Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте». М: Изд-во Физматлит 2007. С. 300-305.

86. Баринов С. В., Гладков Л. А. Компоновка МЭС на основе многоуровневого подхода. «Нано- и микросистемная техника», №2/2007 с. 33-39.

87. R. Bazylevych. The Optimal Circuit Reduction Method as an Effective Tool to Solve Large and Very Large Size Intractable Combinatorial VLSI Physical Design Problems. 10th NASA Symposium on VLSI Design, 2002.

88. C. J. Alpert. The ISPD-98 Circuit Beanchmark Suit,, in Proc. ACM/IEEE International Symposium on Physical Design, April 1998, pp.80-85.

89. Баринов C.B., Курейчик B.M. Обзор методов учета временных задержек при логическом синтезе. Известия ТРТУ.-Таганрог: Изд-во ТРТУ,2007, №1(73), с.75-77.

90. P. Pan, А. К. Karandikar, and С. L. Liu. Optimal Clock Period Clustering for Sequental Circuits with Retiming. IEEE Trans. On Computer-Aided Design of Integrated Circuits And Systems, 17(6):489-498, 1998.

91. Кормен Т., Лейзерсон И., Ривест Р. Алгоритмы: построения и анализ. М.: МЦМОДООО.

92. М. Шредер. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая. Научно-издательский центр «Регулярная и хаотичная динамика», 2001.

93. Chen С. P., Chen Y.P, Wong D. F. Optimal Wiresizing Under Elmore Delay Model // IEEE Trans. On CAD of Integrated Systems. 2002. - V. 21. - No.3. pp. 319-329.

94. J. Cong and D. Z. Pan. Interconnect estimation and planning for deep submicron designs. In Proc. ACM Design Automation Conf., pp. 507-510, 1999.

95. J. Rubinstein, P. Penfield, Jr., and M. A. Horowitz. Signal delay in RC tree networks. IEEE Trans. On CAD of Integrated Circuits and Systems, v. 2, pp. 202-211, 1983.

96. Semiconductor Industry Association. National Technology Roadmap for Semiconductors, 1997.

97. Ope. О. Приглашение в теорию чисел. Изд-во: Едиториал УРСС, 2003 г. 130с.

98. В.М. Курейчик. Гибридные генетические алгоритмы. Известия ЮФУ. Технические науки Тематический выпуск "Интеллектуальные САПР",-Таганрог: Изд-во ТТИЮФУ, 2007, №2(77). С. 5-12.

99. P. Mazumder and Е.М. Rudnick. Genetic Algorithms for VLSI Design, Layout and Test Automation. Prentice Hall, Toronto, Canada, 1999.

100. Баринов С. В., Гладков JI. А. Анализ разработанной структуры данных для решения задач схемной компоновки на основе многоуровневого подхода. -Известия ТРТУ. Таганрог: Изд-во ТРТУ, 2005, №3(47). С. 141-144.