Авторефераты по всем темам  >>  Авторефераты по техническим специальностям  

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

       

Ерошенко Илья Николаевич

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

АЛГОРИТМОВ ПЛАНИРОВАНИЯ СБИС

05.13.12 - системы автоматизации проектирования

(вычислительная техника и информатика)

АВТОРЕФЕРАТ

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

кандидата технических наук

Таганрог - 2012

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

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

        Курейчик Виктор Михайлович

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

       Карелин Владимир Петрович

       (Таганрогский институт управления

       и экономики, г. Таганрог)

       доктор технических наук, профессор

       Чернышев Юрий Олегович

       (Донской государственный

       технический университет,

       г. Ростов-на-Дону)

Ведущая организация:        Открытое акционерное общество

       Таганрогский научно-

       исследовательский институт связи,

       г. Таганрог

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

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

Автореферат разослан л10 октября 2012 г.

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

диссертационного совета Д 212.208.22,

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

АКТУАЛЬНОСТЬ РАБОТЫ

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

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

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

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

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

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

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

ЦЕЛЬ ДИССЕРТАЦИИ

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

Задачи, которые необходимо решить для достижения цели:

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

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

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

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

5. Разработка и исследование генетического алгоритма назначения напряжений для учета энергосбережения при планировании СБИС.

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

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

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

2. Модифицирован алгоритм коллективной альтернативной адаптации для поддержки негильотинного представления плана.

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

4. Разработан параллельный генетический алгоритм планирования СБИС с учетом энергопотребления.

ПОЛОЖЕНИЯ, ВЫНОСИМЫЕ НА ЗАЩИТУ

1. Генетический алгоритм планирования кристалла СБИС.

2. Модифицированный алгоритм коллективной альтернативной адаптации для негильотинного представления плана СБИС.

3. Меметический алгоритм планирования кристалла СБИС.

4. Генетический алгоритм назначения напряжений.

ПРАКТИЧЕСКАЯ ЗНАЧИМОСТЬ

Практическая значимость работы состоит в том, что основные теоретические положения доведены до конкретных методик и алгоритмов. Разработанные методы эволюционной адаптации на основе самообучения и генетического поиска являются мощным средством выхода из "локальных ям", приводящим к синтезу решений, близких к оптимальным. Алгоритм планирования кристалла СБИС методами эволюционной адаптации реализован в виде программы на языке C++ в среде разработки Microsoft Visual Studio 2010 для операционной системы Windows. Благодаря предложенным методам достигнуты улучшенные показатели объектов проектирования (площадь и энергопотребление).

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

Основные теоретические и практические результаты, полученные в диссертационной работе, использованы в ряде научно-исследовательских работ, проводимых в Южном федеральном университете: грант РФФИ № 11 - 01 - 00122 Разработка теории и принципов построения интеллектуальных гибридных нечетких генетических, эволюционных и адаптивных методов принятия решений при проектировании и оптимизации, грант РФФИ № 10 - 01 - 00115 Разработка теории и принципов построения интеллектуальных интегрированных подсистем в задачах проектирования и управления.

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

МЕТОДЫ ИССЛЕДОВАНИЯ

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

АПРОБАЦИЯ РАБОТЫ

Основные результаты диссертационной работы обсуждались и были одобрены на международных научно-технических конференциях Интеллектуальные САПР (г. Дивноморск, 2009-2011 гг.), международной конференции по мягким вычислениям и измерениям (г. Санкт-Петербург, 2010 г.) всероссийских научных конференциях Информационные технологии, системный анализ и управление (г. Таганрог, 2008-2010 гг.), всероссийских научных конференциях Технологии Microsoft в теории и практике программирования (г. Таганрог, 2008-2011 гг.), всероссийской научной конференции Техническая кибернетика, радиоэлектроника и системы управления (г. Таганрог, 2010 г.).

ПУБЛИКАЦИИ

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

ОБЪЕМ И СТРУКТУРА ДИССЕРТАЦИИ

Диссертация состоит из 156 страниц текста, содержит введение, 4 главы, заключение, список литературы из 106 наименований, 121 рисунок и 8 таблиц.

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

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

В первой главе содержится обзор состояния исследований в области планирования как одного из этапов конструкторского проектирования СБИС.

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

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

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

