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

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

БАЛКЖ Любовь Владимировна

□ОЗОВЗЭ55

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ИНТЕГРИРОВАННЫХ АЛГОРИ ГМОВ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ НА ОСНОВЕ МЕТОДОВ ЭВОЛЮЦИОННОГО МОДЕЛИРОВАНИЯ

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

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

1 * ИЮН 2007

Таганрог 2007

003063955

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

Научный руководитель Научный консультант Официальные оппоненты

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

доктор технических наук, профессор Курейчик Владимир Викторович

кандидат технических наук, доцент Нужное Евгений Владимирович

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

университет путей и сообщений, г Ростов-на-Дону),

кандидат технических наук, доцент Родзин Сергей Иванович

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

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

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

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

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

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

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

Целых А Н

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

Большой вклад в разработку и исследование интеллектуальных систем автоматизированного проектирования (САПР) ЭВС внесли В И Анисимов, Б В Баталов, Д И Батищев А.М Бершадский, Л С Берштейн, Ю.Х. Вермишев, В М. Курейчик, В В Курейчик, Н Я Матюхин, А Н Мелихов, И.П Норенков, В А Селютин, Ш Айкерс, М Бреуэр, Н Шервани и многие другие

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

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

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

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

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

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

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

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

2 Разработаны бионические алгоритмы размещения

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

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

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

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

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

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

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

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

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

• новая интегрированная архитектура процесса размещения фрагментов и/или групп фрагментов БИС, основанная на методах эволюционного моделирования,

• новая модифицированная архитектура алгоритма Ant Colony для решения задачи размещения фрагментов БИС,

• новые и усовершенствованные операторы генетического поиска на основе «Золотого сечения», кодов Хаффмана, метода «Простых чисел», обеспечивающие уменьшение времени поиска Практическая ценность работы заключается в реализации программного комплекса «In4Placement», использование которого позволяет на 10-30% ускорить процесс синтеза сложных систем, повысить качество размещения на" 29% по сравнению с существующими аналогами, благодаря использованию интегрированного подхода к решению задачи размещения Данная среда позволяет автоматизировать процесс размещения, сделать его доступным для специалистов различных областей науки, не обладающих навыками программирования

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

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

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

2004 г), Ш Всероссийская научная конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», (г Таганрог, 2005 г), 1 ежегодная научная конференция студентов и аспирантов базовых кафедр ЮНЦ РАН, (г Ростов-на-Дону, 2005 г), Международная конференция «Интеллектуальные системы (IEEE AIS'05)», (с Дивноморское,

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

Получено свидетельство об официальной регистрации программы для ЭВМ № 2006613139, 2006 г

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

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении дано обоснование актуальности темы диссертационной работы, описаны цель работы и основные научные положения, выносимые на защиту, определены круг задач, объект и предмет исследования, указаны методы исследования, показаны научная новизна и практическая значимость, а так же подтверждены достоверность полученных результатов

В первой главе рассмотрены основные проблемы и перспективы решения задач размещения приведена постановка задачи размещения фрагментов БИС Решаемая в диссертационной работе дискретная задача размещения может быть сформулирована следующим образом На прямоугольную конструкцию накладывается Декартова система координат с осями s и / определяющая граф G,, задающий собой координатную решетку

Задача размещения сводится к отображению заданного графа-моде™ G-(X. !J) схемы в решетку G, таким образом, чтобы множество вершин X = {х } ■.

1 = графа G размещалось в узлах решетки, число которых конечно, а также соблюдался интегрированный критерий С ompl(G) представ 1яющий собой интегрированную целевую функцию (ЦФ)

[С ompl (G) = Compl _ Kr(G), ее ш V Кг >0 и N _ G 4 = 0, <1)

JComp!{G)= L_GA{G) ест ,V Ki = 0h,V_G/4>0,

[compHG) = aL_GA(G)~ ßCompl _Kt(G),ecm Д'_ Kr>0u Л _GA >0,

где

• L Ki (G) - длина критических связей (длина гамильтоновых цепей в графе),

• L_G4(G) - величина суммарной длины соединений стремилась к минимуму,

• N Кг' 0 к N G4=0 - условие оптимизации ЦФ, основанное на соблюдении критерия длин критических связей,

• N_Kr-0 и V G1X) - условие оптимизации ЦФ, основанное на выполнении критерия суммарной длины соединений,

