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

005532028

КУЛИЕВ Эльмар Валерьевич

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

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

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

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

15 АВГ 2013

Таганрог 2013

005532028

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

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

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

Официальные оппоненты: д.т.н., проф., кафедры информатики

Таганрогского государственного педагогического института имени А.П. Чехова

ВИТИСКА Николай Иванович

д.т.н., проф., кафедры автоматики и телемеханики на железнодорожном транспорте Ростовского государственного университета путей сообщения КОВАЛЕВ Сергей Михайлович

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

образовательное учреждение Донской Государственный технический университет (ДГТУ г. Ростов-на-Дону).

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

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

Автореферат разослан «06» августа 2013 г.

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

диссертационного совета Д 212.208.22, доктор технических наук, профессор Целых А.Н.

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Создание программного комплекса, использующего разработанные алгоритмы размещения.

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

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

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

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

2. Построена модифицированная модель адаптивного поведения пчелиной колонии применительно к задачи размещения, отличающаяся принципами формирования окрестностей.

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

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

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

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

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

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

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

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

4. Механизмы интеграции моделей эволюционной адаптации и адаптивного поведения пчелиной колонии.

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

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

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

При разработке программного комплекса применялись пакеты программ в среде Borland С++ Builder 6.0. Тестирование и отладка разработанного программного комплекса проводились на ЭВМ типа IBM PC с процессором Intel Core В. Экспериментальные данные разработанных алгоритмов превосходят данные известных алгоритмов, а также позволяют получать квазиоптимальные решения за полиномиальное время

Реализация результатов работы. Основные результаты диссертационной работы использованы в НИР № 301.38-11/2013-14 «Разработка теории и принципов эволюционной оптимизации и принятия решений на основе методов и моделей адаптивного поведения биологических систем», а также в Грант РФФИ (№ 12 - 07 - 00058) «Разработка теоретических основ информационных технологий поддержки принятия решений при оптимизации и проектировании на основе методов, инспирированных природными системами», Грант РФФИ (№ 12 - 01 - 00100) «Разработка теории и принципов коллективного интеллекта на основе моделей адаптивного поведения муравьиной колонии для решения оптимизационных задач», Грант РФФИ № 12381 (№ 10 - 07 - 00055) «Разработка теории и принципов поиска решений в экспертных системах на основе методов и моделей адаптивного поведения биологических систем», Грант РФФИ № (№ 1107 — 00064) «Разработка теории и принципов создания интегрированных методов интеллектуального анализа данных для реализации на высокопроизводительных вычислительных системах», Грант РФФИ № 12388 (№ 11 - 01 - 00975) «Разработка теории и принципов управления точностью решения комбинаторно-логических задач на основе методов искусственного интеллекта и принятия решений».

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

Апробация работы. Основные результаты диссертационной работы обсуждались и были одобрены на научных семинарах (с 2009 по 2012 гг., ТТИ ЮФУ), VI Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «МОЛОДЕЖЬ XXI ВЕКА — БУДУЩЕЕ РОССИЙСКОЙ НАУКИ» (г.Ростов-на-Дону, 2009), Молодежной научно-технической конференции «Интеллектуальные системы - 2009» («ИС-2009») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'09» (Дивноморское, 2009 г.), Молодежной научно-технической конференции «Интеллектуальные системы - 2010» («ИС-2010») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'10» (Дивноморское, 2010 г.), Молодежной научно-технической конференции «Интеллектуальные системы - 2011» («ИС-2011») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'12» (Дивноморское, 2012 г.).

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

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 147 страницы, а также 58 рисунков, 6 таблиц, список литературы из 107 наименований, 7 страниц приложений, в числе которых акты об использовании результатов диссертационной работы.

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

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

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

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

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

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

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

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

Результаты предыдущего шага конструкторского

(трассировка)

Рисунок 1 - Архитектура модифицированного гибридного алгоритма размещения

На рисунке 1 также представлен блок анализа неперспективных решений (Блок №7). Данный блок анализирует и собирает решения в ходе выполнения генетического алгоритма. В ходе анализа каждому индивиду присваивается определённый ранг (неперспективное, перспективное, тривиальное и др.).

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

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

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

Рисунок 2 - Архитектура модифицированного поиска

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