Кратко описаны представления плана СБИС. Принято разбивать все множество представлений на 2 класса: гильотинный и негильотинный. Преобразование гильотинного представления в план осуществляется быстро, за линейное относительно модулей время, но доля мертвой зоны может быть больше, чем у негильотинных представлений. У негильотинных представлений пространство поиска больше, чем у гильотинного представления, трансформация в план происходит медленней, оценка временной сложности часто достигает O(n2) относительно числа модулей n, но доля мертвой зоны меньше, чем у гильотинного представления.

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

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

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

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

При решении задачи планирования важно выбрать эффективное представление плана и алгоритм поиска в пространстве решений. Рассматривается негильотинное представление плана лобобщенная польская запись (ОПЗ). Если у обычной польской записи используются операторы горизонтального (H) и вертикального (V) разрезов, то для ОПЗ представлен угловой оператор @, который позволяет эффективно задействовать мертвую зону, планы получаются более компактными на 1Ц5% по сравнению с другими негильотинными представлениями (рис. 1). Трансформация ОПЗ в план происходит за линейное время. Поиск субоптимального плана с ОПЗ происходит до 5 раз быстрее, чем при использовании другого негильотинного представления, также основанного на бинарном дереве - B*-дереве.

Рис. 1. Использование углового оператора

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

Решение представляется набором хромосом S = {H1, H2, H3, H4}. Пусть n - число модулей. Хромосома H1 кодирует разметку модулей. H2 определяет структуру бинарного дерева. С помощью хромосомы Н3 задаются типы операторов (Н, V, @). Значением гена является 0, 1 или 2 (флаг 0 - Н-разрез, флаг 1 - V-разрез, флаг 2 - угловой оператор @). Хромосома H4 определяет ориентацию модулей. Если gi = 0, то высота прямоугольного модуля меньше либо равна ширине, при gi = 1 высота больше его ширины. Декодирование хромосом имеет оценку трудоемкости O(n), где n - число модулей. Пространственная сложность для одного решения имеет оценку O(n).

В данном генетическом алгоритме используются 4 оператора кроссинговера: одноточечный К1, равномерный К2, хромосомный K3 и специализированный К4. Кроссинговер K3 напоминает равномерный кроссинговер K2, но работает на уровне хромосом, а не генов. Специализированный кроссинговер K4 анализирует деревья Ti и Tj, декодированные из особей i и j. Выбирается лучшее (в плане критерия оптимизации) поддерево STbest среди двух декодированных деревьев. Обозначим родителя, имеющего лучшее поддерево, как P1, а другого родителя - P2. Поддерево STbest помещается в специальный пул. Затем в пул добавляются поддеревья из P2, которые не содержат модулей из выбранного поддерева. Множество модулей, не попавших в пул, помечаются как вырожденные поддеревья и добавляются в пул. Из пула циклически выбираются два поддерева (попарное сравнение), к ним применяются последовательно операторы H, V, @. Определяется лучший результат при слиянии двух поддеревьев на текущем этапе. Лучшая пара поддеревьев удаляется из пула, а вместо них добавляется только что созданное поддерево. Процесс повторяется до тех пор, пока не будет получено дерево, содержащее все модули.

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

Рассмотрена коллективная альтернативная адаптация, с помощью которой общая площадь кристалла снижается в несколько раз благодаря переориентации модулей при заданном негильотинном представлении плана ОПЗ. Ориентация модуля mi при его размещении в области задается параметром oi. , т.е. для mi возможны два способа (две ориентации) размещения. Если oi = 0, то высота прямоугольного модуля меньше либо равна ширине (альтернатива А1), при oi = 1 высота больше его ширины (альтернатива А2). Пространство решений составляют решения, отличающиеся друг от друга значениями элементов множества O, задающими ориентацию модулей. Пусть для множества модулей M задан первоначальный план, т.е. задана ОПЗ, ориентация модулей, сформированы выражения для определения высоты h0 и ширины w0 охватывающего прямоугольника R. Для оценки состояния объекта адаптации в среде используются 2 параметра <РIх,РIу>. РIх = 1, если размер wi модуля входит в состав выражения, определяющего ширину w0 охватывающего прямоугольника R; РIх = 0 - в противном случае. РIу = 1, если размер hi модуля mi, входит в состав выражения, определяющего высоту h0 прямоугольника R; РIу = 0 - в противном случае (рис. 2).

