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

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

ЛЕЖЕБОКОВ Андрей Анатольевич

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

Специальность: 05.13.12 - системы автоматизации проектирования (вычислительная техника и информатика)

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

Таганрог - 2008

003453789

003453789

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

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

Гладков Леонид Анатольевич

Официальные оппоненты: доктор технических наук, профессор

Чернышев Юрий Олегович (Государственная академия сельскохозяйственного машиностроения, г.Ростов-на-Дону)

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

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

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

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

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

- Автореферат разослан « 06 » ноября 2008 г.

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

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

Целых А.Н.

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

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

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

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

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

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

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

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

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

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

Методы исследования. Выполненная работа характеризуется

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

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

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

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

2. Разработана новая методика построения модели цепи, на основе дерева Штейнера, для оценки временной задержки, возникающей на межсоединениях цепи схемы.

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

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

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

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

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

1. Модифицированная архитектура генетического поиска, учитывающая ограничения на временные характеристики проектируемого устройства.

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

3. Усовершенствованные проблемно-ориентированные операторы генетического поиска.

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

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

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

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

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

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

Структура н объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы. Работа содержит 131 страницу, включая 31 рисунок, 10 таблиц, список литературы из 110 наименований, 3 страниц приложений с актами об использовании результатов работы.

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

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

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

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

Решаемая в диссертационной работе дискретная задача размещения

может быть сформулирована следующим образом. На прямоугольную конструкцию накладывается Декартова система координат с осями 5 и определяющая граф Сг, задающий собой координатную решетку. Задача размещения сводится к отображению заданного гиперграфа-модели Н=(Х, и) схемы в решетку Сг таким образом, чтобы множество вершин X = {х,},

/ = 1 гиперграфа Я размещалось в узлах решетки, число которых конечно.

Целевая функция может быть выражена следующим выражением:

I

Г(Р) = ^ , где В] - оценка задержки цепи у

7=1

Задача оптимизации заключается в минимизации значения целевой функции: Р(Р)—+т 'т.

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

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

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

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

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

Вход

Рис 1 Модифицированная архитектура генетического поиска

В разработанной модифицированной архитектуре генетического поиска добавлены блоки эволюционной адаптации (Блок №5) и блок анализа неперспективных решений (Блок № 7). Блок эволюционной адаптации предназначен для выбора и реализации различных стратегий и механизмов адаптации. Также в этом блоке на основе обратных связей производится выбор используемой модели эволюции. Еще одно предназначение данного блока состоит в настройке и изменении порядка использования и применения различных генетических операторов и схем поиска. Результаты работы блока эволюционной адаптации оказывают непосредственное влияние на процесс перестройки текущей популяции альтернативных решений и создания на ее основе новой популяции.

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

Разработана новая методика построения модели цепи, на основе дерева Штейнера, для оценки временной задержки, возникающей на межсоединениях

цепи схемы.

Для построения модели цепи в указанной метрике предлагается использовать пошаговую процедуру. Рассмотрим её на примере:

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

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

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

4. Через эту точку проводится «столб», для построения дерева Штейнера.

5. Каждый элемент цепи связывается со «столбом Штейнера».

Имеем модель цепи на основе дерева Штейнера в Манхэттенской

метрике (рис. 2).

Координаты центроида:

хе-ауд(вигп(х1))

Уо - ауд(8шп(У|)) ___ _

О ч цент / гаид ВД<р.Ур>

у у С(Хо.у=)Ч\ ~о

01 У О ад

Ц.1ЗДЛ

О

"Ли

о

о.

щ>

ЦрСр-Уи)

О

-У»)

Рис. 2 Пример построения модели цепи на основе дерева Штейнера

Временная задержка вычисляется в два этапа:

- задержка начального сопротивления заряда цепи нагрузки и всех контактов этой цепи;

02(и„п!) = гс*11+г*1,1Ся

)