ЭА - эволюционный алгоритм;

РА - роевой алгоритм, основанный на методе пчелиной колонии.

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

1 э а і

Рисунок 3 — Двухуровневый алгоритм поиска оптимальных решений

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

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

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

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

С

3

Редукция (отбор)

г

ГТ

окрестности

іст окрестностей ■і кол-ва агентов дна каждого ретени

Рисунок 4 - Гибридный алгоритм размещения компонентов СБИС

Исследование перспективных позиций, а также окрестностей в пространстве решений является важным вопросом при рассмотрении алгоритма колонии пчел. Предложена процедура формирования окрестности поиска методом колонии пчел. Рассмотрим принцип работы пчелиного алгоритма на примере. Пусть в пространстве решений в найдено 10 источников нектара (рисунок 5). Для каждого источника нектара определяется ЦФ. Каждый источник нектара имеет окрестность для поиска, которая будет задаваться динамически изменяющейся переменной I. Границы переменной I определяются как число неповторяющихся значений ЦФ в данной области поиска (рисунок 6). К полученным решениям (хромосомам) применяются генетические операторы, в результате работы которых ЦФ значений улучшается.

-31.

'24,

14 '

V IV •

- ' -..Л-1'; V,'*, ' . '

-V- -л 52 -"-Л'-', ' "'г ; ..V

> « . ' „'«.-- . Ш-* - I • ♦

-У''-

• ' * V

Рисунок 5 - Область поиска альтернативных решений

ЦФ I 52

50

31

24

14

13

11

Рисунок б - Ранжированная популяция альтернативных решений

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

Схематичное представление данной процедуры поиска представлено на рисунке 7.

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

В параграфе 4.1. представлены цели экспериментальных исследования.

Параграф 4.2. приводит описание интерфейса программного комплекса.

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

1) генетический алгоритм; 2) роевой алгоритм; 3) гибридный алгоритм.

Результаты экспериментальных исследований для 1000 итерация представлены в таблице 1.

Определена временная сложность разработанного гибридного алгоритма. Таблица 1 Результаты экспериментальных исследований для ЮООитераций

Начальное Генетический Роевой Гибридный

размещение алгоритм алгоритм алгоритм

600_600 215640 182621 125556 118978

1200_1200 1093221 773157 587683 512732

3000_4500 1593160 1445161 1165326 715545

8000 7600 5662719 2575481 1961520 1214671

12000 9000 3704285 2961622 2319658 1238092

В таблице 2 и на рисунке 8.отображены показатели зависимости времени работы алгоритмов от размера схемы.

Таблица 2 Зависимость времени работы алгоритмов от размера схемы

Число элементов схемы

Алгоритмы 100 200 300 400 500 600 700 800 900 1000

Генетический 0,2 0,6 0,9 1,2 1,5 1,9 2,3 3,3 4,7 7,5

Эволюционный 1,5 2,3 2,3 3,3 5,2 9,8 11,7 16,4 28,6 56,3

Роевой 3,6 5,6 8 9,4 13,1 17,8 28,6 32,8 46,4 87,7

Гибридный 8,5 10,1 12,6 15,5 24,3 35,2 50,2 63,3 82 108,8

ГА —ЗА —*_ Р«*мй - м . Гвбршамй

1?о • У

г

2

60

_____—

—-5--—"

1 сю а ста зоо «оо воо ьоо 700 воо »ао юоо

Рисунок 8 - Зависимости времени работы алгоритмов от количества элементов схемы.

В таблице 3 и на рисунке 9 отображена эффективность работы разработанного гибридного алгоритма.

Таблица 3 Определение эффективности алгоритмов

Число элементов схемы

Алгоритмы 1000 2500 5000 7500 10000

Генетический 65,4 115,5 139,8 150,4 200,8

Эволюционный 50,1 102,7 124,6 144,9 193,6

Пчелиный 60,3 82,6 104,1 136,7 155,8

Гибридный 58,9 80,2 95,7 123,1 145,1

О ГА а Рое вс

а за

СЗ Гибрндиый

Рисунок 9 - Гистограмма сравнения качества решения,

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

Бенчмарки Число элементов Число цепей ЦФ Бга§оп ЦФ Р1очг ЦФ ГбпА