• ЫКг>0 и ЫСА^-О - условие оптимизации ЦФ, основанное на одновременном соблюдении критериев длин критических связей и суммарной длины соединений,

• а, р - коэффициенты полезности вышеуказанных критериев, которые определяются на основании конструкторского опыта или экспертных оценок,

• Сотр! Кг (О) - комплексный критерий оценки качества размещения на основе длин критических связей, определяющийся формулой

Сотр1 _ Кг(О)=А(0) + 1 _Кг2(0)! А(С) (2)

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

Суммарная длина (весовая функция) рассчитывается по формуле «достроенной» критической связи

(3)

А(в) = 0,5 I ¿(х ,,х^хс(х„х,),

и, А х V

где

• сЦх^х^ - расстояние между вершинами Х( и Х) графа С.

отождествленными с узлами / иJ решетки,

• с(Х1, х ,) - число кратных ребер между этими вершинами

Выходная информация представляет собой список 5, 7 координат на КП для всех модулей

Требование оптимизации Сотр1(С/)—> тт. т е чтобы весовая функция была наименьшей для всевозможных способов отождествления вершин графа и узлов решетки

Пространство решений - множество всех целых чисел Ограничения

• 2<п<10000, где п - число вершин в графе (7,

• (¿(х^х^ = 0 , если X, = X ,

• ¿1(х1,х1) = с11Гест хг ФХ ,

• с(х1,х/)>0, элементы в силу геометрических ограничений не могут накладываться друг на друга

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

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

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

1 анализ графовой модели коммутационной схемы, полученной на этапе выполнения предыдущего шага конструкторского проектирования (решения задачи компоновки), с использованием модифицированного алгоритма Ant Colony (МААС),

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

3 реализация методов эволюционного моделирования в соответствие с выбранным критерием оценки качества размещения

3 1 реализация быстрого эволюционного поиска (использование оператора мутации),

3 2 выполнение генетического поиска (использование различных генетических операторов),

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

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

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

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

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

В третьей главе разработан интегрированный алгоритм, представленный на рис 1

С"

Г

X_____

Гегера^! я начального размещения

" Вычисление суммарной длины связей

.....:

I Задание !Ч_ОА Ыгтах, г=Ф1пах

|__ Ч,01" Со'-р^^гНЗ Соггр _

¿"¿"«•"■ер кт-ти 1еск |х связей?!

]

Кр^^ер м суммарной дл «нь ! _ соед <неш_й_ ]

Г ' °азмеи*ение влинеикч 1 _

I Генетический го 'ск I |

-Ж.,

Определение критических связей их длин N 1 1чг(С)

__ Крктср:^ останова доспгт "р"' __

"дГ

0 г

Щ'

Размещение в линейку модифицированный Л! Сшоп\'__|

Чр?ггсои'1

6 ) Ч ^

_____лж - - -

°азметен. еаг <мсГчу ^од.'дгаи^ова^ь й ОН _ _j

Ь

а.'фгипрова £? _Критери?! оспновл ло

с\ ммлияо 5 ли нь

-.-^¿ег.

Да

Сотой го! ч^О I Очергтоо м грации

Г

и --раак и_|

Фоом розаиие х-ОВОР ' оп\гя^» и

| Со'^о^Соггл 11 1

6

— о

'Л"

ч у

С

Сотр1 Конец

Рис 1 Структурная схема интегрированного алгоритма размещения фрагментов

БИС

Он основан на использовании методов эволюционного моделирования модифицированного алгоритма Ant Colony (МААС), усовершенствованного бионического поиска для решения задачи размещения фрагментов БИС Здесь

• N G 4 - число итераций генетического алгоритма размещения фрагментов БИС,

• Nmax - число итераций интегрированного алгоритма,

• t - текущая итерация интегрированного алгоритма,

• N от- число итераций эволюционного алгоритма размещения,

• Compl - значение комплексного критерия оценки качества размещения,

• N _Кг - число критических связей,

• L Kr(G) - длина критических связей в графовой модели схемы

Модификация алгоритма Ant Colony (АС) используется как блок анализа перед моделированием модифицированного бионического поиска Далее выполняется коррекция размещения на основе выбранных критериев оценки качества двумерного размещения суммарной длины соединений и длин критических связей в графовой модели коммутационной схемы Коррекция заключается в выделении и размещении «строительных блоков» и и/или фрагментов БИС, не входящих в сформированные строительные блоки (СБ)

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

Разработаны и описаны эвристики сжатия коммутационных схем большой размерности на основе выделения СБ

Эвристика 1 эффективна при небольшом числе (п<1000) вершин графовой модели КС и заключается в том, что

• вершины, соединенные ребрами с меньшей длиной, в линейке располагаются на максимальном расстоянии,

• вершины, соединенные ребрами с максимальными весами объединяются в блоки и не модифицируются генетическими операторами

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

Эвристика 1 позволяет повысить быстродействие предложенного автором интегрированного алгоритма и при количестве вершин графа п- 1000 При этом первые ii'<</7 (11'=/, 2, , п) вершин графа группируются в строительные блоки, фиксируются в линейке на основе эвристики 1 Остальные (п м) вершин графа размещаются на основе эволюционной части модифицированного бионического алгоритма Отметим, что величину ir задает экспертная подсистема размещения