- внутренняя задержка пути от ш до и<3 за счет внутренней емкости и внутреннего сопротивления. Вычисляется для каждой пары элементов цепи;

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

Проведен анализ разработанной модели и сделан вывод о том, что представленная модель является более точной по сравнению с известной моделью

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

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

• схема

• количество элементов схемы;

• матрица инцидентности;

• размеры дискретного рабочего поля (ДРП), на котором осуществляется размещение;

• ограничения на временные характеристики схемы

Параметры генетического алгоритма это:

• виды и вероятности генетических операторов;

• количество скрещиваний в одном поколении и количество поколений;

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

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

• сопротивление проводника на единицу длины;

• ёмкость загрузки контакта на единицу длины;

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

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

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

Рис. 3 Архитектура проблемно-ориентированного генетического алгоритма

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

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

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

• уровень миграции, который определяет, сколько элементов мигрирует в генерацию;

• расписание миграций, которое определяет порядок миграции;

• топология связи между подпопуляциями.

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

Рис. 4 Архитектура многопопуляционного параллельного генетического

алгоритма

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

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

Круговая модель

Модель «2-х кланов«

Модель выделенного источника

Полная модель

Рис.5 Модификации модели островов

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

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

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

Родитель 1 4 3 2 8 6 9 5 7

Потомок 1 4 3 2 8 9 б 5 7

1 4 3

2 8 6

9 5 7

Рис б Пример работы ОМ I

1 8 5 ! 3 6 4 i 9 2 7

I I

1 8 5 ¡4 6 3 j 9 2 7

1 8 5

3 6 4

9 2 7

1 4 3

2 8 9

6 5 7

1 8 5

4 6 3

9 2 7

Рис. 7 Пример работы ОИ

Модифицированные проблемно-ориентированные операторы

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

В четвертой главе определены теоретические оценки временной сложности разработанных алгоритмов. Экспериментальные исследования проводились на 10 тестовых схемах. Первая из них имеет 12506 элементов, последняя - 68685 элемент. Тестирование и экспериментальные исследования проводились с помощью специализированного программного обеспечения (ПО), разработанного на объектно-ориентированном языке программирования С++ в среде Builder 6.0. Для тестирования использовалась операционная система Microsoft Windows ХР Professional™ Service Pack 2. Отладка и тестирование проводилось на ЭВМ типа IBM PC с процессором Pentium-IV с ОЗУ-512М6.

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

—♦—Последовательный —Итерационный

—а—Модифицированный ГА ■ » - Параллельный ГА

Рис 8 Временная сложность алгоритмов

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

□ Последовательный ■ Итерационный

□ Модифицированный ГА □ Параллельный ГА

100 250 500 750 1000

Рис. 9 Эффективность алгоритмов

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

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

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

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

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

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

2. Приведена постановка задачи размещения компонентов СБИС с учетом временных задержек. Предложен новый критерий - сумма оценок временных задержек.

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

4. Разработана новая методика построения модели цепи на основе дерева

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

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

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

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

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

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

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

2. Гладков JI.A., Лежебоков A.A. АРМ преподавателя с интеллектуальной поддержкой. // «Программные продукты и системы», № 4, 2005. - с. 58 - 60.

3. Лежебоков A.A. Решение задачи размещения элементов СБИС с учетом временных задержек. // Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 2006. №8(63).-с. 146151.

4. Лежебоков A.A. Новый подход к решению задачи размещения элементов СБИС с учетом временных задержек.//УШ всероссийская научная конференция студентов и аспирантов «Техническая кибернетика,

радиоэлектроника и системы управления». - Таганрог: Изд-во ТРТУ, 2006.-е.

5. Лежебоков A.A., Гладков Л.А. Моделирование временных задержек при решении задачи размещения элементов СБИС. // Известия ТРТУ, №1(73), 2007. - Таганрог: Изд-во ТРТУ, 2007. - с. 75-77.