5ирегЫие19 12506 13636 151.1 149.2 160.5

вирегЫиеЫ 19342 19935 180.5 190.2 189.5

.яирегЬ1ие16 22853 27118 210.2 235.2 236.2

яирегЫиеЭ 27220 31769 245.5 244.5 250.6

вирегЫиеЗ 28146 28220 215.7 230.5 232.4

БирегЫиеП 32332 34654 274.2 289.6 300.5

йирегЫиеб 45639 47786 327.9 335.8 340.4

кирегЫие2 51023 51227 350.4 365.5 354.2

5ирегЫие12 53110 60606 400.5 398.5 392.6

хирегЬ1ие7 68685 74179 450.7 469.5 472.1

5ирегЫие19 33186 33622 271.6 268.4 265.1

На основе экспериментальных данных, можно судить, что разработанные модифицированные алгоритмы показали преимущество по сравнению с .итерационным и последовательным алгоритмами, качество решений удалось повысить на 15-25%. Гибридный алгоритм улучшил решение задачи размещения на 7-12% по результатам сравнения с бенчмарками

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

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

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

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

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

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

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

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

6. Разработана двухуровневая архитектура эволюционного алгоритма размещения элементов СБИС.

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

8. Представлены процедуры кодирования-декодирования решений и формирования окрестности поиска методом роевого интеллекта.

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

10. Создан программный комплекс для решения задачи размещения, проведены экспериментальные исследования разработанных модифицированных алгоритмов. Определены оценки временной сложности алгоритмов: для гибридного алгоритма она имеет вид: 0(Ы2) ч- 0(И3), где N — число элементов СБИС.

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

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

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

изданий ВАК РФ

1. Э.В. Кулиев, A.A. Лежебоков Исследование характеристик гибридного алгоритма размещения // Известия ЮФУ №3, март 2013г. стр. 255- 261

2. Э.В. Кулиев, A.A. Лежебоков О гибридном алгоритме размещения компонентов СБИС // Известия ЮФУ №11, ноябрь 2012г стр. 188-192

II Свидетельства о регистрации программ на ЭВМ

3. Свидетельство об официальной регистрации программы для ЭВМ № 2013614706, 2013г. Программа размещения на основе адаптивного поведения биологических систем

4. Свидетельство об официальной регистрации программы для ЭВМ № 2013614653, 2013г. Программа гибридного алгоритма размещения компонентов СБИС

III. Публикации в других изданиях

5. Э.В. Кулиев Разбиение на основе муравьиной колонии // Государственное образовательное учреждение высшего профессионального образования «Ульяновский государственный технический университет», стр. 324-326

6. Э. В. Кулиев, Б.К. Лебедев Определение функции окрестности в задачах размещения на основе роевого интеллекта // Материалы третьей международной конференции Автоматизация управления и интеллектуальные системы и среды. Нальчик 2012. Том 1. с 45-48

7. Э. В. Кулиев, Б.К. Лебедев Нахождение максимального значения функции с помощью пчелиного алгоритма // IX Всероссийская научная конференция молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление». Таганрог: Изд-во ТТИ ЮФУ, 2011.-Т.1. - С. 236-238

8. Э.В. Кулиев Генетический алгоритм решения задачи размещения элементов СБИС // X Всероссийская научная конференция молодых ученых аспирантов и студентов «Информационные технологии, системный анализ и управление». Таганрог: Изд-во ТТИ ЮФУ, 2012. -Т.2. - С. 55-59

9. Э.В. Кулиев, A.A. Лежебоков Эффективный способ кодирования решения для задачи размещения компонентов СБИС // Электронный журнал. Информатика, вычислительная техника и инженерное образование. Св. № ФС77-39729 от 29.04.2010г. - Таганрог: ТТИ ЮФУ, 2012, №8(10), - С. 1-6

10. Э.В. Кулиев, Д.В.Заруба Работа гибридного поиска размещения компонентов СБИС // Труды молодых ученых Южного федерального университета и Южного научного центра РАН «Высокопроизводительные вычислительные системы». Выпуск 2. Изд-во Ростов-на-Дону - Таганрог 2012. с 43-46

11. Э.В. Кулиев, Б.К. Лебедев Размещение элементов на основе природных вычислений // X Всероссийская научная конференция молодых ученых