Эвристика 2 выполняется, если количество вершин больше 1000, и состоит в следующем

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

• каждый строительный блок представляет собой «вертикальную» линейку,

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

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

Предложенная структура параллельного интегрированного алгоритма (ИА) показана на рис 2

С Начало

. _ _Г____

С

Ззод начальных данных

*■ Эво; юиио^ый алгооити Размешен е СБ

Критерии оа 1нои юстигн^ .

6 ~~~.iit.~~ Зь оор

1". : ~ Эзолюцг'он-'ь " aJ гое «-л '

пазмеи.ение С5 |

Да"

-Г

Сжатие

~~т '

г

'ене-имеский алгоритм I

___~т г

°ачке^ение СБ

- -с.5 КЛутсрш! ос-анова достигни;^

____

| Зь'бор |

- -

I Очеоатоо ми оациа

'- - "Т—

о » _ _ .

, з

_ "Л_________

С жат^е |

И-^-егр^ровачный поиск |

Размещение СБ

I

е«ет.меекии а^оэ/Пм

" к ______

Размещение СБ .р Зазерше" 'е рабо~ь*9 _

Окончательное размещение

"Л---ШИТ"

.^.КрИТСрИ! ОС" IHOBd достигн\?П^~

ИГ______

5ьбор к-

1. __ , с'и-е р рова-шы? поиск \

- 1

^азме^ечле С5

' $аэе и екле ^гбо^ъ^Ц.-" [Да

___шрагме^в эЛС _ J

СГ Кс^ед .

Рис 2 Структура параллельного интегрированного алгоритма Выработан механизм обмена данными в структурах параллельного и последовательно-параллельного алгоритмов При этом для каждого

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

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

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

Графический интерфейс пользователя программного комплекса Шп4Р]асетепЪ> представлен на рис, 3.

подсчетека

<'■<■<: ■ иий —---

результатов _ ^ ^ ..........._ ....... /J' " !

Рис. 3. Графический интерфейс пользователя программного комплекса

«1л 4 Placement»

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

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

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

Таблица (фрагмент) Сравнительный аналиг эффективности размещения при йстояьзоа&щи различных алгоритмов

ЛГ. | Кол-во ДА ГП1А ПА 1 11тА ГА