6. Лежебоков A.A. Кодирование решения для генетического алгоритма решения задачи размещения. // Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS'07) и «Интеллектуальные САПР» (CAD-2007). Научное издание в 4-х томах, т.1. - М.: Физматлит, 2007. -с. 66-71.

7. Лежебоков A.A. Программная реализация алгоритма решения задачи размещения с учетом временных задержек. // Известия ЮФУ. Технические науки Тематический выпуск "Интеллектуальные САПР", №2(77), 2007. -Таганрог: Изд-во ТТИ ЮФУ, 2007. - с. 65-70.

8. Лежебоков A.A. Генетический алгоритм решения задачи размещения элементов СБИС с учетом временных задержек. // Сборник научных трудов международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте», т.1. - , М.: Физматлит, 2007. - с. 429-436.

9. Лежебоков A.A. Программная реализация решения задачи размещения. // Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS'08) и «Интеллектуальные САПР» (CAD-2008). Научное издание в 4-х томах, т.1. - М.: Физматлит, 2008. - с. 55-63.

10. Лежебоков A.A., Гладков Л.А. Результаты компьютерного моделирования решения задачи размещения элементов СБИС с учетом временных задержек. III Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлекгронных систем-2008», - Сборник научных трудов/ под общ. ред. АЛ.Стемпковского-М.: ИППМ РАН, 2008. с. 130-136.

Личный вклад автора в работах, опубликованных в соавторстве: [2] -разработка эффективной структуры данных для хранения больших объемов информации; [5] - анализ различных моделей для оценки временной задержки цепи; [10] - программная реализация разработанного параллельного генетического алгоритма размещения компонентов СБИС с учетом временных задержек.

90-91.

Соискатель

Содержание.

ВВЕДЕНИЕ.

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

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

1.1. Анализ проблемы размещения.

1.2. Анализ математических моделей схем для задачи размещения.

1.3. Классификация критериев задачи размещения.

1.4. Постановка задачи размещения с учетом временных задержек.

1.5. Классификация и анализ методов размещения.

1.6. Выводы.

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

2.1. Определения и понятия эволюционного моделирования.

2.2. Разработка архитектуры генетического поиска.

2.3. Оценка задержки на основе модели Эльмора.

2.4. Построение модели цепи на основе дерева Штейнера для оценки временной задержки.

2.5. Выводы.

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

3.1. Последовательный алгоритм размещения.

3.2. Алгоритм «слепого» поиска.

3.3. Разработка проблемно-ориентированного генетического алгоритма.

3.4. Разработка многопопуляционного параллельного генетического алгоритма.

3.5. Разработка усовершенствованных генетических процедур и операторов.

3.6. Построение архитектуры композитного поиска.

3.7. Выводы.

4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ

РАЗРАБОТАННЫХ АЛГОРИТМОВ.

4.1. Теоретическая оценка временной сложности.

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

4.3. Описание программно-алгоритмического комплекса.

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

4.5. Выводы.

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

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

Разработка методов и алгоритмов для решения задачи размещения осуществляется на протяжении многих лет, но по-прежнему является актуальной. Это связано, в первую очередь, с тем, что эта задача является NP-полной, и разработать универсальный алгоритм, позволяющий находить точное оптимальное решение за приемлемое время затруднительно. Появление новых более совершенных средств вычислительной техники, дающих мощные вычислительные ресурсы, а также повышенные требования к проектируемым устройствам, все это является побудительной причиной разработки новых алгоритмов решения задачи размещения. Существует несколько подходов к решению NP - полных задач [4,5].

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

Недостатки алгоритмов первого класса очевидны. Недостатки эвристических алгоритмов решения задачи размещения сводятся, в общем, к низкому качеству решения, либо затрачивают на его поиск избыточное количество времени [4-25]. Алгоритмы случайно-направленного поиска обладают способностью находить более высококачественные решения за приемлемое время.