аспирантов и студентов «Информационные технологии, системный анализ и управление». Таганрог: Изд-во ТТИ ЮФУ, 2012. - Т.1. - С. 70-73

12. Э.В. Кулиев, Лежебоков A.A. Архитектура гибридного поиска для размещения компонентов СБИС // Научная сессия НИЯУ МИФИ-2013. Аннотации докладов. В 3 томах. Т.2. Проблемы фундаментальной науки. Стратегические информационные технологии. М.: НИЯУ МИФИ, 2013. с. 320.

13. Э.В. Кулиев, Задача размещения элементов ЭВА с использованием генетического алгоритма и алгоритма пчелиной колонии // Труды конгресса по интеллектуальным системам и информационным технологиям «IS - IT'12». Научное издание в 4-х томах, т.З. - М.: Физматлит, 2012. - с.104

Личный вклад автора. Все результаты, изложенные в диссертации, получены лично автором. Автору также принадлежит ведущая роль в разработке и исследовании работы гибридного алгоритма. Автором были разработаны модифицированные алгоритмы, определены функции окрестности в задачах размещения на основе роевого интеллекта [1,2,6,7,8,10]; разработан генетический алгоритм решения задачи размещения элементов СБИС [9,11]; проведение исследований характеристик гибридного алгоритма размещения [1].

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

Соискатель

Э.В. Кулиев

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

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

04201 361 086 Кулиев Эльмар В алерьев ич

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

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

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

Научный руководитель: профессор кафедры САПР,

д.т.н., профессор Лебедев Б.К.

Таганрог 2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.............................................................................................................5

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

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

1.1.1 Развитие полузаказных матричных СБИС...............................................13

1.1.2 Иерархический подход к проектированию ЭВА.......................................13

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

1.3 Постановка задачи размещения компонентов СБИС...........................20

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

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

1.4.2 Анализ методов эволюционного моделирования.......................................30

1.4.3 Анализ модели муравьиной колонии...........................................................31

1.4.4 Анализ модели пчелиного роя......................................................................33

1.5 Выводы............................................................................................................37

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

2.1 Архитектура модифицированного гибридного алгоритма размещения...........................................................................................................38

2.2 Построение схемы гибридного поиска..............................................41

2.3 Построение модифицированной структуры гибридного поиска....................................................................................................................43

2.4 Метод биоинспирированного поиска.................................................46

2.5 Разработка гибридного двухуровневого подхода размещения компонентов СБИС.............................................................................................51

2.6 Модели адаптивного поведения биологических систем................55

2.6.1 Метод пчелиной колонии.............................................................................55

2.6.2. Алгоритм работы колонии пчел................................................................59

2.6.3 Метод генетического алгоритма.............................................................61

2.7 Разработка модифицированного генетического оператора.................66

2.8 Многоагентный подход к описанию разработанных моделей.............70

2.9 Выводы............................................................................................................74

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

3.1 Модифицированный гибридный алгоритм размещения компонентов СБИС.............................................................................................75

3.2 Гибридный алгоритм размещения компонентов СБИС.......................78

3.3 Модель модифицированного гибридного алгоритма размещения компонентов СБИС.............................................................................................81

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

3.5 Применение гибридного механизма для решения задач размещения компонентов СБИС.....................................................................89

3.6 Разработка роевого алгоритма размещения............................................95

3.6.1 Формирование окрестности поиска методом колонии пчел................100

3.7 Процедура кодирования - декодирования............................................102

3.8 Выводы..........................................................................................................106

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

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

4.2 Описание программного комплекса.......................................................108

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

4.3.1 Определение временной сложности разработанного гибридного алгоритма............................................................................................................121

4.4 Выводы..........................................................................................................125

ЗАКЛЮЧЕНИЕ.................................................................................................127

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ.....................................129

ПРИЛОЖЕНИЕ................................................................................................141

ВВЕДЕНИЕ

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

Проектирование СБИС производится на паномегровом диапазоне, чю ipe6yci новых методов и подходов.