Рис. 2. План для ОПЗ = {a b H c @ d V}

Возможны четыре комбинации значений параметров <РIх, РIу>: <0, 0>, <0, 1>, <1, 0>, <1, 1>. Если  РIх = 1, то предпочтительней будет альтернатива А2, т.к. в выражение для w0 войдет меньшая величина. Если РIу = 1, то предпочтительней будет альтернатива А1, следовательно, в выражение для h0 войдет меньшая величина. Модули mi рассматриваются в качестве объектов адаптации с двумя альтернативными состояниями. На вход автомата адаптации с двумя группами состояний {С1i, C2i}, соответствующих двум альтернативам А1i и А2i, подаются сигналы поощрения (+) и наказания (Ц) в зависимости от состояния объекта адаптации в среде (рис. 3). Сигналы поощрения вырабатываются, если предпочтительная альтернатива совпадает с реализованной, в противном случае вырабатываются сигналы наказания. Число состояний в группе задается параметром Qi, называемым глубиной памяти.

Рис. 3. АА с двумя группами состояний

Работа алгоритма коллективной альтернативной адаптации на каждой итерации осуществляется за 4 такта: определение кортежей флагов <РIх, РIу>, выработка управляющих сигналов, переход в автоматах адаптации, реализация альтернатив (переориентация модулей).

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

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

Рис. 4. Псевдокод комбинированной адаптивной поисковой процедуры (меметического алгоритма)

Третья глава посвящена планированию СБИС с учетом энергосбережения.

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

Рис. 5. Пример двух островов напряжения

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

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

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

Рис. 6. Алгоритм планирования СБИС с учетом энергопотребления

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

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

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

Рис. 7. Топология кольцо для параллельного ГА

Четвертая глава посвящена экспериментальным исследованиям с помощью разработанного программного обеспечения.