Одним из методов случайно-направленного поиска является метод генетического поиска. В 1975 году американский исследователь Дж. Холланд описал методологию изучения адаптивных систем и их применения для искусственных систем, а также разработал подходы к решению комбинаторно-оптимизационных задач. Сейчас генетические алгоритмы (ГА) хорошо известная и эффективная технология оптимизации, применяемая для различных задач техники, моделирующая естественный процесс эволюции в качестве средства достижения оптимума и основанная на имитации процессов натуральной селекции и генетических преобразований [26].

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

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

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

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

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

2. Разработка модели цепи, на основе дерева Штейнера, для оценки временной задержки межсоединений; разработка процедуры для расчета значения целевой функции.

3. Разработка и исследование нового проблемно-ориентированного генетического алгоритма для решения задачи размещения компонентов СБИС.

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

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

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

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

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

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

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

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

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

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

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

1. Модифицированную архитектуру генетического поиска, учитывающую ограничения на временные характеристики проектируемого устройства.

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

3. Программно-алгоритмический комплекс, предназначенный для решения задачи размещения компонентов СБИС.

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

При построении программы генетического поиска использовались пакеты программ С++ Builder, Visual С++. Отладка и тестирование проводилось на ЭВМ типа IBM PC с процессором Pentium-IV с ОЗУ-1024Мб. Проведенные вычислительные эксперименты, показали преимущество разработанных алгоритмов, по сравнению с известными алгоритмами, в качестве решения задачи размещения компонентов СБИС. Разработанные алгоритмы размещения позволяют получать набор квазиоптимальных альтернативных решений за полиномиальное время.

Реализация результатов работы. Основные результаты диссертационной работы использованы в госбюджетных и хоздоговорных работах, проводимых в Таганрогском технологическом институте Южного федерального университета: госбюджетная работа по заказу Минобразования РФ №12354 (1.04.01) «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», №12361 (РНП.2.1.2.3193) «Разработка интеллектуальных систем проектирования для решения задач разбиения СБИС на основе эволюционных методов», №12362 (РНП.2.1.2.2238) «Разработка бионических методов и принципов поиска оптимальных решений при проектировании».

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

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

Публикации. Результаты диссертации отражены в 10 печатных работах, в числе которых 3 - в изданиях, рекомендованных ВАК.

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 147 страниц, а также 31 рисунок, 10 таблиц, список литературы из 110 наименований, 16 страниц приложений, в числе которых акты об использовании результатов диссертационной работы и листинг программно-алгоритмического комплекса.

4.5. ВЫВ ОДЫ

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

2. Проведены экспериментальные исследования разработанных алгоритмов на тестовых примерах. Определена оценка временной сложности: для последовательного алгоритма и алгоритма «слепого поиска» она быть выражена формулой: 0(I*N); для генетических алгоритмов она быть

Л Л выражена формулой 0(aN )- 0(PN ), где N - число элементов схемы (размер решаемой задачи).

3. Определены оптимальные значения управляющих параметров для генетических алгоритмов: вероятность ОК должна быт в пределах 0,7-0,8, вероятность ОМ - 0,2. При данных значениях параметров обеспечиваются наилучшие условия для нахождения приемлемого по качеству решения задачи размещения.

4. Разработанные генетические алгоритмы размещения элементов показали преимущество по сравнению с последовательным алгоритмом и алгоритмом слепого поиска, качество решений удалось повысить на 1525%. Многопопуляционный параллельный генетический алгоритм улучшил решение задачи размещения с учетом временных задержек на 25% по результатам сравнения с бенчмарками, решенными известными алгоритмами Dragon и Flow.

ЗАКЛЮЧЕНИЕ

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

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

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

3. Разработан алгоритм построения модели цепи на основе дерева Штейнера в Манхэттенской метрике. Описана математическая модель цепи для вычисления значения оценки временной задержки. Проведен сравнительный анализ модели цепи на основе дерева Штейнера и модели Эльмора. Сделан вывод о том, что модель на основе дерева Штейнера является точнее модели Эльмора на 13-18%. Для расчета целевой функции в разрабатываемых генетических алгоритмах используется модель цепи на основе дерева Штейнера.

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

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

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

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

