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

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

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

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

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

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

Таганрог - 2012

005048620

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

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

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

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

Карелин Владимир Петрович (Таганрогский институт управления и экономики, г. Таганрог)

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

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

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

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

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

Автореферат разосла

Ученый секретар диссертационног) доктор техничес

Целых А.Н.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПУБЛИКАЦИИ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение представляется набором хромосом Б = {Н К Н2, НЗ, Н4}. Пусть п -число модулей. Хромосома Н1 кодирует разметку модулей. Н2 определяет структуру бинарного дерева. С помощью хромосомы НЗ задаются типы операторов (Н, V, @). Значением гена является 0, 1 или 2 (флаг 0 - Н-разрез, флаг 1 - У-разрез, флаг 2 -угловой оператор @). Хромосома Н4 определяет ориентацию модулей. Если g¡ = 0, то высота прямоугольного модуля меньше либо равна ширине, при g¡ = 1 высота больше его ширины. Декодирование хромосом имеет оценку трудоемкости О(п), где п - число модулей. Пространственная сложность для одного решения имеет оценку О(п).

В данном генетическом алгоритме используются 4 оператора кроссинговера: одноточечный К1, равномерный К2, хромосомный КЗ и специализированный К4. Кроссинговер КЗ напоминает равномерный кроссинговер К2, но работает на уровне хромосом, а не генов. Специализированный кроссинговер К4 анализирует деревья Т; и "Г|, декодированные из особей I и Выбирается лучшее (в плане критерия оптимизации) поддерево ЗТЬе51 среди двух декодированных деревьев. Обозначим родителя, имеющего лучшее поддерево, как Р1, а другого родителя - Р2. Поддерево

ЗТЬе51 помещается в специальный пул. Затем в пул добавляются поддеревья из Р2, которые не содержат модулей из выбранного поддерева. Множество модулей, не попавших в пул, помечаются как вырожденные поддеревья и добавляются в пул. Из пула циклически выбираются два поддерева (попарное сравнение), к ним применяются последовательно операторы Н, V, @. Определяется лучший результат при слиянии двух поддеревьев на текущем этапе. Лучшая пара поддеревьев удаляется из пула, а вместо них добавляется только что созданное поддерево. Процесс повторяется до тех пор, пока не будет получено дерево, содержащее все модули.

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

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