Дается краткий анализ библиотек для программной реализации метаэвристик, показаны преимущества библиотеки GAlib: язык C++ (реализация на C++ обладает большим быстродействием, чем реализации на C# и Java), простота архитектуры. Так как ГА назначения напряжений достаточно близок к стандартным ГА (в отличие от МА планирования СБИС), то для сокращения времени разработки он был реализован с использованием библиотеки GAlib.

Представлена архитектура библиотеки GAlib. Отмечается невозможность непосредственной организации островной модели ГА с использованием вычислительных потоков ОС Windows, поэтому в качестве надстройки необходимо использовать специальные средства для распараллеливания вычислений.

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

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

Планировщик принимает на вход файлы формата txt, в качестве выходных файлов создаются файлы формата bbb (как у некоторых других планировщиков). Возможно использование двух режимов планирования: классическое (учитывается только площадь) и с учетом энергопотребления. Для назначения напряжений используется генетический алгоритм, для размещения модулей - альтернативная адаптация, генетический алгоритм или меметический алгоритм. Настройки алгоритмов хранятся в XML файлах проекта *.fpp.

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

Представлены результаты экспериментов, выполненных на ЭВМ с процессором Intel Core 2 Duo T6600 2200 МГц, 4 Гб ОЗУ под управлением ОС Windows 7. Большая часть экспериментов проводилась для гильотинного представления плана (польской записи) и для негильотинного представления плана - обобщенной польской записи. Для тестирования использовались бенчмарки MCNC (apte, xerox, hp, ami33, ami49), у которых количество элементов варьировалось от 9 до 49.

Рис. 8. Внешний вид планировщика СБИС

Для сравнения ГА и АА им был предоставлен одинаковый промежуток времени (500 мс), использовался бенчмарк MCNC xerox. После серии из 10 независимых тестов средняя величина мертвой зоны для ГА составила 7,17% для ОПЗ и 9,31% для ПЗ, для АА мертвая зона 9,51% в случае с ОПЗ, 12,5% при использовании ПЗ. Более высокие показатели у ГА объясняются тем, что он является методом глобального поиска, содержит специализированный кроссинговер. Целесообразно совместное использование ГА и АА для локальной оптимизации перспективных особей в виде МА.

Для экспериментального определения временной сложности МА и ГА назначения напряжений при фиксированных параметрах алгоритмов на вход подавалось разное количество модулей. Эксперименты подтвердили линейную оценку временной сложности данных алгоритмов в случае использования ПЗ и ОПЗ. Планирование с ОПЗ занимает больше времени (приблизительно на 30%), чем планирование с ПЗ, но если в рамках МА предоставить одинаковый временной лимит для ПЗ и ОПЗ, то у плана, полученного из ПЗ, как правило, выше доля мертвой зоны (на 2%, а то и более). При выполнении параллельного ГА назначения напряжений может быть использовано несколько потоков.

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

С ростом числа островов прирост скорости многопоточной реализации ГА относительно однопоточной также растет, т.е. использование библиотеки PPL становится особенно актуальным при большом числе островов. Например, для 2 островов использование PPL для метаэвристической библиотеки GAlib позволяет ускорить вычисления на 20%, а для 8 островов ускорение вычислений достигает величины около 35%, при этом в экспериментах участвовал процессор T6600 всего с двумя ядрами.

При планировании ГА+МА энергосбережение достигает в среднем величины 46,3%, что соизмеримо с результатами аналога. Улучшение по площади по сравнению с аналогом (в среднем) - 13,6%.

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

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

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

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

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

2. Существующий генетический алгоритм планирования СБИС был усовершенствован благодаря использованию обобщенной польской записи, наличию различных видов кроссинговера и механизма регулирования частоты их использования. Всего за 0,5 с ГА позволяет снизить уровень мертвой зоны до уровня 7% для бенчмарка MCNC xerox.

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

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

5. Меметический алгоритм планирования был распараллелен для получения более надежных решений, при этом для островной модели использовалась топология кольцо. Разработанный меметический алгоритм может работать автономно, а может использоваться в рамках современного планирования с учетом энергосбережения благодаря специальной надстройке. Данная надстройка выполнена в виде параллельного генетического алгоритма назначения напряжений. Многопоточная реализация позволяет ускорить вычисления на 30Ц35% по сравнению с однопоточной.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ:

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

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

1. Ерошенко И.Н. Разработка генетического алгоритма кластерного планирования СБИС // Известия ЮФУ. Технические науки. Т. 108, №7. Изд-во ТТИ ЮФУ, 2010. - С. 54 Ц60.
2. Ерошенко И.Н. Меметический алгоритм планирования СБИС. // Известия ЮФУ. Технические науки. Т. 113, №12. Изд-во ТТИ ЮФУ, 2010 - С. 55Ц62.
3. Ерошенко И.Н. Обзор современных моделей эволюционных вычислений для решения задачи планирования СБИС. // Известия ЮФУ. Технические науки. Т. 120, №7. Изд-во ТТИ ЮФУ, 2011 - С. 45Ц51.

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

4. Ерошенко И.Н., Курейчик В.М., Курейчик В.В. Программа планирования СБИС на основе альтернативной адаптации с использованием обобщенной польской записи (ААОПЗ). Свидетельство о государственной регистрации программы для ЭВМ № 2011611036, 2011.
5. Ерошенко И.Н., Курейчик В.М., Курейчик В.В. Программа планирования СБИС на основе мультихромосомного генетического алгоритма с использованием обобщенной польской записи (МГАОПЗ). Свидетельство о государственной регистрации программы для ЭВМ № 2011613132, 2011.
6. Ерошенко И.Н., Курейчик В.М., Курейчик В.В. Программа планирования СБИС на основе островного меметического алгоритма с использованием обобщенной польской записи (ОМАПС). № 2012615642, 2012.

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

7. Ерошенко И.Н. Разработка бионических методов планирования СБИС // VI Всероссийская научная конференция молодых ученых, аспирантов и студентов: Информационные технологии, системный анализ и управление. Таганрог: Изд-во ТТИ ЮФУ, 2008. - С. 152Ц153.
8. Ерошенко И.Н. Разработка визуализатора плана СБИС в среде Microsoft Visual Studio 2008 // Технологии Microsoft в теории и практике программирования: труды VI-ой Всероссийской конференции студентов, аспирантов и молодых ученых. Таганрог: Изд-во ТТИ ЮФУ, 2009. - С. 9Ц11.
9. Ерошенко И.Н. Применение альтернативной адаптации для планирования СБИС на основе обобщенной польской записи. Труды Конгресса по интеллектуальным системам и информационным технологиям УAIS-ITТ09Ф. - М: Физматлит, 2009. Т.3. - С. 77Ц81.
10. Ерошенко И.Н. Современные тенденции в планировании СБИС // VII Всероссийская научная конференция молодых ученых, аспирантов и студентов: Информационные технологии, системный анализ и управление. Таганрог: Изд-во ТТИ ЮФУ, 2009. - С. 305Ц310.
11. Ерошенко И.Н. Обзор состояния и перспективы планирования кристалла СБИС // Перспективные информационные технологии и интеллектуальные системы. №39/40(3/4)/2009. - С. 74Ц88.
12. Ерошенко И.Н. Применение библиотеки PPL в алгоритмах генетического поиска // Технологии Microsoft в теории и практике программирования: труды VII-ой Всероссийской конференции студентов, аспирантов и молодых ученых. Таганрог: Изд-во ТТИ ЮФУ, 2010. - С. 23Ц26.
13. Ерошенко И.Н. Меметические алгоритмы как эффективный метод оптимизации // XIII Международная конференция по мягким вычислениям и измерениям. Санкт-Петербургский государственный электротехнический университет ЛЭТИ им. В.И. Ульянова (Ленина), 2010. т.1. СПб. Изд-во СПбГЭТУ "ЛЭТИ". 2010. - С. 126Ц129.
14. Ерошенко И.Н. Использование природных вычислений в задачах конструкторского проектирования СБИС // Информатика, вычислительная техника и инженерное образование. №1. Изд-во ТТИ ЮФУ, 2010. - С. 19Ц28.
15. Ерошенко И.Н. Эволюционные вычисления при решении задач конструкторского проектирования СБИС // Труды Конгресса по интеллектуальным системам и информационным технологиям УAIS-ITТ10Ф.2010. Т.3. - С. 3Ц10.
16. Ерошенко И.Н. Платформы для эволюционных вычислений: проблемы и перспективы развития // Труды X Всероссийской научной конференции студентов и аспирантов         Техническая кибернетика, радиоэлектроника и системы управления, 2010. - С. 123Ц124.
17. Ерошенко И.Н. Роль гибридизации метаэвристик в задачах оптимизации // VIII Всероссийская научная конференция молодых ученых, аспирантов и студентов: Информационные технологии, системный анализ и управление. Таганрог: Изд-во ТТИ ЮФУ, 2010. - С. 370Ц376.
18. Ерошенко И.Н. Моделирование плана СБИС с использованием бинарных деревьев // Труды Российской школы-семинара аспирантов, студентов и молодых ученых Информатика,  моделирование,  автоматизация  проектирования. 2010. - С. 214-219.
19. Ерошенко И.Н. Разработка планировщика СБИС с использованием библиотеки параллельных шаблонов // Технологии Microsoft в теории и практике программирования: труды VIII-ой Всероссийской конференции студентов, аспирантов и молодых ученых. Таганрог: Изд-во ТТИ ЮФУ, 2011. - С. 5Ц8.
20. Ерошенко И.Н. Методы адаптации генетических алгоритмов к задаче планирования СБИС // Труды конгресса по интеллектуальным системам и информационным технологиям IS-ITТ11. М: Физматлит, 2011. Т.3. - С. 138Ц145.
21. Ерошенко И.Н. Применение обучающихся автоматов в задаче упаковки блоков. // Сборник научных трудов третьей Всероссийской школы-семинара аспирантов, студентов и молодых ученых информатика, моделирование, автоматизация проектирования - Ульяновск: УГТУ, 2011. - С. 171Ц176.

ичный вклад автора в работе [4] состоит во внедрении негильотинного представления плана ОПЗ в алгоритм коллективной альтернативной адаптации, программной реализации планировщика ААОПЗ, в работе [5] - в модификации мультихромосомного представления плана для поддержки ОПЗ, программной реализации планировщика МГАОПЗ, в работе [6] - в разработке специализированного кроссинговера, механизма адаптации вероятностей выбора различных операторов кроссинговера, островной модели параллельного ГА с динамическим периодом миграции особей, программной реализации планировщика ОМАПС.

Соискатель Ерошенко И.Н.

Авторефераты по всем темам  >>  Авторефераты по техническим специальностям