0(I*N); для генетических алгоритмов она быть выражена формулой 0(aN )-0((3N ), где N — число элементов схемы (размер решаемой задачи).

8. Разработанные генетические алгоритмы размещения элементов показали преимущество по сравнению с последовательным алгоритмом и алгоритмом слепого поиска, качество решений удалось повысить на 15-25%. Многопопуляционный параллельный генетический алгоритм улучшил решение задачи размещения с учетом временных задержек на 2-5% по результатам сравнения с бенчмарками, решенными известными алгоритмами Dragon и Flow.

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

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

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

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

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

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

7. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы

8. САПР. М.: Энергоатомиздат, 1987.

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

10. Норенков И.П., Маничев В.Б. САПР ЭВА. М.: Высшая школа, 1983. Ю.Гридин В.Н. Теоретические основы построения базовых адаптируемыхкомпонентов САПР МЭА. М.: Наука, 1989. П.Вермишев Ю.Х. Основы автоматизированного проектирования. М.: Радио и связь, 1988.

11. Sherwani Naveed. Algorithms for VLSI Physical Design Automation, Kluwer

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

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

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

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

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

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

18. Гладков Л.А., Курейчик В.В., Курейчик В.М. Основы теории алгоритмов / под ред. В.М. Курейчика. Учебное пособие по курсу «Математическая логика и теория алгоритмов». Таганрог. ТРТУ, 2002.-82с.

19. Харари Ф. Теория графов. М.: Мир, 1977.

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

21. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2000.

22. Иванов Б.Н. Дискретная математика. М.: Лаборатория базовых знаний, 2001. "

23. Зыков А.А. Основы теории графов. М.: Наука, 1987.

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

25. Петренко А.И. Тетельбаум А.Я. Модели электронных устройств при решении конструкторских задач. Кибернетика,№2,1978, с.47-54.

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

27. Баталов Б.В., Щемелинин В.М. Проектирование топологии интегральных схем на ЭВМ. М.: Машиностроение, 1979.

28. Нильсон Н. Принципы искусственного интеллекта.- М: Радио и связь, 1985.-376 с.

29. Мелихов А.Н., Берштейн Л.С. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов на-Дону. Изд-во РГУД981.

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

31. Петренко А.И., Тетельбаум А .Я., Шрамченко Б.Л. Автоматизация конструирования электронной аппаратуры (топологический подход). Киев: Вища шк., 1980.

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

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

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

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

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

37. Чернышев Ю.О., Яценко О. В. Определение нечеткости в задачах оптимизации функционально распределенных систем обработки данных и подходы к ее решению. IEEE AIS-02, CAD-2002. Интеллектуальные системы, интеллектуальные САПР, М.: Физматлит, 2002, с. 74-78.

38. Курейчик В.В., Курейчик В.М. Перспективные технологии для решения оптимизационных задач. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.1, М.: Физматлит, 2003, с 59-67.

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

40. Karypis G., Kumar V. A coarse-grain parallel multilevel k-way partitioning algorithm. In Proceedings of the eighth SIAM conference on Parallel Processing for Scientific Computing, 1997.,

41. Karypis G., Kumar V. hMETIS 1.5: A hypergraph partitioning package. Technical report, Department of Computer Science, University of Minnesota, 1998. Available on the WWWat URL http://www.es.umn.edu/.metis.

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

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

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

45. Caldwell A.E., Kahng A.B. and Markov I. L. Optimall Portitioners and End -Case Placers for Standard Cell Layout. -//-V.19, №11, November 2000, pp. 1304- 1313.

46. Kernighan В., Lin S. An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech.J., vol 49, Feb 1970, pp. 291-307.

47. Fiduccia C., Mattheyses R. A linear time heuristics for improving network partitions. Proceedings 19th ACM/IEEE Design automation conference, 1982, pp. 175-181.

48. Saab. Y. A new effective and efficient multi-level partitioning algorithm. Proceedings Design, Automation and Test in Europe Conference 2000, Paris, France, 27-30 March 2000, pp. 112-116.

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

50. Дарвин Ч. Происхождение видов путем естественного отбора. М.: «Тайдекс Ко», 2003.

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

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

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

54. Goldberg David E. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989.

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

56. Эволюционные вычисления и генетические алгоритмы. Составители Гудман Э.Д., Коваленко А.П. Обозрение прикладной и промышленной математики. М.: Изд-во ТВП, 1966.

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

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

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

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

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

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

63. Курейчик В.М., Курейчик В.В. Генетический алгоритм разбиения графа// Известия АН. Теория и системы управления, № 5, 1999, с.79-87.

64. Плеханов А.С. Компонентное разбиение в совместном проектировании аппаратно-программных средств на основе масштабируемых моделей IEEE AIS-02, CAD-2002. Интеллектуальные системы, интеллектуальные САПР, М.: Физматлит, 2002, с. 349-350.

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

66. Смирнова О.В. Модели эволюции в задачах компоновки схем ЭВА. Перспективные информационные технологии интеллектуальные системы, №1 (19), 2002, с.47-49.

67. Frohlich N., Glockel V., Fleischmann J. A new partitioning method for parallel simulation of VLSI circuits on transistor level. Proceedings Design,

68. Automation and Test in Europe Conference, 2000, Paris, France, 27-30 March 2000, pp.679-685.

69. Лежебоков А.А. Решение задачи размещения элементов СБИС с учетом временных задержек. // Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 2006. №8(63). с. 146-151.

70. Wei Y.C., Cheng С.К. A two-level two-way partitioning algorithm, Tech. report CH2924-9, University of California, San Diego, IEEE, 1990.

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

72. Bui T: N., Moon B. R. Genetic algorithm and graph partitioning, IEEE Trans. Comput., vol.45, 1996, pp. 841-855. •

73. Chandrasekharam R., Subhramanian and chadhurys. Genetic algorithms for node partitionaly problem and application in VLSI design. IEEE Proc-E, Vol.140, No.5, September, 1993. pp. 167 178.

74. Kling R.M., Banerjee P.: Placement by Simulated Evolution. IEEE Trans, on CAD, Vol.8, No.3, 1989. pp. 245-256.

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

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

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

78. Лежебоков А.А. Программная реализация алгоритма решения задачи размещения с учетом временных задержек. // Известия ЮФУ. Технические науки Тематический выпуск "Интеллектуальные САПР", №2(77), 2007. Таганрог: Изд-во ТТИ ЮФУ, 2007. - с. 65-70.

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

80. Попов Э.В. Экспертные системы реального времени. Открытые системы №2(10), 1995. http://kiryushin.boom.ru/docs/esrv.htm.

81. Осипов Г.С. Приобретение знаний интеллектуальными системами. М.: Наука, 1997.

82. Микони С.В. Взаимодействие БЗ и системы выбора. Интеллектуальное управление: новые информационные технологии в задачах управления, М.: Наука, 1999,с.68-72.

83. Джексон П. Введение в экспертные системы. М.: Издательский дом «Вильяме», 2001.

84. Дейт К. Введение в системы баз данных (седьмое издание).-М.: Вильяме. 2001.

85. Уотермен О. Руководство по экспертным системам. М.: Мир, 1989.

86. Искусственный интеллект: В 3 кн. Кн. 1. Системы общения и экспертные системы. Справочник / Под ред. Э.В. Попова. М.: Радио и связь, 1990.

87. Искусственный интеллект: В 3 кн. Кн. 2. Модели и методы . Справочник / Под ред. Д.А. Поспелова. М.: Радио и связь, 1990.

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

89. Аверкин А.Н. и др. Приобретение и формализация знаний. Искусственный интеллект. М.: Радио и связь, 1990.

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

91. Непейвода Н.Н. Прикладная логика. Издание 2-е. Новосибирск, изд-во Новосибирского университета, 2000.

92. Luger G. Artificial Intelligence: Structures and Strategies for Complex

93. Problem Solving. Fourth Edition. Addison-Wesley Publishing Company, 2002.

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

95. Лежебоков А.А., Гладков Л.А. Моделирование временных задержек при решении задачи размещения элементов СБИС. // Известия ТРТУ, №1(73), 2007. Таганрог: Изд-во ТРТУ, 2007. - с. 75-77.

96. Берштейн Л.С., Карелин В.П., Целых А.Н. Модели и методы принятия решений в интегрированных ИС. Ростов-на —Дону, изд-во РГУ,1999.

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

98. Цетлин М.Л. Исследования по теории автоматов и моделирование биологических систем.- М.: Наука, 1969.

99. Курейчик В.М., Мухлаев А.В. Моделирование адаптации в алгоритмах синтеза топологии электронных систем. Программные продукты и системы,№3, 2000, с.13-16.

100. Chen С.Р., Chen Y.P., Wong D.F. Optimal Wiresizing Under Elmore Delay Model // IEEE Trans. On CAD of Integrated Systems.- 2002. -V21-№3, pp.319-329

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

102. Rubinstein J, Penfield P. jr., Horowitz M.A. Sifnal delay in RC tree networks. // IEEE Trans. On CAD of Integrated Systems.- 2002. -V2-№3, pp.202-211, 1983

103. Semiconductor Industry Association. National Technology Roadmap for Semiconductors. 1997.

104. В частности, были использованы следующие результаты кандидатской диссертации А.А. Лежебокова:- модифицированная архитектура генетического поиска;- методика построения модели цепи схемы на основе дерева Штейнера длярасчета оценки временной задержки.

105. Заместитель руководителя работы1. В.В. Курейчикруководителя ТТИ ЮФУ тботе1. В.М. Курейчик2008 г.t1. АКТоб использовании научных результатов диссертационной работы на соискание ученой степени кандидата технических наук Лежебокова А.А.

106. Научные результаты, полученные в диссертационной работе А.А. Лежебокова, использовались в госбюджетной работе №12361 «Разработка интеллектуальных систем проектирования для решения задач разбиения СБИС на основе эволюционных методов».

107. Научные результаты, полученные в диссертационной работе А.А. Лежебокова, использовались в госбюджетной работе №12362 «Разработка бионических методов и принципов поиска оптимальных решений при проетировании».

108. TElement Element 1024.; TElementType ElementTypes[100]; int ElementTypeCount = 0; AnsiString WorkingDirPath; AnsiString IniPath; // константы

109. TColor CFonColor = clBtnFace; TColor CPixelColor = clBlack;

110. SizeDRPX = StrToIntDef(InputSizeDRPForm->GorEdit->Text,1) //SizeDRPY = StrToIntDef(InputSizeDRPForm->VerEdit->Text,1) SizeDRPX = StrToIntDef(InputSizeDRPForm->ComboBoxl->Text,1)

111. ElementTekCell.Type = random(ElementTypeCount);1. TekCell + +; }