п п I г№еращгй| ЦФ ( ЦФ 1 ЦФ * ЦФ t ЦФ Г

Число фра'тактов ЗКС - ЗзО, критерии критически гвя; ек и с уммзрной

длины соединений

1 ю 1725 25 1720 27 1720 36 . 1720 32 1720 26

20 1700 26 1700 27 1680 38 1701 35 1705 28

30 1652 28 1620 28 1655 45 1675 38 1675 36

! 40 1658 25 1600 29 1652 46 1620 42 1654 38

, 50 1620 32 1580 30 1600 62 1622 45 1625 41

" 1 60 1532 35 1579 31 1595 64 159? 49 1602 45

70 1580 38 1577 33 1554 68 1500 52 1597 47

80 1577 38 1575 35 153$ 65 . 1585 57 1582 49

90 1577 41 1575 35 1587 75 1582 59 1580 49

:оо 1575 ¿2 1575 36 1582 75 . 1580 60 1575 50

Столбцы приведенного фрагмента таблицы описывают: первый - номер эксперимента (тестовой задачи), второй - число генераций алгоритмов, значения ЦФ рассматриваемых тестовых задач и времени моделирования ИА, параллельного интегрированного алгоритма (ПИА), последовательного алгоритма (Г1А), итерационного алгоритма (ИтЛ) и генетического алгоритма (ГА) далее парами соответствен но.

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

квазиоптимальных решений, является гибкой, обладает высоким быстродействием (15%-30%) на одних и тех же входных данных ВСА-

Все это говорит об эффективности рассматриваемого метода по сравнению с существующими аналогами

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

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

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

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

результаты

результатов

архитектура

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

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

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

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

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

операторы,

выполнения

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

1 Балюк Л В Исследование влияния генетических алгоритмов на точность модели» Известия ТРТУ Тематический выпуск «Интеллектуальные САПР» Материалы Международной научно-технической конференции «Интеллектуальные САПР» Таганрог Изд-во ТРТУ, 2003, Ж2(31) - 329 с

2 Балюк Л В , Курейчик В В Вероятностный генетический алгоритм Ant Colony и его приложение для решения задач (на примере задачи о коммивояжере) Труды Международных научно-технических конференций «Интеллектуальные системы» (IEEE AIS'04) и «Интеллектуальные САПР (CAD-2004)» - VI Изд-во Фихматлит, 2004, т i Тираж 250 экз с 53-65

3 Балюк Л В , Курейчик В В Исследование возможностей, предоставляемых вероятностными генетическими алгоритмами, для решения комбинаторных задач Труды VII Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» - Таганрог Изд-во ТРТУ, 2004 Тираж 700 экз с 89 90

4 Балюк Л В Исследование возможностей, предоставляемых вероятностным генетическим алгоритмом Ant Colony, для решения задачи о коммивояжере Труды II Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» - Таганрог Изд-во ТРТУ, 2004 Тираж 80 экз с 74-76

5 Балюк Л В Исследование влияния бивариантных генетических алгоритмов на точность определения модели Известия ТРТУ Тематический выпуск "Интеллектуальные САПР" Материалы международной научно-технической конференции "Интеллектуальные САПР" Таганрог Изд-во ТРТУ, 2005 .N'23(47) с 220-221

6 Балюк Л В Исс 1едование возможностей оптимизации комбинированных алгоритмов решения задачи размещения Ш Всероссийская научная конференция мотодых ученых и аспирантов «Информационные технологии системный анализ и управление» Таганрог Изд-во ТРТУ 2005 с 113-116

7 Балюк Л В Исследование влияния бивариантных генетических алгоритмов на точность построения моделей Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS'05) и «Интеллектуальные САПР» (CAD-2005) Научное издание в 3-х томах - М Изд-во Физико-математической литературы, 2005, Т I с 20 - 22

8 Балюк Л В Сравнительный анализ возможностей вероятностного генетического алгоритма Ant Colony с алгоритмами полного перебора с симметричной матрицами для решения задачи о коммивояжере Материалы

первой ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН

9 Балюк Л В Возможности комбинированных стратегий решения задачи размещения разногабаритных элементов СБИС Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS'06) и «Интеллектуальные САПР» (CAD-2006) Научное издание в 3-х томах - М Изд-во Физико-математической литературы, 2006, Т 1 с 552-557

10 Балюк Л В Генетические алгоритмы решения задачи размещения элементов СБИС Известия ТРТУ Тематический выпуск "Интеллектуальные САПР" Таганрог Изд-во ТРТУ, 2006 №8(63) -с 66-72

В работах [2, 3], опубликованных в соавторстве, лично автору принадлежат следующие результаты - модификация вероятностного генетического алгоритма Ant Colony для решения задачи размещения фрагментов БИС с установленным критерием минимизации взвешенной длины соединений графового эквивалента электрической схемы Изначально данный подход был разработан' для решения задачи коммивояжера На основе проведенных исследований были усовершенствованы значения входных параметров данного | алгоритма, позволившие получить эффективное решение поставленной задачи за минимальное, по сравнению с существующими аналогами время

Соискатель

Л В Балюк

Тип ТТИ ЮФУ Заказ № тир экз

ВВЕДЕНИЕ

1. АНАЛИЗ ПРОБЛЕМ И ПЕРСПЕКТИВ МЕТОДОВ РАЗМЕЩЕНИЯ

1.1. Анализ проблемы размещения фрагментов БИС

1.2. Постановка задачи размещения фрагментов БИС

1.3. Классификация и анализ методов размещения фрагментов БИС

1.4. Выводы

2. РАЗРАБОТКА ИНТЕГРИРОВАННЫХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ РАЗМЕЩЕНИЯ

2.1. Стратегия и принципы решения задачи размещения

2.2. Архитектура интегрированного поиска

2.3. Разработка генетических и эволюционных стратегий размещения фрагментов БИС

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

2.5. Выводы

3. ПОСТРОЕНИЕ ИНТЕГРИРОВАННОГО АЛГОРИТМА РАЗМЕЩЕНИЯ ФРАГМЕНТОВ БИС

3.1. Интегрированный алгоритм па основе методов эволюционного моделирования

3.2. Разработка модифицированного алгоритма Ant Colony

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

3.4. Разработка параллельного алгоритма размещения фрагментов БИС

3.5. Выводы

4. ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ И АНАЛИЗ РАЗРАБОТАННЫХ АЛГОРИТМОВ РАЗМЕЩЕНИЯ

4.1. Цель и основные задачи построения программного комплекса решения задач размещения фрагментов БИС

4.2. Описание программной реализации интегрированного алгоритма размещения фрагментов БИС

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

4.4. Выводы

Технологии интеграции сверхвысокого уровня (Very Large Scale Integration - VLSI), Standart Cells, Mask-Programmed Gate Arrays (MPGAs) явились основой повсеместного применения практически неограниченных возможностей цифровых интегральных схем (ИС) за минимальную плату. Каждая из этих тепологий, тем пе менее, предполагает огромные капиталовложения в производство, а также временные затраты па весь процесс проектирования.

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

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

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

За последние годы важным стало освоение рынка электронных технологий в минимально короткие сроки, а также прогнозирование возможного финансового риска, закладываемого в процесс производства нового изделия. Перепрограммируемые вентильные матрицы (Field

Programmable Gate Arrays - FPGA) - стали эффективным решением проблем, связанных с прогнозированием риска и временными показателями освоения рынка электронных технологий.

Технология создания FPGA обеспечила возможность «реального» производства гибких схем (прототипов) за минимальную стоимость: время выпуска 1 прототипа занимает несколько минут, а его стоиомсть составляет около 100 долларов. Ренрограммируемое устройство - это гибкая схема, логическая структура которой может быть скорректирована (задана и изменена) конечным пользователем без использования интегрированной схемы (статичной), собранной выпускающей компанией [9J.

Важнейшим этапом в цикле проектирования FPGA, является этап конструкторского проектирования, на котором решаются задачи разбиения (компоновки), планирования, размещения, трассировки (разводки), упаковки, верификации [5J.

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

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

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

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

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

• Построение архитектуры интегрированного алгоритма размещения фрагментов БИС, основанного на методах эволюционного моделирования.

• Разработка интегрированного подхода и алгоритмов размещения.

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

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

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

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

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

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

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

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

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

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

2. Модифицированную архитектуру алгоритма Ant Colony для решения задачи размещения фрагментов БИС.

3. Усовершенствованные операторы размещения, обеспечивающие уменьшение времени поиска.

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

Разработанный программный комплекс решения задач размещения фрагментов БИС реализован с использованием визуальной среды программирования Borland С-н- Builder 6.0, СИ иод WINDOWS.

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

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

Реализация результатов работы. Материалы диссертации использованы в госбюджетных научно-исследовательских работах Таганрогского государственного радиотехнического университета (ТРТУ), по гранту Министерства образования и науки РФ, а также научно-исследовательских работах, выполненных по грантам Российского фонда фундаментальных исследований (НИР № 12354, 12362). Результаты этих работ внедрены и используются в учебном процессе на кафедре САПР ТТИ ЮФУ (г. Таганрог). Акты о внедрении и использовании результатов работы приведены в приложении к диссертации.

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

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех разделов, заключения, изложенных па 157 страницах, 51 рисунка, 4 таблиц, списка литературы из наименований и приложения.

4.4. Выводы

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

2. Управление процессом интегрированного поиска при размещении фрагментов БИС позволило определить эффективные значения входных параметров для реализации разработанных алгоритмов.

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

4. Разработан и реализован модифицированный алгоритм Ant Colony, позволяющий част ично решить проблему предварительной сходимости и существенно увеличить быстродействие интегрированного алгоритма размещения фрагментов БИС.

5. Разработана параллельная стратегия интегрированного поиска на основе модифицированного алгоритма Ant Colony и бионического поиска, обеспечивающая распараллеливание вычислений. ВСА является полиномиальной.

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

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

8. Выполнены тестирование и обработка экспериментальных данных, что позволило улучшить качество размещения па 29%, время решения от 10% до 30%.

1. Schallcr Robert R. MOORE IS LAW: past, present, and future. IEEE SPECTRUM JUNE, 1997, pp. 53 59.

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

3. Сороколстов Г1.В. Коммутационные модели блоков ЭВА. Перспективные информационные технологии интеллектуальные системы, №2 (18), 2004, с.46-53.

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

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

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

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

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

9. Stephen D. Brown. Field-Programmable Gate Arrays. Kluwer Academic Publishers, 1992,-210 p.

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

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

12. Cong J., Sung Kyu Lim. Multiway Partitioning with Pairwise Movement // UCLA Department of Computer Science, Los Angeles, CA. 1996.

13. Sanchis L.A. Multiple-way network partitioning // IEEE Trans, on Computers. 1989.

14. Shahookar K., Ma/.umdcr P. VLSI Cell Placement Techniques. // Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Michigan 48109. «ЛСМ Computing Surveys», Vol. 23, No. 2, June 1991.

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

16. Норенков И.П., Кузьмик U.K. Информационная поддержка наукоемких изделий. CALS-тсхнологпп. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002.

17. Колчип А.Ф. и др. Управление жизненным циклом продукции. М.: Апархасис, 2002.

18. Евгеньев Г.Б. и др. CASE- технология создания мпогоагентных САПР изделий машиностроения. ШЕЕ A1S-03, CAD-2003. Интеллектуальные системы, интеллектуальные ("ДПР т.2. М.: Физматлит, 2003, с 41 -46.

19. Грувер М., Зимерс Э. САПР и автоматизация производства. М.: Мир, 1987.

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

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

22. Норенков И.П. основы автоматизированного проектирования. Учебник для вузов. 3-е изд., перераб. и доп. М.: Изд-во МГТУ им. Баумана, 2006.-448 с.

23. Гридип В.II. Теоретические основы построения базовых адаптируемых компонентов САПР МЭА. М.: Паука, 1989.

24. Karypis G., Aggarwal R., Kumar V., and Shekhar S. Multilevel hypcrgraph partitioning: Application in VLSI domain. In Proceedings of the Design and Automation Conference, 1997.

25. Малышев П.Г., Мицук 1I.B. Основы оптимального управления процессами автоматизированного проектирования. М.: Энергоатомиздат, 1990.

26. Kureichik V.V., Kurcichik V.M., Genetic Algorithms. I1G Verlag, Konstans, 2004.

27. Бершадский A.M. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. Саратов: Изд-во СГУ, 1993.

28. Петухов Г.А., Смолим Г.Г., Юлии Б.И. Алгоритмические методы конструкторского проектирования узлов с печатным монтажом. М.: Радио и связь, 1987.

29. Никифоров A.M. Выбор критериев размещения. Известия ТРТУ № 3, 1999. стр. 300-301.

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

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

32. Гладков J1.A., Курейчпк В.В., Курейчик В.М. Основы теории алгоритмов / под ред. В.М. Курсйчика. Учебное пособие по курсу «Математическая логика и теория алгоритмов». Таганрог. ТРТУ, 2002.82 с.

33. Базилевич Р.11. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. Львов: Вища шк., 1981.

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

35. J. Хи, Р. N. Guo, and С. К. Cheng, "Rectilinear block placement using sequence-pair," in Proc. 1998 ACM/1FFF Int. Syrnp. on Physical Design, Monterey, С A, Apr. 6-8, 1998, pp. 173-178.

36. Ойхман Е.Г. Графические системы для СМ ЭВМ. М.: Паука, 1986

37. Sherwani Navccd. Algorithms for VI,SI Physical Design Automation, Kluwer Academic Publishers, Boston/Dordrecht/London, 1995.

38. Physical Design Automation of VLSI Systems. Itdiled by T. Preas and M. Lorenzetti. BCPC, Inc. USA: Menlo Park, 1988.

39. Чичварии II.B. Экспертные компоненты САПР. М.: Машиностроение, 1991.

40. Морозов К.К., Одиноко в В.Г., Курейчик В.М. Автоматизированное проектирование конструкций РЭА. М.: Радио и связь,1983.

41. Никифоров A.M. Оценка качества размещения. // Известия ТРТУ № 3,1999. стр. 206-209.

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

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

44. Современная прикладная теория управления: Оптимизационный подход в теории управления /' под ред. А.А. Колесникова. Таганрог: Изд-во ТРТУ, 2000.4.1.

45. Современная прикладная теория управления: Сипсргетический подход в теории управления / под ред. А.А. Колесникова. Таганрог: Изд-во ТРТУ, 2000.4.2.

46. Современная прикладная теория управления: Новые классы регуляторов технических систем / под ред. А.А. Колесникова. Таганрог: Изд-во ТРТУ, 2000.4.3.

47. Садовничий В.А. и др. Устойчивость глобального развития и хаотичность региональных явлений в нелинейных динамических процессах. Синергетика// Груды семинара. Том 3. М.: Изд-во МГУ,2000, с.5-39.

48. Пригожип И., Стсигсре И. Время, хаос, квант. К решению парадокса времени. М.: Эдиториал УРСС, 2000.

49. Моисеев Н.Н. Современный рационализм. М.: MI В11 Кокс, 1995.

50. Лоскутов А.Ю., Михайлов А.С. Введение в синергетику. М.: Паука, 1990.

51. Пригожин И. От существующего к возникающему. М.: Паука, 1985.

52. Eisemann II. and Johannes P.M. Gcncric global placement and door planning. // in Proc IRE/ACM Int Conf CAD 1998. pp. 269-274.

53. Батищев Д.П., Львович Я.И., Фролов В.II. Оптимизация в САПР. -Воронеж: Изд-во ИГУ, 1997.

54. Курицкий Б.Я. Оптимизация вокруг пас. JI.: Машиностроение, 1989.

55. Алексеев О.В. и др. Автоматизация проектирования радиоэлектронных средств. М.: Высшая школа, 2000.

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

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

58. Caldwell А.Е., Kahng А.В. and Markov I. Г. Optimal Portitioncrs and End •Case Placers for Standard Cell Layout. -//-V.19, №11, November 2000, pp. 1304- 1313.

59. Handbook of Genetic Algorithms. Edited by Lawrence Davis. USA: Van Nostrand Reinhold, New York, 1991.

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

61. Курсйчик В.М. Совместные методы квантового и бионического поиска. Труды конференций IEEE AIS'04, CAD-2004, М.: Физматлит, 2004. с. 1219.

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

63. Курсйчик В.М. Гепстичсскис алгоритмы. Обзор и состояние. Новости искусственного интеллекта, №3, 1998, с. 14-64.

64. Mazumder P., М. Rudnic. Genetic Algorithms For VLSI Design, Layout & Test Automation. PL, Inc. Singapore, 1999.

65. Курейчик В.М. Генетические алгоритмы: Состояние. Проблемы. Перспективы. Теория и системы управления РАН, Москва, N 1, 1999, с.144-160.

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

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

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

69. Гладков JI.A., Курсйчик В.В., Курейчик В.М. Генетические алгоритмы. / под ред. В.М. Курейчика. Учебное пособие. Ростов на Дону: Ростиздат, 2004.

70. De Jong К. Evolutionary Computation: Recent Development and Open Issues. Proceedings 1st International conf, Evolutionary Computation and Its Application, EvCA 96, Moscow, 1996, pp.7 18.

71. Mak 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

72. Эволюционная эпистемология и логика социальных паук: Карл Поппср и его критики// Составление Д.Г. Лахути, В.II. Садовского, В.К. Финна. -М.: Эдиториал УРСС, 2000.

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

74. Курейчик В.В., Курейчик В.М. Об управлении на основе генетического поиска. Автоматика и телемеханика. PAII, №10, Москва, 2001, с. 174187.

75. Тарасов В.Б. Интеллектуальные системы в проектировании. Новости ИИ, №4, 1993, с.24-67.

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

77. Мищенко М. II. Бионический метод размещения элементов схем ЭВА. Перспективные информационные технологии интеллектуальные системы, №2 (22), 2005, с. 34.36.

78. Colorni A., Dorigo М., Maniezzo V., "Distributed Optimization by Ant Colonics," Proceedings of the First Huropcan Conference on Artificial Life, Paris, France, F.Varela and P.Bourginc (lids.), Hlsevicr Publishing, 134 142, 1991.

79. Colorni A., Dorigo M., Maniezzo V., "The Ant System: Optimization by a colony of cooperating agents," Tcch.Rep.IRIDIA/94-28, Universitc Libre dc Bruxelles, Belgium, 1996.

80. Балюк JI.B. Сравнительный анализ возможностей вероятностного генетического алгоритма Ant Colony с алгоритмами полного перебора с симметричной матрицами для решения задачи о коммивояжере.

81. Материалы нерпой ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН. Ростов-на-Дону: Изд-во ЮНЦ РАИ, 2005. с. 195-197.

82. Балюк J1.B. Генетические алгоритмы решения задачи размещения элементов СБИС. Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 2006. №8(63). с. 66-72.

83. Langton С. (Ed.) Artificial Life. New York: Addison Wesley, 1998.

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

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

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

87. Комарцова Л.Г., Максимов А.В. Нейрокомпьютеры. М.: Изд-во МГТУ, 2002.

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

89. Васильев В.И., Ильясов Б.Г. Интеллектуальные системы управления с использованием генетических алгоритмов// Приложение к журналу Информационные технологии, №12, 2000.

90. Скурихип A.II. Генетические алгоритмы// Новости искусственного интеллекта, М., №4, 1995. с.6-46.

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

92. Андерсон Д. Дискретная математика и комбинаторика. М.: Вильяме, 2003.

93. Breuer М. Min cut placement. J. Des. Autom. and Fault Tolerant Comput., 1997. V. 1. pp. 343-362.

94. Kling R.M. and Banerjee P. Empirical and Theoretical Studies of the Simulated Evolution Method applied to standard Cell Placement. IEEE Trans, on CAD, Vol.10, No. 10, 1991. pp. 1303-1315.

95. Potts C.I., Giddens T.D., Yadav S.B. The Development and Evaluation of an Improved Genetic Algorithm Based on Migration and Artificial selection. IEEE Trans, on Systems, Man and Cybernetics, vol.24, No.l, 1994. pp. 73 -86.

96. Shahookar K., Ma/.munder P. A Genetic Approach to standard Cell Placement Using Meta-Genetic Parameter Optimization. IEEE Trans, on CAD, Vol.9, No.5, 1990. pp. 500 511.

97. Cohoon J.P., Paris W.D. Genetic Placement, IliEH Trans, on CAD, Vol.6, No 6, November, 1987. pp. 956 964.

98. Курейчик В.М. Курсйчик В.В. Генетический алгоритм размещения графа// Известия АН. Теория и системы управления, № 5, 2000, с.67-74.

99. Kureichik V.M, Kureichik V.V. Genetic Algorithm for Graph Placement Journal of Computer and Systems Sciences International, vol.39, №5, 2000, pp.733-740.

100. Попов Э. В. и др. Статические и динамические экспертные системы. -М.: Финансы и статистика, 1996.

101. Ведерникова О.Г. Разработка и исследование комбинированного генетического алгоритма генетического поиска и имитации отжига для задачи размещения элементов СЬИС: Дне. к.т.н. Ростов и/Д РГЛ сельхозмашиностроения, 1999.

102. Курейчик В.В. Программная подсистема но исследованию оптимизационных задач па графах. Программные продукты и системы. №1,2002. с.26-28.

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