т( при его размещении в области задается параметром О;. о/ е {0,1} > т-е- Для т:

возможны два способа (две ориентации) размещения. Если о; = 0, то высота прямоугольного модуля меньше либо равна ширине (альтернатива А1), при 0[ = 1 высота больше его ширины (альтернатива А2). Пространство решений составляют решения, отличающиеся друг от друга значениями элементов множества О, задающими ориентацию модулей. Пусть для множества модулей М задан первоначальный план, т.е. задана ОПЗ, ориентация модулей, сформированы выражения для определения высоты Ь0 и ширины \у0 охватывающего прямоугольника Я. Для оценки состояния объекта адаптации в среде используются 2 параметра <Р1х,Р1у>. Р'х = 1, если размер модуля входит в состав выражения, определяющего ширину \¥0 охватывающего прямоугольника Я; Р'х = 0 - в противном случае. Ру = 1, если размер Ь; модуля т„ входит в состав выражения, определяющего высоту И0 прямоугольника Я; Р'у = 0 - в противном случае (рис. 2).

К

ь

с £3

а

ОПЗ: а Ь Н с @ <3 V

\\г = V.; + V,' +

0 Ъ с й

Ь = 1т + Ь 0 а Ь

Рис. 2. План для ОПЗ = {а Ь Н с @ с1 V}

Возможны четыре комбинации значений параметров <Р'Х, Р'у>: 0>, <0, 1>, <1, 0>, <1, 1>. Если Рх = 1, то предпочтительней будет альтернатива А2, т.к. в выражение для войдет меньшая величина. Если Р'у = 1, то предпочтительней будет альтернатива А1, следовательно, в выражение для Ь0 войдет меньшая величина.

Модули т, рассматриваются в качестве объектов адаптации с двумя альтернативными состояниями. На вход автомата адаптации с двумя группами состояний {С1!, С2;}, соответствующих двум альтернативам А'| и А2,, подаются сигналы поощрения (+) и наказания (-) в зависимости от состояния объекта адаптации в среде (рис. 3). Сигналы поощрения вырабатываются, если предпочтительная альтернатива совпадает с реализованной, в противном случае вырабатываются сигналы наказания. Число состояний в группе задается параметром называемым глубиной памяти.

А1. А2.

(+) (+) (+) '(+)

(-) В (-) В

С1. С2.

1 ■

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

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

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

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

Меметический Алгоритм {

задача := ИСХОДНЫЕ ДАННЫЕ: нач_попул := ФОРМ (задача); k := Т:

ПОКА к > О {

тек_попул := ГЕНЕТИКА (нач_попул): ад_попул := А_СЕЛЕКЦИЯ (тек_попул): ад_попул := АДАПТАЦИЯ (ад_попул): тек_попул := ОБЪЕДИНИТЬ (т е к_п о пуп, ад_п о пул); нач_попул := СЕЛЕКЦИЯ (тек_попул): к :=к- 1:

}

}

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

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

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

Уровень напряжения на чипе 1.4 В Остров напряжения А(1.3 В}: т4. т5. тб Остров напряжения В (1.2 В}:. т7. т8. тЭ

т1{1.2,1.4}; т2{ 1.1, 1.2,1.4}; тЗ{1.0, 1.3.1.4} т4{1.3.1.4}: т5{1.1. 1.3}: т6{1.2, 1.3. 1.4} т7{1 1. 1.2}: т8{1.1. 1.2, 1.3}: т9{1.0. 1.2. 1.4}

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

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

m 1 Е т 7 т8

m2 тЗ ъ- т9

m4 /■ ^ m5 тб

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

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

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

Алгоритм

{

Дана информация о геометрических параметрах модулей и ш энергопотр е блении.

Применение ГА для создания начальной популяции;

Пока не выполнены условия останова: {

Для каждой хромосомы б популяции: \

Для каждого острова напряжения, закодированного в хромосоме: {

Применение МА для планирования в рамках текущего острова: >

Применение МА для планирования на уровне кристалла; >

Оценивание приспособленности популяции; Применение операторов селекции.

кроссинговера и мутации для создания новых хромосом; }

}

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

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

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

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

^ Конечное решение

Остров 1-► Остров 2

N Остров 3 ~

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

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

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

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

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

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

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

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

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

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

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

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

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

величины около 35%, при этом в экспериментах участвовал процессор Т6600 всего с двумя ядрами.

При планировании ГА+МА энергосбережение достигает в среднем величины 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%). К достоинствам двухуровневой архитектуры планирования с учетом энергопотребления

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

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

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

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

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. Т.З. - С. 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-10.

16. Ерошенко И.Н. Платформы для эволюционных вычислений: проблемы и перспективы развития // Труды X Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», 2010.-С. 123-124.

17. Ерошенко И.Н. Роль гибридизации метаэвристик в задачах оптимизации // VIII Всероссийская научная конференция молодых ученых, аспирантов и студентов: Информационные технологии, системный анализ и управление. Таганрог: Изд-во ТТИ ЮФУ, 2010. - С. 370-376.

18. Ерошенко И.Н. Моделирование плана СБИС с использованием бинарных деревьев // Труды Российской школы-семинара аспирантов, студентов и молодых ученых «Информатика, моделирование, автоматизация проектирования». 2010. - С. 214-219.

19. Ерошенко И.Н. Разработка планировщика СБИС с использованием библиотеки параллельных шаблонов // Технологии Microsoft в теории и практике программирования: труды VIII-ой Всероссийской конференции студентов, аспирантов и молодых ученых. Таганрог: Изд-во ТТИ ЮФУ, 2011.-С. 5-8.

20. Ерошенко И.Н. Методы адаптации генетических алгоритмов к задаче планирования СБИС // Труды конгресса по интеллектуальным системам и информационным технологиям «IS-IT'll». М: Физматлит, 2011. Т.З. - С. 138-145.

21. Ерошенко И.Н. Применение обучающихся автоматов в задаче упаковки блоков. // Сборник научных трудов третьей Всероссийской школы-семинара аспирантов, студентов и молодых ученых информатика, моделирование, автоматизация проектирования - Ульяновск: УлГТУ, 2011. - С. 171-176.

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

Соискатель

Ерошенко И.Н.

Введение.

1 Анализ и состояние проблемы планирования СБИС.

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

1.2 Представление модулей при планировании СБИС.

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

1.4 Классификация и анализ представлений плана СБИС.

1.5 Анализ существующих методов и подходов к задаче планирования СБИС.

1.6 Выводы.

2 Планирование СБИС на основе композиционного подхода.

2.1 Постановка задачи.

2.2 Представление плана «обобщенная польская запись».

2.3 Поисковая адаптация в задачах САПР.

2.4 Разработка архитектуры генетического поиска для решения задачи планирования СБИС.

2.5 Организация поисковой процедуры на основе коллективной альтернативной адаптации для решения задачи планирования СБИС.

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

2.7 Выводы.

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

3.1 Проблема энергопотребления СБИС.

3.2 Основные подходы к решению проблемы энергопотребления при мультивольтажном проектировании СБИС.

3.3 Постановка задачи.

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

3.5 Двухуровневое распараллеливание алгоритма планирования СБИС с учетом энергосбережения.

3.6 Выводы.

4 Программная реализация и экспериментальные исследования разработанных алгоритмов планирования СБИС.

4.1 Обзор библиотек метаэвристик для эволюционных вычислений.

4.2 Архитектура библиотеки GAlib.

4.3 Многопоточная реализация алгоритма назначения напряжений.

4.4 Описание программного продукта.

4.5 Эксперименты.

4.6 Выводы.

Общая характеристика диссертационного исследования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Объектом исследования является планирование СБИС.

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

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

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

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

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

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

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

Основные положения, выносимые на защиту:

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

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

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

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

Практическая ценность работы состоит в том, что основные теоретические положения доведены до конкретных методик и алгоритмов. Разработанные методы эволюционной адаптации на основе самообучения и генетического поиска являются мощным средством выхода из "локальных ям", приводящим к синтезу решений, близких к оптимальным. Алгоритм планирования кристалла СБИС методами эволюционной адаптации реализован в виде программы на языке С++ в среде разработке 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 таблиц.

4.6 Выводы

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

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

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

Заключение

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

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

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

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

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

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

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

1. Гулякович Г.Н. и др. Перспективы и проблемы полупроводниковой наиоэлектроники // Электронный научный журнал «Инженерный Вестник Дона», №2. 2012.

2. Лебедев В.Б. Разработка и исследование методов планирования кристалла СБИС на основе эволюционной адаптации: Дис. канд. тех. наук. Таганрог, 2003.- 145 с.

3. Kahng А.В. Classical floorplanning harmful? // Proceedings of the 2000 International Symposium on Physical Design: San Diego, CA, 2000. pp. 207-213.

4. Ерошенко И.Н. Современные тенденции в планировании СБИС // VII Всероссийская научная конференция молодых ученых, аспирантов и студентов: Информационные технологии, системный анализ и управление. Таганрог: Изд-во ТТИ ЮФУ, 2009. С. 305-310.

5. Ерошенко И.Н. Обзор состояния и перспективы планирования кристалла СБИС // Перспективные информационные технологии и интеллектуальные системы. №39/40(3/4)/2009. С. 74-88.

6. Subbaraj. P. et al. Multi-objective Optimization in VLSI Floorplanning // Control, Computation and Information Systems, Communications in Computer and Information Science, 2011, Volume 140, 1. pp. 65-72.

7. Shanavas I.H., Gnanamurthy R.K. Wirelength Minimization in Partitioning and Floorplanning Using Evolutionary Algorithms // VLSI Design Vol. 2011. 2011.

8. Ma Q. et al. MSV-Driven Floorplanning // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume: 30 Issue: 8. 2011. pp. 1152 -1162.

9. Haghdad K. et al. Floorplanning for low power 1С design considering temperature variations // Microelectronics Journal Volume 42, Issue 1, January 2011. pp. 89-95.

10. Alpert C. et al. Handbook of Algorithms for Physical Design Automation: Taylor & Francis Group, LLC, 2009. p. 1024.

11. Young F.Y. et al. Placement Constraints in Floorplan Design. // IEEE Transactions on Very Large Scale Integration Systems, 2004. pp. 735-745.

12. Young F.Y. et al. On extending slicing floorplans to handle L/T-shaped blocks and abutment constraints // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2001. pp. 800-807.

13. Young F.Y. et al. Slicing floorplans with boundary constraints // IEEE Transactions on Computer-Aided Design, 1999. pp. 1385-1389.

14. Wong D.F. and Liu C.L. A New Algorithm for Floorplan Design // Proc. DAC, 1986. -pp.101-107.

15. Sengupta D. et al. Sequence pair based voltage island floorplanning // IEEE International Green Computing Conference, 2011. pp. 1-6.

16. Nakatake S. et al. The channeled-BSG: a universal floorplan for simultaneous place/route with 1С applications // International Conference on Computer-Aided Design, 1998.-pp. 418-425.

17. Guo P.N. Floorplanning Using a Tree Representation // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 20, No. 2, FEBRUARY 2001.-pp. 281-289.

18. Chang Y.-C. B*-trees: A New Representation for Non-slicing Floorplans // proc. DAC, 2000.-pp. 458^163.

19. Wang R. et al. An Improved P-admissible Floorplan Representation Based on Corner Block List // Proceedings of the 2005 Asia and South Pacific Design Automation Conference. 2005. pp. 1115-1118.

20. Lin J.-M., Chang Y.-W. TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans // IEEE Transactions on Very Large Scale Integration (VLSI) Systems Volume 13 Issue 2, 2005. pp. 288-292.

21. Lin C.-T. et al. GPE: A New Representation for VLSI Floorplan Problem // IEEE International Conference on Computer Design (ICCD'02), 2002. pp. 42-44.

22. Ерошенко И.Н. Моделирование плана СБИС с использованием бинарных деревьев // Труды Российской школы-семинара аспирантов, студентов и молодых ученых «Информатика, моделирование, автоматизация проектирования». 2010. С. 214—219.

23. Lai M., and Wong D.F. Slicing Tree Is a Complete Floorplan Representation // In Proc. DATE, 2001. pp. 228-232.

24. Лебедев Б.К., Рябов O.B. Построения графа ограничения методом списка глубин для задачи сжатия // Известия ЮФУ. Технические науки. Таганрог: Изд-во ТТИ ЮФУ, 2008.№ 4(81). - С. 51-55.

25. Akers S.B., Geyer J.M. and D.L. Roberts. 1С Mask Layout with a Single Conductor Layer // Proceedings of 7th Design Automation Workshop, 1970. pp. 716.

26. Hsueh M.Y. and Pederson D.O. Computer-Aided Layout of LSI Circuit BuildingBlock // IEEE International Symposium on Circuits and Systems, 1979. pp. 474 -477.

27. Carpenter C.W. and Horowitz M. Generating Incremental VLSI Compaction Spacing Constraints // Proceedings of the 24th ACM/IEEE Design Automation Conference: IEEE Computer Society Press, 1987. pp. 291-297.

28. Sutanthavibul S. et al. An analytical approach to floorplan design and optimization // DAC '90 Proceedings of the 27th ACM/IEEE Design Automation Conference. 1990.-pp. 187-192.

29. Sherwani N. Algorithms for VLSI Physical Design Automation: Kluwer Academic Publisher 1999. p. 608.

30. Гармаш A.B. Решение задачи планирования СБИС на основе квантовых алгоритмов // Перспективные информационные технологии и интеллектуальные системы. 2004. №3. С.47-52.

31. Ерошенко И.Н. Использование природных вычислений в задачах конструкторского проектирования СБИС. // Информатика, вычислительная техника и инженерное образование. №1. Изд-во ТТИ ЮФУ, 2010. С. 19-28.

32. Курейчик В.М. и др. Поисковая адаптация: теория и практика. М.: Физматлит, 2006. — С. 272.

33. Ерошенко И.Н. Применение альтернативной адаптации для планирования СБИС на основе обобщенной польской записи // Труды Конгресса поинтеллектуальным системам и информационным технологиям "AIS-IT'09". -М: Физматлит, 2009. Т.З. С. 77-81.

34. Chen Т.-С. et al. Modern floorplanning based on B*-tree and fast simulated annealing // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006. pp. 637-650.

35. Fang J.-P. et al. A Parallel Simulated Annealing Approach for Floorplanning in VLSI // Proceedings of the 9th International Conference on Algorithms and Architectures for Parallel Processing. 2009. pp. 291-302.

36. Qi L. et al. Simulated annealing based thermal-aware floorplanning // International Conference on Electronics, Communications and Control (ICECC), 2011.-pp. 463-466.

37. Курейчик B.B., Курейчик B.M., Родзин С.И. Концепция эволюционных вычислений, инспирированных природными системами. // Известия Южного федерального университета. Технические науки. 2009. Т.93. №4. с. 16-24.

38. Курейчик В.М., Родзин С.И. Эволюционные алгоритмы: генетическое программирование (обзор) // Известия РАН. Теория и системы управления. -2002, № 1.-С. 127-137.

39. Ерошенко И.Н. Эволюционные вычисления при решении задач конструкторского проектирования СБИС // Труды Конгресса по интеллектуальным системам и информационным технологиям "AIS-IT'10". 2010. Т.З.-С. 3-10.

40. Ерошенко И.Н. Обзор современных моделей эволюционных вычислений для решения задачи планирования СБИС // Известия Южного федерального университета. Технические науки. 2010. Т. 120. № 7. С. 45-51.

41. Lin С.-Т. et al. An efficient genetic algorithm for slicing floorplan area optimization // Proceedings of the International Symposium on Circuits And Systems, 2002. pp. 879-882.

42. Hung W.-L. et al. Thermal-aware floorplanning using genetic algorithms // Sixth International Symposium on Quality of Electronic Design, 2005. pp. 634-639.

43. Chen J., Zhu W. A hybrid genetic algorithm for VLSI floorplanning // IEEE International Conference on Intelligent Computing and Intelligent Systems (ICIS), 2010.-pp. 128-132.

44. Kureichik V.M. et al. Hybrid evolutionary algorithm of planning VLSI // Proceedings of the 12th annual conference on Genetic and evolutionary computation 2010.-pp. 821-822.

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

46. Ерошенко И.Н. Разработка генетического алгоритма кластерного планирования СБИС // Известия Южного федерального университета. Технические науки 2010 №7(108) С. 54-60.

47. Moni D.J. et al. VLSI Floor Planning relying on Differential Evolution Algorithm // ICGST International Journal on Artificial Intelligence and Machine Learning. Vol. 7. No 1.-2007.-pp. 62-67.

48. Лебедев О.Б. Планирование СБИС на основе метода муравьиной колонии // Известия Южного федерального университета. Технические науки. 2010. Т. 108. №7. - С.67-73.

49. Лебедев Б.К., Лебедев В.Б. Размещение на основе метода пчелиной колонии // Известия Южного федерального университета. Технические науки. 2010. Т. 113. № 12.-С. 12-19.

50. Chiang C.-W. Ant Colony Optimization for VLSI Floorplanning with Clustering Constraints // Journal of the Chinese Institute of Industrial Engineers Volume 26, Issue 6, 2009. pp. 440-448.

51. Luo R., Sun P. A Novel Ant Colony Optimization Based Temperature-Aware Floorplanning Algorithm // Third International Conference on Natural Computation ICNC 2007.-pp. 751-755.

52. Курейчик В.М., Кажаров А.А. Использование роевого интеллекта в решении NP-трудных задач // Известия Южного федерального университета. Технические науки. 2010. Т. 120. № 7. С. 30-36.

53. Лебедев Б.К., Лебедев В.Б. Планирование на основе роевого интеллекта и генетической эволюции Известия Южного федерального университета. Технические науки. 2009. Т. 93. № 4. С. 25-33.

54. Sun T.-Y. Floorplanning based on particle swarm optimization // ISVLSI '06 Proceedings of the IEEE Computer Society Annual Symposium on Emerging VLSI Technologies and Architectures. 2006. - pp. 5-10.

55. Chen G. et al. A PSO-based intelligent decision algorithm for VLSI floorplanning // Soft Computing A Fusion of Foundations, Methodologies and Applications Volume 14, Number 12. 2010.-pp. 1329- 1329.

56. Ерошенко И.Н. Методы адаптации генетических алгоритмов к задаче планирования СБИС // Труды конгресса по интеллектуальным системам и информационным технологиям «IS-IT'll». М: Физматлит, 2011. Т.З. С. 138— 145.

57. Ерошенко И.Н. Роль гибридизации метаэвристик в задачах оптимизации. // VIII Всероссийская научная конференция молодых ученых, аспирантов и студентов: Информационные технологии, системный анализ и управление. Таганрог: Изд-во ТТИ ЮФУ, 2010. с. 370 376.

58. Talbi, E.-G. A Taxonomy of Hybrid Metaheuristics // Journal of Heuristics, Kluwer Academic Publishers, 8. pp. 541-564.

59. Giinther R. A Unified View on Flybrid Metaheuristics // Lecture Notes in Computer Science. Vol. 4030. 2010. pp. 1-12.

60. Ерошенко И.Н. Меметическнй алгоритм планирования СБИС // Известия Южного федерального университета. Технические науки. 2010 №12(113) С. 55-62.

61. Maolin Т., Xin Y. A memetic algorithm for VLSI floorplanning // IEEE Transactions On Systems, Man, And Cybernetics—PartB: Cybernetics, 37(1), 2007. -pp. 62-69.

62. Shanavas I. H. et al. Evolutionary Algorithmical Approach for VLSI Floorplanning Problem // International Journal of Computer Theory and Engineering Vol.1, No.4 . 2009. pp. 461-464.

63. L. Wang, Y. Chang, K. Cheng. Electronic Design Automation: Synthesis, Verification, and Test. Morgan Kaufmann, 2009. - p. 972.

64. R.H.J.M. Otten, Automatic floorplan design // Proceedings of the 19th Design Automation Conference, Las Vegas, NV, 1982. pp. 261-267.

65. Курейчик B.M., Лебедев Б.К., Лебедев О.Б., Чернышев Ю.О. Адаптация на основе самообучения. Ростов-на-Дону: РГАСХМ ГОУ 2004. - 146 с.

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

67. Лебедев Б.К., Лебедев В.Б. Планирование СБИС на основе эволюционной адаптации // Известия Южного федерального университета. Технические науки. Т. 64, №9. 2006. С. 93-97.

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

69. Day W.H.E., EdelsBrunner Н. Efficient algorithms for agglomerative hierarchical clustering methods // Journal of Classification. Volume 1, Number 1. 1984. pp. 7— 24.

70. D.-S. Chen, С.-Т. Lin and Y.-W. Wang. A robust genetic algorithm for rectangle packing problem // Journal of Combinatorial Optimization 2006. vol. 13, no. 2.

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

72. Moscato, P. On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms // Caltech Concurrent Computation Program (report 826), 1989.

73. The International Technology Roadmap for Semiconductors — ITRS 2007 Edition: Tech. rep., Ed. by ITRS: International Technology Roadmap for Semiconductors, 2007. http://www.itrs.net.

74. Piguet C. Low-Power CMOS Circuits: Technology, Logic Design and CAD Tools. Boca Raton: CRC Press, 2005. - p. 867.

75. Yu В., Dong S.and GOTO S. Multi-Voltage and Level-Shifter Assignment Driven Floorplanning. // IEEE 8th International Conference on ASIC, 2009. pp. 1264-1267.

76. Yu В., Dong S., GOTO S. and Chen S. Voltage-Island Driven Floorplanning Considering Level-Shifter Positions // Proceedings of the 19th ACM Great Lakes symposium on VLSI, 2009. pp. 51-56.

77. Hung W.-L. Temperature-Aware Voltage Islands Architecting in System-on-Chip Design // Proceedings of the 2005 International Conference on Computer Design.2005. -pp. 689-696.

78. Hu J., Shin Y., Dhanwada N., and Marculescu R. Architecting Voltage Islands in Core-based System-on-a-chip Designs // Proceedings of the 2004 International Symposium on Low Power Electronics and Design. 2004. pp. 180-185.

79. Ma Q.and Young F.Y. Voltage Island-Driven Floorplanning // ICCAD, 2007. -pp. 644-649.

80. Мак W.K. and Chen J.W. Voltage island generation under performance requirement for soc designs // ASP DAC, 2007. pp. 798-803.

81. Lee W.P. and Chang Y.W. An ILP algorithm for postfloorplanning voltage-island generation considering powernetwork planning. ICCAD, 2007. pp. 650-655.

82. Wu H., Liu I.M. and Wang Y. Post-placement voltage island generation under performance requirement // Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, 2005. pp. 309-316.

83. Ching R. and Young F.Y. Post-placement voltage island generation // Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, 2006. pp. 641-646.

84. Lee W.-P. Voltage Island Aware Floorplanning for Power and Timing Optimization // IEEE/ACM International Conference on Computer-Aided Design,2006.-pp. 389—394.

85. Chen С.-Н. and Tollis I. G. Area Optimization of Slicing Floorplans in Parallel // VLSI Design, vol. 2, no. 2, 1994. pp. 143-156.

86. Cohoon J.P. Distributed Genetic Algorithms for the Floorplan Design Problem // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. Volume: 10, Issue: 4. 1991.-pp. 483^192.

87. Tang M., Lau R. Y. K. A Parallel Genetic Algorithm for Floorplan Area Optimization // Seventh International Conference on Intelligent Systems Design and Applications. 2007. -pp.801-806.

88. Ерошенко И.Н. Платформы для эволюционных вычислений: проблемы и перспективы развития. // Труды X Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», 2010. С. 123-124.

89. Luke S. ECJ: A Java-based Evolutionary Computation and Genetic Programming Research System-http://www.cs.umd.edu/proiects/plus/ec/eci/

90. Keijzer M. et al. Evolving Objects: A General Purpose Evolutionary Computation Library // Lecture Notes in Computer Science. Vol 2310. 2002. pp. 829- 888.

91. Cahon S. ParadisEO: A Framework for the Reusable Design of Parallel and Distributed Metaheuristics // Journal of Heuristics, 10, 2004. pp. 357-380.

92. Wall M. GAlib: A С++ Library of Genetic Algorithm Components -http://lancet.mit.edu/ga/.

93. Open BEAGLE http://beagle.gel.ulaval.ca/

94. MSDN http://msdn.microsoft.com/ru-ru/library/dd492418(v=VS.100).aspx

95. Ma Q., Young E.F.Y. Multivoltage Floorplan Design // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume: 29 No: 4. -2010.-pp. 607-617.