112. PB->Canvas->Pen->Color = clBlack; MainForm->PB->Canvas->Pen->Style = psSolid; MainForm->PB->Canvas->Pen->Color=clBlack;t=0;for(int il=0;il<SizeDRPY;il++)for(int i2=0;i2<SizeDRPX;i2++) {

113. PB->Canvas->Rectangle(pointil.[12].x 25,point[il][12].у30,pointil.[i2].x + 29,point[il][i2].у + 34);

114. PB->Canvas->Brush->Color = clOlive; PB->Canvas->Brush->Color = clSilver;

115. PB->Canvas->Rectangle(pointil. [12] .x 30,point[il] [i2] .у -40,point[il][i2].x + 30,point[il][12].у + 40);

116. PB->Canvas->Brush->Color = clOlive;

117. PB->Canvas->Pen->Color = clWhite;

118. PB->Canvas->MoveTo(pointxl.[yl].x,point[xl][yl].y);

119. PB->Canvas->LineTo(pointx2.[y2].x,point[x2][y2].у); }

120. PB->Canvas->Pen->Width = 1; /*

121. PB->Canvas->Pen->Color = colLineDRP; int TekCell=0;for(int il=0;il<SizeDRPY;il++)for(int i2=0;i2<SizeDRPX;i2++) {

122. PB->Canvas->Rectangle(pointil.[i2].x 25,point[il][i2].у -30,point[il][i2].x + 27,point[il][i2].у + 32);

123. PB->Canvas->Rectangle(pointil.[i2].x 25,point[il][i2].у -30,point [il] [i2] .x + 25, point [il] [i2] . у + 30);

124. PB->Canvas->TextOut(pointil.[i2].x 22,point[il][i2].у -25,IntToStr(TekCell+1));1. TekCell++; }/*

125. PB->Canvas->Pen->Color = clBlack; for(int il=0;il<SizeDRPY;il++)for(int i2=0;i2<SizeDRPX;i2++) {

126. PB->Canvas->Brush->Color = clBlack;

127. PB->Canvas->Rectangle(pointil.[i2].x 15,point[il][i2].у -13,point[il][12].x + 15,point[il][i2].y + 17);

128. PB->Canvas->Brush->Color = colTopGraf;

129. PB->Canvas->Rectangle(pointil.[12].x 13,point[il][i2].у -11,point[il][i2].x + 17,point[il][12].y + 19);

130. PB->Canvas->TextOut(pointil.[12].x 5,point[il][i2].у5,IntToStr(DRP il. [12]+1) ) ; }t=0;for(int i1 = 0;il<SizeDRPY;il++)for (int i2=0;i2<SizeDRPX;i2 + + ) {

131. PB->Canvas->Brush->Color = clRed; // PB->Canvas->Rectangle(pointil.[12].x 25,point[il][12].у30,pointil. [i2] .x + 29,point[il] [i2] . у + 34);

132. PB->Canvas->Brush->Color = clOlive; PB->Canvas->Brush->Color = (TColor)RGB(206,206,0); PB->Canvas->Rectangle(pointil.[12].x 25,point[il][i2].у -30,point[il][12].x + 25,point[il][i2].y + 30);

133. PB->Canvas->Brush->Color = clOlive;

134. PB->Canvas->TextOut(pointil.[±2].x 22,point[il][i2].у25,IntToStr(t+1)); */