В настоящее время вопросы развития методов, моделей, а также стратегий и алгоритмов автоматизированного проектирования сверхбольших интегральных схем нашло отображены в работах Норепкова И.П., Бершадского A.M., Курейчика В.М., Морозова К.К., Казепнова Г.Г., Селютипа В.А., Шервани Н., и др. В большинстве случаев, алгоритмы, методы и модели разрабатываемые специалистами направлены па формирования базового плана кристалла, а также на оптимизацию этапа трассировки. А именно этапа трассировки соединений по критерию минимизации длины связей и занимаемой площади [1 - 7].

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

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

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

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

В последнее время активно развивается научное направление Natural Computing, основанное на принципах природных механизмов пришпия решений и включающее генетические алгоритмы, иейросехевые вычисления, муравьиные алгоритмы, метод роящихся часшц, табуироваппый поиск и др АСО-алгори1мы обладают способностью находи ib более высококачсс1 венные решения за приемлемое время.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Посфоена модифицированная модель адаптивного поведения пчелиной колонии применительно к задачи размещения, отличающаяся принципами формирования окрестностей.

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

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

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

6. Разработана двухуровневая архитектура эволюционного алгоритма размещения шементов СБИС.

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

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

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

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

4. Механизмы интеграции моделей эволюционной адаптации и адаптивного поведения пчелиной колонии.

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

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

При носLроении программы использовались пакеты программ в среде Borland С++ Builder 6.0. Отладка и тестирование проводилось на ЭВМ шла IBM PC с процессором Intel Core 13. Экспериментальные данные разработанных алгоритмов превосходят данные извесшых ал гори imob, в качсове решения задачи размещения компонентов СБИС. Разрабо1анные алюришы размещения позволяют получать набор квазиогпимальных альтернативных решений за полиномиальное время.

Реализации результатов работы. Материалы диссер1 анионной рабопл использованы в НИР № 301.38-11/2013-14 «Разрабопса i сори и и принципов )волюциошюй оптимизации и принятия решений на основе меюдов и моделей адаптивного поведения биологических сис1ем», а также Граш РФФИ (№ 12 - 07 - 00058) «Разработка теоретических основ информационных технологий поддержки принятия решений при оптимизации и проектировании на основе методов, инспирированных природными системами», Грант РФФИ (№ 12 - 01 - 00100) «Разработка 1сории и принципов коллективного интеллекта па основе моделей адаптивного поведения муравьиной колонии для решения отними рационных «дач», Граш РФФИ № 12381 (№ 10 - 07 - 00055) «Разработка теории и принципов поиска решений в экспертных системах на основе меюдов и моделей адаптивного поведения биологических систем», Грант РФФИ № (№ 11 - 07 - 00064) «Разработка теории и принципов создания итерированных меюдов интеллектуального анализа данных для реализации па высокопроизводительных вычислительных системах», Грант РФФИ № 12388 (№ 11 - 01 - 00975) «Разработка теории и принципов управления iочное 1ыо решения комбинаторно-логических задач па основе методов искусственною интеллекта и принятия решений».

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

Апробация работы. Основные результаты диссер1ациошюй работы обсуждались и были одобрены на научных семинарах (с 2009 по 2012 ir., Т1И ЮФУ), Молодежной научно-технической конференции «Интеллектуальные системы - 2009» («ИС-2009») в рамках Кошресса по интеллектуальным системам и информационным технологиям «AIS-I Г09» (Дивпоморское, 2009 г.), Молодежной научно-технической конференции «Ишеллектуалытые системы - 2010» («ИС-2010») в рамках Кошресса по интеллектуальным системам и информационным технологиям «AIS-I Г'10» (Дивпоморское, 2010 г.), Молодежной научно-технической конференции «Интеллектуальные системы - 2011» («ИС-2011») в рамках Кошресса по интеллектуальным системам и информационным технолотиям «AIS-I Г11» (Дивпоморское, 2011 г.), Молодежной научно-технической конференции «Интеллектуальные системы - 2012» («ИС-2012») в рамках Кошресса по интеллектуальным системам и информационным технологиям «AIS-1P12» (Дивпоморское, 2012 г.).

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

Cipyiciypa и обьем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 147 страницы, а также 58 рисунков, 6 таблиц, список литературы из 107 наименований, 7 страницы приложений, в числе которых акты об использовании результатов диссертационной работы и листинг протраммпого комплекса.

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

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

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

сисi см.

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

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

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