Содержание к диссертации
Введение
1 Обзор и анализ существующих подходов к моделированию биоинспирированного поиска 14
1.1 Обзор и анализ методов проектирования СБИС 14
1.2 Описание маршрута проектирования СБИС 25
1.3 Сравнительная характеристика существующих подсистем биоинспирированного поиска 28
1.4 Постановка задачи размещения фрагментов СБИС 34
1.5 Выводы 39
2 Разработка гибридной архитектуры биоинспирированного поиска 41
2.1 Общие положения теории биоинспирированного поиска 41
2.2 Построение архитектуры подсистемы генерации биоинспирированных поисковых механизмов 44
2.3 Автоматизация процесса генерации стандартизированного представления алгоритмов оптимизации 54
2.4 Разработка генетического алгоритма для генерации иерархических поисковых процедур 59
2.5 Выводы 64
3 Разработка биоинспириров анной инструментальной среды для решения задач конструкторского проектирования СБИС 65
3.1 Построение модели организации подсистемы биоинспирированного поиска 65
3.2 Разработка гибридного алгоритма решения задачи размещения фрагментов СБИС с использованием разработанной интегрированной инструментальной подсистемы 71
3.3 Разработка механизма кодирования и декодирования для решения задачи размещения фрагментов СБИС 72
3.4 Построение атомарных поисковых процедур для решения задачи размещения фрагментов СБИС 78 3.5 Построение гибридных архитектур поиска 107
3.6 Пример работы разработанного алгоритма размещения фрагментов СБИС ПО
3.6 Выводы 117
4 Исследование эффективности подсистемы биоинспирированного поиска на примере задачи размещения фрагметов СБИС 118
4.1 Цель экспериментальных исследований 118
4.2 Теоретические оценки временных и пространственных характеристик гибридного алгоритма размещения 120
4.3 Планирование вычислительного эксперимента 123
4.4 Основные результаты экспериментальных исследований 125
4.4 Выводы 131
Заключение 132
Литература
- Сравнительная характеристика существующих подсистем биоинспирированного поиска
- Построение архитектуры подсистемы генерации биоинспирированных поисковых механизмов
- Разработка механизма кодирования и декодирования для решения задачи размещения фрагментов СБИС
- Теоретические оценки временных и пространственных характеристик гибридного алгоритма размещения
Введение к работе
Актуальность темы исследований. Современное развитие человечества в области создания объектов новой техники, оригинальных процессов и технологий уже не возможно без использования автоматических и автоматизированных систем поддержки процессов их проектирования. Подобные системы характеризуются большой алгоритмической и аппаратной сложностью, поэтому при их разработке и реализации целесообразно использование системного подхода.
Проектирование СБИС является сложным, трудоемким процессом, который должен осуществляться в кратчайшие сроки, с минимизацией затрат и с учетом такого немаловажного показателя, как качество проектируемых продуктов.
Основным средством достижения этих целей при проектировании СБИС являются системы автоматизированного проектирования.
В настоящее время при разработке СБИС выполняется общепринятая последовательность этапов проектирования: системная спецификация, функциональное проектирование, алгоритмическое проектирование, конструкторское проектирование, верификация, технологическое проектирование (изготовление кристаллов (чипов), сборка, тестирование и контроль.
На этапе конструкторского проектирования одной из наиболее сложных является задача размещения фрагментов СБИС, так как в состав современной СБИС входят несколько сотен логических блоков, а размещаемая схема занимает до 80% ее площади. В условиях быстрого прогресса в области информационных технологий используемые алгоритмы автоматизированного проектирования не позволяют находить эффективные решения или требуют большое количество процессорного времени для их поиска. Поэтому разработка новых эвристических подходов, основанных на биоинспирированном поиске, для решения задач конструкторского проектирования является актуальной научно-технической проблемой, имеющей важное народно-хозяйственное значение.
Большой вклад в разработку и исследование интеллектуальных САПР, эволюционного моделирования и биоинспирированного поиска внесли Д.И. Батищев, A.M. Бершадский, Л.С. Берштейн, Г.Г. Казенов, В.М. Курейчик, А.Н. Мелихов, Ю.А. Гатчин, Д. Холланд, И.П. Норенков, Г.Г. Рябов, Н. Шервани, Ю.О. Чернышев, А.П. Карпенко, В.Н. Гридин, И.Л Букатова и многие другие.
Цель работы состоит в разработке и исследовании подсистемы биоинспирированного поиска для повышения эффективности и качества решения задач конструкторского проектирования.
Для достижения сформулированной цели в диссертации были поставлены следующие основные задачи:
-
Сформулировать общие принципы разработки методов и алгоритмов биоинспирированной оптимизации.
-
Разработать модуль создания новых механизмов оптимизации, в рамках которой построить генетический алгоритм генерации новых иерархических поисковых процедур.
-
Построить модель организации подсистемы биоинспирированного поиска.
-
Разработать атомарные поисковые процедуры (АПП) на основе генетического, эволюционного, муравьиного, пчелиного и бактериального алгоритма.
5. Разработать гибридный биоинспирированный алгоритм размещения фрагментов СБИС с использованием построенной подсистемы биоинспирированного поиска.
Методы исследования. Для решения поставленных задач автором использовались модели и методы фундаментальных теорий алгоритмов, графов, биоинспирированной оптимизации, механизмы планирования экспериментов и математической статистики, а также теории популяционных алгоритмов, линейного, параллельного и объектно-ориентированного программирования.
Разработанные в рамках данной диссертационной работы положения подтверждаются результатами экспериментальных исследований.
Научная новизна работы состоит в следующем.
-
Разработана подсистема биоинспирированного поиска для решения задач конструкторского проектирования СБИС, основанная на моделировании поведения биологических видов и позволяющая сократить время реализации алгоритмов для решения различных задач автоматизированного проектирования (пункт 4 паспорта специальности 05.13.12).
-
Построены лингвистические (протокол передачи) и программные средства, а также структура формального описания процедур биоинспирированного поиска, позволяющая хранить и обрабатывать полученные архитектуры поиска в едином формате разработанной подсистемы (пункт 6 паспорта специальности 05.13.12).
-
Разработан модуль создания новых механизмов оптимизации, основанных на использовании методов генетического поиска, для уменьшения времени, затрачиваемого на разработку алгоритмов оптимизации при решении задач конструкторского проектирования СБИС (пункт 3 паспорта специальности 05.13.12).
-
Разработаны эволюционный, генетический, муравьиный, пчелиный и бактериальный алгоритмы решения задачи размещения фрагментов СБИС, позволяющие находить наборы оптимальных и квазиоптимальных решений за полиномиальное время (пункт 3 паспорта специальности 05.13.12).
-
Построен новый гибридный алгоритм решения задачи размещения фрагментов СБИС с использованием разработанной подсистемы биоинспирированного поиска, позволяющий эффективно решать задачу размещения фрагментов СБИС за полиномиальное время (пункт 3 паспорта специальности 05.13.12).
Практическая ценность работы заключается в реализации механизма биоинспирированного поиска для решения задач конструкторского проектирования СБИС в виде законченного клиент-серверного приложения, использование которого позволяет эффективно управлять гибридными алгоритмами решения различных задач конструкторского проектирования, разрабатывать новые и модифицировать существующие биоинспирированные механизмы оптимизации, а так же генерировать новые многоуровневые биоинспирированные алгоритмы, для повышения скорости и эффективности разработки инструментов автоматизации конструкторского проектирования. Второй основной практический результат диссертационной работы состоит в конструировании нового гибридного биоинспирированного алгоритма решения задачи размещения фрагментов СБИС как результата использования предложенной в данной диссертационной работе подсистемы.
Реализация и внедрение результатов работы. Результаты диссертационной работы использовались в ряде НИОКР, выполненных в Институте компьютерных
технологий и информационной безопасности Южного Федерального университета, направленных на решение задач конструкторского проектирования. К наиболее важным результатам следует отнести:
-
Участие в реализации гранта РФФИ №13-01-00371 «Разработка теории и принципов построения интеллектуальных систем проектирования для решения задач разбиения СБИС на основе биоинспирированных методов».
-
Участие в реализации гранта РФФИ №14-07-00829 «Разработка комплекса гибридных моделей, методов и алгоритмов поддержки принятия решений для интеллектуальных информационных систем транспортной логистики».
-
Участие в реализации гранта РФФИ №15-01-05669 «Разработка основ теории и принципов построения иерархических клиент-серверных архитектур для реализации быстродействующих подсистем конструкторского проектирования СБИС».
-
Участие в реализации гранта РФФИ №12-01-31356 «Разработка теоретических основ и принципов размещения компонентов СБИС на основе адаптивных процедур».
-
Участие в реализации ГБ 213.01-11/2014-56ПЧ на выполнение проектной работы в части государственного задания МИНОБРНАУКИ России в сфере научной деятельности.
Материалы диссертации внедрены в учебный процесс кафедры систем автоматизированного проектирования Южного федерального университета.
Апробация. Основные результаты, представленные в диссертационной работе, обсуждались на международных, всероссийских и региональных научных конференциях: конгрессе по интеллектуальным системам и информационным технологиям «AIS-IT'll» (Дивноморское, 2011г.), Молодежной научно-технической конференции «Интеллектуальные системы - 2011» («ИС-2011»), X Всероссийская научная конференция молодых ученых аспирантов и студентов «Информационные технологии, системный анализ и управление» (Таганрог, 2012г.), конгресс по интеллектуальным системам и информационным технологиям «AIS-IT'12» (Дивноморское, 2012г.), конгрессе по интеллектуальным системам и информационным технологиям «IS-IT' 14» (Дивноморское, 2014г.), конгрессе по интеллектуальным системам и информационным технологиям «IS-IT' 15» (Дивноморское, 2015г.).
Публикации. По теме диссертационной работы опубликовано 19 печатных работ, в числе которых 10 - в изданиях, рекомендованных ВАК РФ; 3 - в изданиях, индексируемых в базе данных Scopus; 4 Свидетельства о государственной регистрации программ для ЭВМ.
Структура и объем работы. Диссертационная работа включает следующие разделы: введение, четыре раздела и заключение, изложенные на 147 страницах, содержит 55 рисунков, 8 таблиц, 115 наименований библиографии и приложение.
Сравнительная характеристика существующих подсистем биоинспирированного поиска
Самые нижние маски определяют формирование базовых транзисторов на кремниевой подложке, следующие уровни определяют их топологические соединения металлическими проводниками для формирования базовых логических элементов и макро-блоков. Верхние уровни масок определяют межсоединения между крупными макроблоками (мега-элементами) и конфигурацию ввода-вывода. В современных технологических процессах производства полупроводников используется свыше срока масок, определяющих транзисторы, слои металлизации и изоляции. Стоимость комплекта масок достигает миллиона долларов и выше [6].
К основным характеристикам заказных СБИС относятся [5,8]: Все слои масок полностью заказные, могут быть использованы для производства только этой конкретной СБИС. Разработчик должен спроектировать топологию каждого вентиля своими руками (без использования стандартных библиотек). Возможны частично автоматизированное размещение и трассировка. Критические пути проектируются практически вручную или с использованием специального инструментария, управляемого уникальными скриптами разработчика.
Полностью заказное проектирование СБИС дает возможность получить наиболее высокую производительность и минимальную цену кремния (меньший размер чипа) для конкретной разработки.
Недостатками заказной разработки СБИС являются длительное время разработки (годы для больших процессоров), сложность и дороговизна процесса разработки, а также наиболее высокий риск (ошибки и задержки).
Обычно микропроцессоры раньше выполнялись в виде полностью заказных СБИС, но сейчас проявляется массовая тенденция использования технологий проектирования полузаказных СБИС, особенно в системах на кристалле. Другими примерами полнозаказных микросхем являются специализированные схемы для высоковольтной логики (автомобили), аналого-цифровые схемы (коммуникации), датчики и микромеханизмы, также как динамическая память DRAM [4,8].
Основными характеристиками полузаказных СБИС на основе стандартных элементов-ячеек являются [8]: Используется так же аббревиатура CBIC —"sea-bick (Cell-basedASIC). Используются библиотеки стандартных элементов. Возможно использование предварительно спроектированных мега-ячеек, мегафункций, полнозаказных мега-ячеек, системных макросов, блоков с фиксированными функциями, готовых процессорных ядер (IP-ядер) от других поставщиков, или стандартных функциональных блоков.
Все слои масок являются заказными - размещение транзисторов и все соединения между ними. Автоматизированное изменение размерности буферов, размещение блоков и трассирование межсоединений. Полнозаказные блоки легко могут быть встроены в структуру СБИС без проблем (если спроектированы под ту же технологию). Ориентировочное время производственного цикла с момента получения топологии в виде GDS файла около восьми недель. Этот тип полузаказных СБИС является базовой кремниевой платформой для современных систем на кристалле (СнК). Размещение блоков и трассирование межсоединений в полузаказной СБИС на основе стандартных элементов и макроблоков происходит следующим образом.
Так как с точки зрения свободы размещения блоков и макроблоков этот тип СБИС близок к полнозаказной и отличается только использованием заранее спроектированных библиотечных элементов и макроблоков, то размещение базовых транзисторов может быть совершенно произвольным и определяется макрокомпоновкой топологии (Рис. 1.3) полузаказной СБИС.
Библиотечные элементы-ячейки в такой СБИС могут располагаться в виде матрицы, имеющей определенное число строк и столбцов, пресечениями которых являются логические элемент - ячейки. Между строками и столбцами могут оставляться пространства (каналы) для разводки межсоединений. И полузаказная структура СБИС строится путем соединения этих ячеек-элементов в логические схемы в соответствии с принципиальной схемой логического устройства, оформленной в виде списка логических сетей в формате EDIF или структурного кода VHDL/Verilog.
На рис. 1.4 показана структура топологии полузаказной СБИС на основе базовых стандартных библиотечных элементов и макроблоков.
«Стена» из стандартных элементов используется для формирования полузаказного макроблока. Слой металлизации Metal2 может быть использован в специальных промежутках между элементами (feedthrough cell) для пересечения линейки стандартных элементов, которые используют слой металлизации metal 1 для межсоединений внутри линейки стандартных элементов.
Построение архитектуры подсистемы генерации биоинспирированных поисковых механизмов
В общем случае процесс автоматизации процесса генерации стандартизированного представления алгоритма оптимизации (СПАО) состоит из следующих этапов:
1. Определение множества АППА(аі). На данном этапе ЛПР определяется множество всех атомарных поисковых процедур, которые могут быть включены в конечный алгоритм оптимизации.
2. Определение функции оценки результирующего алгоритма оптимизации Q(i//(F)), где F-результирующий алгоритм оптимизации, ц/ функция оценки (критерий) с известным глобальным или квазиоптимальным значением. Є= fbest - result (2Л) где y/best - известное глобальное или квазиоптимальное решение, result ЛУ41116 решение, полученное разрабатываемым генетическим алгоритмом. Очевидно, что для задачи минимизации при О О результирующий алгоритм (СПАО) является не эффективным, по сравнению с тем, с помощью которого было получено значение best- В качестве оценок для сравнения целесообразно применять бэнч марки.
3. Ввод ограничений С(СІ). К таким ограничениям можно отнести временные ограничения, а так же ограничения, специфичные для решаемой задачи.
4. Вид решения VIEW, с которым будет работать алгоритм оптимизации. Другими словами необходимо определить структуру данных, которая будет подаваться на вход алгоритма и приниматься на выходе.
В данной диссертационной работе для упрощения процесса генерации стандартизированных описаний алгоритма предлагается использовать следующие допущения: 1. В качестве функции оценки ifKF) использовать скалярные математические функции, например функцию Экли, Растригина, Швефеля и др. Данные функции широко применяются в международном сообществе для оценки качества получаемых оптимизационных механизмов. 2. В качестве поискового механизма для получения новых алгоритмов оптимизации применять генетический алгоритм с модифицированными генетическими операторами. Выбор генетического алгоритма обусловлен тем, что стандартизированное описание алгоритмов оптимизации легко записать в виде хромосомы; количество АПП в искомом алгоритме не превышает 10-15 элементов, что делает вероятность нахождения глобального оптимума высокой; временная сложность генетических алгоритмов невысока для малого числа входных данных; в результате работы алгоритма получается множество альтернативных решений, что дает возможность ЛПР выбрать лучший с его точки зрения, алгоритм.
3. Ввиду п.1 вид решений VIEW будет представлен в виде бинарной или векторной хромосомы (в зависимости от количества аргументов функции Для обеспечения работоспособности модуля генерации новых решений автором построены новые механизмы кодирования и декодирования стандартизированного представления алгоритмов оптимизации. Они позволяют представлять стандартные описания в виде альтернативных решений (хромосом). Разрабатываемая структура кодирования или декодирования должна соответствовать следующим требованиям [33-36]:
Скорость кодирования и последующего декодирования. Временная сложность алгоритмов кодирования / декодирования не должна превышать п log (п). Данный факт обусловлен тем, что генетические алгоритмы работают с большим набором альтернативных решений, каждое из которых должно быть закодировано и декодировано как минимум один раз целью его оценки.
Целостность данных. Алгоритмы кодирования и декодирования должны быть реализованы таким образом, чтобы после последовательно применения методов кодирования и декодирования исходное решение должно быть идентично результирующему.
Простота кодированного представления. СПАО должно быть закодировано в таком виде, чтобы легко было автоматически вносить случайные изменения (оператор мутации) и объединять два СПАО в один (оператор скрещивания).
Для того чтобы создать эффективный механизм кодирования и декодирования СПАО в диссертационной работе предлагается использовать элементы теории генетического программирования (ГП) [33-35]. Традиционно, любой алгоритм легко представить в виде дерева. В древовидном кодировании каждый узел дерева содержит функцию, а каждый лист — операнд. Выражение, представленное в виде дерева может быть легко рекурсивно посчитано [36-42].
Применительно к решаемой задаче узлы дерева интерпретируются как связи между АПП, а листья как сами АПП. Для уменьшения количества кодируемой информации и упрощения работы генетических операторов автором предлагается использовать двухуровневый механизм кодирования [36]. На первом уровне выполняется процедура упрощения, на второй кодирование упрощенного СПАО.
Процедура упрощения. Стандарт XML-описания обязывает применять дополнительные сущности для структурирования СПАО. Такие структуры как algorithm, start, end, flow и subflow обязательны для XML документа, но имеют избыточность при работе алгоритма генерации СПАО. Поэтому в данной работе предлагается удалить избыточные данные при кодировании. Рассмотрим пример, приведенный в таблице 2.1. После упрощения описание примет вид представленный в таблице 2.3.
На рисунке 2.5 вершина S - указывает на отношения между алгоритмами. Введем два типа отношений S - последовательный, Р -параллельный. Также отметим, что отношения не являются коммутативными, а значит порядок операндов имеет значение. Относительно примера, изображенного на рисунке 2.5 справедливо утверждение, что результат работы beeAlgoritm является исходными данными для genetic Algorithm.
В качестве структуры данных в хромосоме предлагается использовать обратную польскую нотацию. Обратная польская нотация (ОПН) — форма записи выражений, в которой операнды расположены перед знаками операторов. Под операндами автор понимает АПП, а под операторами -отношения между АПП. СПАО примет вид изображенный на рисунке 2.6.
Разработка механизма кодирования и декодирования для решения задачи размещения фрагментов СБИС
На начальном шаге вводятся управляющие параметрами. Для генетического алгоритма такими параметрами являются количество итераций Т (Т 0), вероятность кроссинговера Per ( 0 Per 1), вероятность мутации Pmut (0 Pmut 1).
На следующем этапе обнуляется счетчик итераций и генерируется начальная популяция [50-55].
После этого выполняется оператор кроссинговера. Выполнения данного процесса для всей популяции состоит из следующих шагов: обнуление счетчика выполненных операторов кроссинговера, далее выбор пары хромосом для скрещивания, непосредственно скрещивание и проверка условия остановки выполнения оператора кроссинговера. Выбор хромосом для скрещивания является одной из ключевой операций, так как от данного выбора зависит качество новых решений. В данной работе предлагается использовать вероятностный метод выбора хромосом (селекции) на основе колеса рулетки. Данный механизм широко известен и позволяет выбирать с высокой долей вероятности наиболее эффективные решения и с более низкой вероятностью менее эффективные. Это позволяет снизить вероятность попадания алгоритма в локальный экстремум за счет «разбавления» генотипа популяции и обеспечить сходимость алгоритма за счет использования большего количества решений, приближенных к глобальному оптимуму. Управляющий параметр «вероятность кроссинговера» позволяет управлять количеством нового генетического материала, что обеспечивает контроль над скоростью сходимости алгоритма. Непосредственно процедура скрещивания описана ранее и заключается в передаче одному потомку от первого родителя только генов операторов, а от другого родителя только генов операндов. Второй потомок получает, наоборот, от первого родителя гены операнды, а от второго - оператора. После проведения ряда операции кроссинговера полученные новые квазиоптимальные (в общем случае) решения добавляются в исходную популяцию [48,49]. Инициируется процесс выполнения оператора мутации.
Процесс выполнения оператора мутации аналогичен механизму выполнения оператора кроссинговера. Из всей популяции выбирается хромосома на основе колеса рулетки и применяется оператор мутации. Сам процесс получения нового решения с помощью оператора мутации основан на парных перестановках. Выбирается произвольно ген, если значение гена больше 0 (ген операнд), то произвольно выбирается другой ген операнд и производится парная перестановка. Если же значение начального гена меньше 0 (ген оператор), то случайно выбирается другой ген оператор и выполняется парная перестановка. Данные механизмы изображены на рисунке 3.10 и 3.11. После того, как были выполнены все генетические операторы, применяется оператор отбора. Данный оператор необходим для сокращения размера текущей популяции до начальных размеров, путем выбора эффективных квазиоптимальных решений в новую популяцию. Предлагается использовать отбор на основе колеса рулетки, как наиболее эффективного вероятностного метода отбора, который позволяется добавлять в результирующую популяцию хромосомы пропорционально значению её целевой функции. Процесс продолжается итерационно до тех пор пока t Т, т.е. число итераций достигнет заданного значения.
Основная идея алгоритма муравьиной колонии заключается в умении муравьев находить кратчайшее расстояние от источника пищи к муравейнику без использования внешней информации. Данная способность обуславливается выделением особого фермента (феромона) во время их движения [83-86].
Каждый муравей следует некоторым указателям (маркерам), в качестве которых выступает фермент. С течением времени фермент улетучивается и, следовательно, меньшее его количество располагается на менее популярном маршруте [84].
Алгоритм муравьиной колонии - это процедура дискретной оптимизации, но, при этом, параметры целевой функции изменяются непрерывно. Переход от непрерывной задачи оптимизации к дискретной производится посредством создания полного ориентированного графа, в котором количество вершин определяется точностью нахождения значений параметров. Каждой вершине принадлежит дуга с равномерно распределенными значениями нормированных параметров целевых функций входных параметров. Каждой вершине графа ставится в соответствие муравей. Цель муравья - посетить столько вершин графа, сколькими параметрами задается целевая функция. Метки дуг, по которым прошел муравей, являются найденным решением [86]. Количество фермента, оставляемого на дугах, прямо пропорционально качеству решения. Для решения задачи размещения фрагментов СБИС предлагается новый подход к использованию алгоритма оптимизации муравьиной колонией. На начальных шагах инициализируется начальная популяция, и вводятся управляющие параметры: количество итераций Т, количество агентов (муравьев), размер популяции N. Далее для каждого решения рассчитывается целевая функция и строится полный граф переходов со взвешенными вершинами между элементами решений (генов) [86-93]. Вес всех ребер принимается равным 1. Положительный вес интерпретируется как номер фрагмента СБИС, отрицательный вес, как оператор. Например, для альтернативного закодированного решения 1,2,-1,6,3,-1,-2,4,-2,5,-1 полный граф [86-90] переходов будет выглядеть как указанно на рисунке 3.13
Теоретические оценки временных и пространственных характеристик гибридного алгоритма размещения
Целью исследования подсистемы биоинспирированного поиска, реализующей набор задач по созданию и исследованию многоуровневых алгоритмов оптимизации, является доказательство повышения эффективности разработанных с помощью подсистемы алгоритма, по сравнению с аналогичными алгоритмами. Это доказательство может быть получено следующим путем [106]: теоретическим путем, основанным на получении оценок временной (ВСА) и пространственной (ПСА) сложности алгоритмов; эмпирическим путем, основанным на сравнении результатов полученных экспериментально.
В диссертационной работе результатом проведенных серий вычислительных экспериментов стали собранные данные и их статистическая обработка.
Объектами исследований являются: разработанная подсистема бионического поиска; разработанный алгоритм размещения фрагментов СБИС; Результатами исследований подсистемы биоинспирированного поиска являются величины приращения затрат времени и памяти, связанные с выполнением процесса генерации новых гибридных архитектур по сравнению с ручным процессом проектирования и реализации, а так же с выполнением новых алгоритмов, разработанных с использованием представленной подсистемы по сравнению с реализованными на других языках программирования без использования подсистемы биоинспирированного поиска. Исследование управляющих параметров каждого биоинспирированного алгоритма, входящего в состав гибридной архитектуры размещения состоит в определении эффекта параметров (число итераций, размер популяции, специфичные для каждого алгоритма параметры) на качество полученных оптимальных и квазиоптимальных решений. Оценка приращения эффективности полученного нового гибридного алгоритма размещения состоит в определении ПСА и ВСА разработанного биоинспирированного алгоритма размещения и сравнении этих оценок с результатами, полученными другими алгоритмами.
Ввиду вышесказанного, сформулируем цели экспериментальных исследований в окончательном виде. В отношении подсистемы генерации новых гибридных поисковых процедур целями эксперимента являются: определение временной зависимости времени генерации новых гибридных поисковых процедур от количества атомарных поисковых процедур, входящих в состав искомого алгоритма оптимизации. Измерения будем производить в миллисекундах; определение зависимости количества оперативной памяти, требуемой для хранения данных во время выполнения алгоритма генерации новых гибридных поисковых процедур от количества атомарных поисковых процедур и значений управляющих параметров. Единица измерений - байт: минимальная адресуемая единица памяти;
В отношении полученного с использованием подсистемы бионического поиска алгоритма размещения фрагментов СБИС: определение временной зависимости работы нового гибридного алгоритма размещения от количества фрагментов схемы СБИС и числа цепей схемы. Измерения будем производить в миллисекундах; определение зависимости количества оперативной памяти, требуемой для хранения данных во время выполнения гибридного алгоритма размещения фрагментов СБИС от количества фрагментов схемы СБИС и числа цепей схемы. Единица измерений - байт;
Подсистема бионического поиска, а также сторонние алгоритма, выбранные для проведения сравнительных экспериментов разработаны на языке программирования Java версии 8. Все вычислительные эксперименты проводились на персональном компьютере, на базе двуядерного процессора Intel Core 15 с частотой ядра 2.7 ГГц, объем оперативной памяти 8 Гб.
Для гибридного алгоритма размещения схемы СБИС временная и пространственная сложности складывается из временных и пространственных сложностей входящих в состав гибридного алгоритма поисковых механизмов. В рамках данной работы к ним относятся бактериальный, пчелиный и эволюционный. Базовыми переменными для оценки сложности являются число элементов N, множества цепей М [107].
Рассмотрим пространственную сложность алгоритма решения задачи размещения фрагментов СБИС. Для хранения габаритов и координат фрагментов СБИС требуется 2 В N ячеек памяти; для хранения списка цепей требуется В N М ячеек памяти, где В - количество ячеек памяти, требуемое вычислительной системе для хранение целого числа. В современных вычислительных системах это число равно 8.
Для хранения одного альтернативного решения требуется В (2 N - 1) ячеек памяти, а для хранения всего набора закодированных решений, входящих в состав популяцию, требуется выделить В (2 N - 1) \Pt\ ячеек памяти, где -\РІ\ - размер популяции каждого биоинспирированного алгоритма, входящего в состав гибридного поискового механизма. Для временного хранения новых альтернативных решений во время выполнения очередной итерации потребуется:
Временная сложность алгоритма (ВСА) [Ошибка! Источник ссылки не найден.]- это зависимость времени работы алгоритма от объема входных данных решаемой задачи. В данной диссертационной работе она складывается из следующих составляющих: сложностей составляющих гибридный алгоритм биоинспирированных алгоритмов, сложности функций кодирования и декодирования, сложности функции оценки.
Временная сложность алгоритма, основанного на поведении колонии пчел оценивается как 0(]РЬ\ Аъ Ib), где Д- размер популяции пчелиного алгоритма, Аь - количество агентов-фуражиров, 1ъ - количество итераций. Для бактериального алгоритма размещения фрагментов СБИС временная сложность оценивается как 0(]РЬак\ Ibak Г), где \Ръак\ - размер популяции бактериального алгоритма, Т - количество шагов хемотаксиса; Т є [1, Tmax], Tmax - конечное целое число. Ibak - количество итераций. Для эволюционного алгоритма временная сложность будет зависеть от следующих параметров: Ое = 0(\Ре\ 1е Рт) + От, где \Ре\ - размер популяции эволюционного алгоритма, Рт - вероятность выполнения оператора мутации; Рт є (0,1), Іе -количество итераций, От - временная сложность оператора мутации;
Временная сложность механизма инициализации популяции для всех алгоритмов пропорциональна 0((2iV — 1) Pt). ВСА функции оценки решений (вычисления ЦФ) пропорциональна 0(N М).
Вычислительная сложность алгоритма кодирования решений 0(N Р{), а алгоритма декодирования - пропорциональна функции 0((3N — 1) Р;), за счет двойного «прогона» каждого альтернативного решения.
Ввиду выше сказанного временная сложность последовательного выполнения группы алгоритмов: бактериальный, пчелиный, эволюционный для одного потока пропорциональна следующей сложности:
Под планированием вычислительного эксперимента обычно понимается процесс подготовки таких тестовых данных, при которых возможно отследить тенденции изменения исследуемый величин от входных данных. Экспериментальные исследования, в общем, планируются следующим образом [108].
Проведение серии экспериментов при статичных значениях управляющих параметров, для определения временных и пространственных затрат в зависимости от количества входных данных. Сводная таблица Поиск решения на наборе тестов с помощью разработанного гибридного алгоритмы для определение качества решения.