135. MatrSmegForm->ShowModal() ;if(MatrSmegForm->set==true) {for (int i=0; i<SizeDRPY;i++)for (int j=0; j<SizeDRPX;j ++) {1. DRP1.j. = INum; lNum++; 1lNum=0;for (int i=0; i<SizeDRPY*SizeDRPX;i++)for (int j =0; j<SizeDRPY*SizeDRPX; j++) {

136. Matrsm1.j. = random(2); Matrsm[j][i] = Matrsm[i][j];if(i==j) Matrsmj.1.=0; }

137. MatrSmegForm->ShowModal();if(MatrSmegForm->set==true) {for (int i=0; i<SizeDRPY*SizeDRPX;i++)for (int j =0; j<SizeDRPY*SizeDRPX;j ++) {

138. Rg = StrToFloatDef ( OptionForm->edtRG->Text, 1 );

139. Cg = StrToFloatDef ( OptionForm->edtCG->Text, 1 );r = StrToFloatDef ( OptionForm->edtR->Text, 1 );с = StrToFloatDef ( OptionForm->edtC->Text, 1 );for(int i=0;i<SizeDRPY*SizeDRPX;i++) for(int j=i;j <SizeDRPY*SizeDRPX;j++) if(Matrsm1.j.!=0)

140. Application->MessageBox("Сначала необходимо ввести граф!","Внимание!",MBOK|MBICONWARNING);return; }1. N21Click(this);if(count!=0) {