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

005007570

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

БУШИН Сергей Алексеевич

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

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

Автореферат

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

1 2ЯНВ2012

Таганрог 2011

005007570

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

Научный руководитель; доктор технических наук, профессор Малюков СЛ.

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

доцент Ковалев А.В.

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

Лебедев Б.К. (ГАОУ ВПО ТТИ ЮФУ, г. Таганрог)

доктор технических наук, профессор Витиска Н.И. (ГОУ ВПО ТГПИ. г. Таганрог)

Ведущая орпшиэация:ФГУП «Таганрогский научно-исследовательский институт связи»

Зашита диссертации состоится «19» января2012 г. в 14"' на заседании диссертационного совета Д 212.208.22 при Южном федеральном университстело адресу. 347928, Таганрог, пер. Некрасовский, 44, ауд. Д-406.

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

Автореферат разослан « Ш.............„„2013 г.

Ученый секретарь . диссертационного совета Д 212.208.22,

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

Целых А.Н.

Общая характеристика работы

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

Быстрый прогресс в технологии сверхбольших интегральных схем обуславливает потребность в новых средствах автоматизированного проектирования. Разработчикам СБИС необходимы интеллектуальные программные системы, позволяющие реализовывать схемы с миллионами транзисторов на одном кристалле. Такие высокие характеристики достигаются за счет совместной оптимизации топологии проектов и мега библиотек. Это позволяет перевести на новый уровень такие ключевые характеристики объектов проектирования, как мощность, быстродействие, занимаемая площадь. Количественный роет сложности объекта проектирования привел к качественным изменениям в методологии проектирования, к повышению роли всех обеспечений систем автоматизированного проектирования (САПР). Это позволяет в области синтеза топологии СБИС выйти на следующий уровень проектирования систем на кристалле в манометровом диапазоне. Причем при создании СБИС возможен переход от множества слоев металлизации к одному-двум слоям. Процесс проектирования современных СБИС состоит из трех основных относительно независимых частей: логическое проектирование, тестирование и верификация, синтез топологии. Системная интеграция данных этапов позволяет реализовывать платформы на «чипах» и переходить к созданию атомных процессоров. Межсоединения па кристаллах все более сложными поэтому возрастает проблема синтеза топологий. В этой связи разработка новых интегрированных алгоритмов проектирования топологии является актуальной и важной для современных поколений радиоэлектронной и электронно-вычислительной аппаратуры. В работе рассмотрена одна из важных задач конструкторского проектирования СБИС - задача размещения. Она относится к классу NP- сложных. В этой связи разработка комплекса эффективных полиномиальных алгоритмов с использованием современных критериев, является актуальной и важной задачей.

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

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

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

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

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

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

1. Предложены основные принципы и классификация математических моделей схем и критериев задачи размещения. Выбран комплексный критерий на основе оценки электро-магнитно-тепловой совместимости элементов.

2. Разработана модель оценки энергопотребления и задержки асинхронными элементами для оптимизации и сравнения КМОП-.элемеитов асинхронной логики.

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

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

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

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

Практическая ценность результатов диссертационной работы:

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

2. Создана специализированная программная среда для моделирования при решении задач размещения.

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

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

Реализации результатов работы. Материалы диссертации использованы в госбюджетных научно исследовательских работах Технологического института Южного федерального университета в г. Таганроге (ТТИ ЮФУ), а также в научно-исследовательских работах, выполненных по грантам Российского фонда фундаментальных исследований'(НИР № 12353, 12388, 12380) и по заказам предприятий (х/д НИР №13411). Результаты этих работ внедрены и используются в учебном процессе на кафедрах КЭС и САПР в ТТИ ЮФУ, а также на предприятиях. Акты о внедрении и использовании результатов работы приведены в приложении к диссертации.

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

Публикации. Основные результаты диссертационной работы отражены в 9 печатных работах, в том числе 5 работ опубликованы в изданиях рекомендованных ВАК РФ для

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

Структура и объем диссертационной работы.

Диссертация состоит из введения, четырех разделов, заключения, изложенных на 142 страницах, 72 рисунков, 10 таблиц, списка литературы из 104 наименований и приложения.

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

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

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

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

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

В основном при проектировании СБИС большой размерности (число элементов более 10f') рассматриваются эвристические методы нахождения приближённых решений. Функциональные характеристики каждого компонента РЭЛ или ЭВА описываются системой коммутационных, электрических, конструктивных и внешних параметров: F =

F(A,B,C.D,H,Vj"

Рис. 1.1, Общий маршрут проектирования СнК

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

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

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

G = (Х.Е),

X ={.v,vv,xA4l......v,v+;i),

E-ie^eJ (U)

1(e) — max I.V,—.y,l + max Ir,—/I

V'tf

Постановка задачи размещения: для каждого размещаемого элемента е, заданы:

линейные геометрические размеры: длина - н; и ширина - />,•; список контактов С„ через которые производится сопряжение элемента с другими элементами схемы или устройства. Каждый контакт характеризуется координатами (л-, у), заданными относительно базовой точки элемента, и номером подключаемой к нему цепи .

В качестве математической модели, описывающей заданную схему, используется

гиперграф С = (А', С/. Р), где: А' = I ¡ = 1,2.....и) - множество вершнн, моделирующих

элементы;У = 2. ..., т) - множество гиперребер, моделирующих цепи,

связывающие элементы; Р~ пнцидентор, заданный на множестве X * Ц и определяющий отношение инцидентности между вершинами н ребрами гнперграфа (двудольного графа), ч Г1. если и { шшидешно х.

п (1-2)

' [О, если не иицидешно х,

В качестве оценки длины цепи гу, моделируемой гиперребром щ , используется длина минимального связывающего дерева, построенного на множестве вершин .V, е X. Определяется некоторый вариант размещения элементов па монтажном пространстве 5= {уч, о/), ... (Л|, V,-, <•>/). ... (лп, у„ о,,)!, где хк У1 - координаты базовой точки, а о, -ориентация элемента размещения <-,••

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

Р = к,-0(Цг11) + Ь ■Я(5„,„1,(су)) + к, • 1>{Т1<1ш). 0.3)

где :/ - некоторый вариант размещения; кг , к.; - весовые коэффициенты, заданные таким образом, чтобы их сумма равнялась единице; !(;,) ~ суммарная длина проводников (межсоедипенний); 0(Цг,)) - нормированная оценка общей длины соединений,

приведенная к интервалу [0, /]; ..... фактическая площадь размещения, определенная

как плошадь минимального прямоугольника, описывающего размещенные элементы;

Р&ыщЩ,)).....нормированная оценка общей площади размещения, принимающая значения

из интервала [0, /]. Р(Т,„-,„,) - нормированное значение задержки сигналов на данном коммутационном поле.

Таким образом, задача размещения состоит в отыскании минимального значения функции /•' на множестве допустимых размещений 2:

^(г,) ->ег (1.4)

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

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

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

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

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

Г\ = (Р°ЛР1*ТиА-Шф.0Г1'-1У),1'0, ОМГл). (2.1)

где /у- исходная популяция хромосом (альтернативных решений), заметим, что в частном случае может быть выбрано одно, решение, которое моделируя идеи «основателя» позволяет получить второе решение. На основе этих решений генерируется набор различных популяции (альтернативных решений задачи размещения); Р!'=(Р°1. Р/а...» Р:"п). Рие Р" - хромосома (альтернативное решение), принадлежащее 1-ой исходной популяции; N - мощность популяции, т.е. число входящих в нее хромосом, Л'=1Р/|; РД<?

Р1 ..... к-я хромосома, принадлежащая /-ой популяции, находящейся в Т поколении

эволюции; Т = 0,1,2.... - номер поколения, проходящего популяцией во время эволюции. Число поколений связывают с числом генераций генетического алгоритма, обозначаемых буквой О; - длина /-он хромосомы (альтернативного решения), т.е. число генов (элементов, входящих в закодированное решение, представленное в заданном алфавите). Отметим, что каждый ген может характеризоваться списком параметров и представлять собой функцию, зависящую от конструктивно-технологических ограничений на проектирование, например, |Р,Т1= 2./. А - произвольный абстрактный алфавит, в котором, кодируются хромосомы, например, Л;={0,1), Дг={0,1,2,...,10}, /1.1= (0.1,2,*),

А<={АЗ,СЛ>}, здесь * - метка, означающая любой символ в алфавите Аг. (ЦФ.ОГР.ГУ).....

целевая функция, ограничения и граничные условия, которые определяются на основе

заданной модели исходной решаемой задачи; ГО - генетические операторы, I.....критерий

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

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

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

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

3. Определение способа представления решения.

4. Построение начальной популяции альтернативных решений.

5. Выбор операторов случайных и комбинированных изменений, а также разработка новых операторов.

6. Поиск и выбор способа «выживания» решений, то есть правил отбора особей в новую популяцию.

7. Формирование правил введения положительных и отрицательных обратных связей на основе адаптации к внешней среде.

8. Задание способа окончания генетического поиска.

9. Построение фенотипа на основе полученного генотипа (декодирование решения).

В третьем разделе предложена модель оценки энергопотребления и задержки асинхронными элементами. Модель использована в САПР СБИС для оптимизации и сравнения КМОП-элемснтов асинхронной логики.

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

О = Кпр+г+рг+1 WW0+VVlW+2Kt,(p+r+pr+I)==S\VWD+WlW+25'. (Л.))

где р - это отношение подвижиостей электронов и дырок; \У, \У], - ширины п-каиалышх транзисторов нагрузочного, текущего н нагрузочного каскадов, соответственно: Ко и К'ц - константы задержек, зависящие от емкостей канала и диффузионных областей соответственно; й и Й' - введенные константы.

Потребляемая энергия в течении одного такта (передний и задний фронты) рассчитывается с помощью выражения:

Е= КЕг+1\У+ К'ЕГ+1\У=11\У+11'\У, (3.2)

где Ке и К'к - константы рассеиваемой энергии на единицу ширины канала и единицу ширины диффузионной области соответственно; т| н г|' - введенные константы.

Значения констант в (3.1) и (3.2} для технологии КМОП 0.5 мкм (5 В) определены с помощью БРЮЕ-моделирования. Таким образом: Ко - 0,0256 не; КЪ = 0,0319 не; Ке = 0,0176 пДж/мкм; К'к = 0,0207 пДж/мкм.

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

Для динамической реализации асинхронного элемента выражение для задержки трансформируется в следующее:

йВ = бп\*ЛУо+2и+\У[.'п\|/+\¥1_и+45', (3.3)

где п - число транзисторов в сети; и - ширина п-канального транзистора в буферном инверторе. Оценка энергии для динамической реализации:

ЕО = п2'М'+и+>1,п\\'+и. (3.4)

Статическая основная реализация включает дополнительные транзисторы как переключательной части, так и в буферной. Выражение для определения задержки: IXГ=йnWWD+2LЦWL'лVV+WLU+2KDI+pгwminWD+wm¡nU+4(б'+KD'l+prwminnW). (3.5)

где ъ\„т - минимальная ширина транзистора. Оценка энергии для. статической основной реализации;

ЕС - ц2пЩи+6кяъ$Е*г1"г№+и+2\«1пь$.Е. (3.6)

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

£>С = 6п »Щ>+2{/+ \\',13+2Кт+р™тт 0+46(3.7)

Оценка энергии для симметричной реализации:

ЕС = фН'+и^н-^Кг+пШ'+и. (3.8)

Сравнение аналитической модели первого порядка с результатами ЗРТСЕ-моделпрования показало расхождение не более чем на 10%. Модель может быть использована в САПР СБИС для оптимизации и сравнения КМОП-элсментов асинхронной логики.

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

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

При проектировании заказных СБИС используются не матричные структуры (полузаказные), а свободные от сеток разногабаритные блоки. Поэтому для эффективного решения задачи размещения блоков заказных СБИС используем направленное диагональное дерево представления для описания размещения разногабаритных блоков СБИС. Дерево является графом О = (\',Е), у которого вершины V - размещаемые блоки, и ребра Е - геометрические отношения между двумя блоками. Направленные ребра Е покалывают отношения "родитель - потомок". В данном графе каждый родитель может

иметь не более двух потомков - Рь (левый) и Рн (правый). Корнем дерева является узел-блок, лежащий в левом нижнем углу поля размещения. Кодирующая хромосома (КХ) представляет собой объектное описание иерархии дерева иа основе ссылок (рис. 3.2). Каждый узел (вершина) дерева может иметь не более двух дочерних узлов (бинарное дерево). Это связано с особенностями процедуры построения топологии. В данном дереве необходимо явно кодировать обе ветви (Рц Рц - левую и правую). При расчете значения целевой функции, учитывается суммарная длина связей, соединяющих не центры блоков, а контакты на границах или внутри блока. Таким образом, для кодирования направленного дерева с 11 узлами-объектами минимально необходимое количество бит Ь можно рассчитать по формуле:

I = Зл[1о§2 и] + 2п = и(3[1с^2 п]+ 2). _ (3.9)

Число возможных кодирующих конфигураций 0(п!2'"' '/п "). Предложенный способ кодирования имеет компактную форму представления данных о размещении и позволяет аффективно оперировать ей. Дня построения топологии рабочего поля необходимо построить дерево и разместить блоки согласно правилам, заложенным в кодировке топологии.

о | о

о | о

»9 I О

«а ) а?

о | о

&с) I О

2*г

ИЖЦрНЩ]

Рис.3.2. Пример описания бинарного дерева на основе ссылок

Этапы алгоритма построения топологии из дерева (первым текущим блоком является корневой узел-объект):

1. Текущий блок устанавливается в вакантное место. Под вакантным местом понимается ЬВ-компакгнос (левое нижнее) положение вставляемого блока.

2. Строится огибающий контур с учетом текущего размещенного блока.

3. Новый огабаюшиб контур будет иметь два вакантных места для потомков Р¡. и Ри вблизи текущего блока (слева сверху и справа снизу);

4. Далее в эти вакантные места размещаются дочерние блоки (если существуют);

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

6. Конец работы алгоритма.

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

Приведем основные свойства бинарного дерева:

• первый узел-объект в списке является корнем дерева;

• вставка нового узла-объекта ("листа") или поддерева может быть произведена в любую позицию с пустой ссылкой на потомка;

• допустимы любые перестановки между потомками одного узла-объекта.

• "листья" дерева имеют две пустые ссылки на потомков;

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

В алгоритме применяются два модифицированных генетических оператора (ГО) -кроссинговер и мутация, ориентированные на решаемую задачу.

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

II, ГО мутации № 1. Суть оператора состоит в том, что он производи- парную перестановку имен узлов по определенным правилам:

- перестановка имен производится путем обмена именами и свойствами между двумя, определенным образом выбранными, узлами-объектами;

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

III. ГО мутации № 2. Оператор осуществляет изменение ориентации блоков без изменения их позиции и структуры дерева. Процедура изменения ориентации также может охватывать различные иерархические уровни в зависимости от времени жизни особен в популяции (рис.3.4).

IV. ГО упорядоченного кроссинговсра. Данный оператор позволяет потомкам наследовать лучшие свойства родительских особей. Суть его состоит в том, что происходит обмен конструкциями одинаковой длины в родительских хромосомах. Сначала в соответствующую позицию потомка 02 вставляется обменная конструкция из родителя Р1, затем добавляются недостающие гены из Р2. В потомок 6 в соответствующую позицию вставляется обменная конструкция из родителя Р2 и добавляются недостающие гены из Р1. Применение данного оператора возможно, если в родителях есть конструкции одинаковой длины, иначе они пе подходят для скрещивания.

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

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

1. Разворачиваем, свернутые на данном'уровне вершимы. Если возможно переход на уровень ниже. Иначе к пункту 10.

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

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

: 4. Вычисление ЦФ и сортировка индивидов на ее основе.

:..' 5. Селекция, основанная на элитной стратегии.

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

7. Формирование новой популяции.

8. Вычисление ЦФ и сортировка индивидов на ее основе.

9.Редукши популяции, сохранение перспективных решений, выбор лучшего решения. Если не пройдено число итераций переход к шагу 5. Иначе переход к пункту 1.

Ш.Конец работы алгоритма.

а)

Р»

ьн«е

б)

Рис.3.3. ГО инверсии: поворот поддеревьев (а) и листьев (б)

Рис, 3.4. ГО мутации: изменение ориентации блоков

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

Для оценки трассируемое™ соединений используется гиперграф, в котором выделяются бинарные связи (БС).

Общее число БС п для всего графа, в котором количество гиперребер равно /.определяется:

Я=У-......гч'. (3.10)

¿-л 21 (ггц - 2) ¡=о

Интегральная ЦФ, которая учитывает критерии временных задержек и трассируемости соединений примет следующий вид:

а * А™

ДФ = —п-"^ + /? * Лг (3.11)

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

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

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

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

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

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

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

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

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

Строим матрицу смежности размерностью (N,E), где N - описывает порядок-размещения вершин, а Е - расстояние между вершинами.

Пусть Ь,(0, где i— 1.....п - число агентов в вершине i в момент времени t. при этом

общее число агентов m вычисляется:

Запишем правила работы агента:

- он должен выбирать вершину с вероятностью, зависящую от расстояния и числа следов в указанном направлении;

- он не имеет право посещать уже пройденные вершины до окончания всего маршрута, когда будет достигнута конечная вершина списка;

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

Пусть »¡/О - интенсивность меток на интервале (у) в момент времени г. Каждый агент в момент времени I выбирает следующую вершину, в которой он окажется в момент времени (1+1). Следовательно, если мы проведем п итераций муравьиного алгоритма для т агентов в интервале (с 1+1), тогда каждая п-итерация алгоритма приведет к тому, что каждый агент сможет закончить тур.

Для выполнения ограничений (каждый агент должен посетит!, п различных вершин), с каждым агентом ассоциируется некоторая структура данных, которая называется 5аЬи-список. В нем сохраняются те вершины, которые уясе посетили к моменту времени I. Таким образом, агенту запрещается посещение одной и той же вершины до окончания пути. Когда маршрут пройден, значения в 1аЬи-списке подсчнтываются для каждого текущего агента (т.е. подсчитывается дистанция, пройденная агентом). ТаЬн-список затем обнуляется, и агент опять может продолжать движение, начиная со стартовой вершины.

п

(3.21)

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

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

Блоки отображенные па рис. 3.6:

Блоки 1-3-задание начальных параметров работы системы. Блоки 4-6 - инициализация входных параметров: Блок 7 - определение стартующей вершины

Блоки 8-11 - цикл прохождения по всем вершинам с одновременным занесением в 1аЬи-список.

Блоки 12-16 - обработка ситуации, когда завершился проход по веем вершинам:

для всех у '.

Блоки 18-19 - наращивание счетчика циклов и обнуление интенсивности. Блоки 20-21 - обработка условия ЖХМСтах. Блок 22- выдать наикратчайший путь.

Время работы алгоритма .зависит от размера анализируемой матрицы или списка. Время работы предлагаемого алгоритма в лучшем муча« имеет порядок роста п, т.е. 0(п), где и - число вершин графовой модели КС. Среднее время работы модифицированного муравьиного алгоритма зависит от выбранного распределения вероятностей и числа вершин графа. Использование моделей приведенного поиска позволяет за кратчайшее

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

Рис. 3.6. Структурная схема модифицированного муравьиного алгоритма

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

Для реализации алгоритмов размещения разработана программная среда на языке программирования Borland С++ Builder 6.0. Программа состоит из основного исполняемого модуля Project.exe, разработанного под операционные системы Windows NT/XP/Vista/7.

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

Для определения ВС.А. алгоритма был проведён ряд экспериментов, в которых изменялось количество элементов от 100 до 5000. Настройки генетического алгоритма следующие: стратегия создания популяции на основе механизма случайно-направленного выбора ( дробовика) ; селекция: элитная; оператор кроссинговера: модифицированный: вероятность ОК: 80%; оператор мутации: модифицированный; вероятность ОМ: 25%; оператор инверсии: модифицированный; вероятность ОИ: 20%; численность популяции 100; количество поколений 300.

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

Рис.4.1 главное окно программы

Рис.4.2.....График зависимости времени работы алгоритмов от числа элементов

1500 т~--—------—

1000 ----------------------— ~ '"щ 1ГА

500 ...' ? «й ' й ? 15 Итерационный

0 Ш., ■ -ж 111 -* ,

1000 2000 3000 4000 5000

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

■ мго шпго

I 1000 2000 3000 4000 5000

Рис.4.4 - Эффективность генетических операторов

Управление процессом бионического поиска при размещении позволяет находить локальные и оптимальные параметры для реализации разработанных алгоритмов.

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

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

1. Приведены новые основные принципы и Описан общий маршрут проектирования СнК до выполнения этапа логического синтеза.

2. Проведен краткий обзор и анализ алгоритмов размещения. Отмечено, что перспективными являются алгоритмы, инспирированные природными системами. Дана постановка задачи размещения.

Я. Приведена классификация математических моделей схем и критериев задачи размещения. Выбран комплексный критерий на основе оценки электромапштотепловой совместимости элементов.

4. Предложена модель оценки энергопотребления и задержки асинхронными элементами. Модель может быть использована в САПР СБИС для оптимизации и сравнения КМОП-элементов асинхронной логики.

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

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

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

8. Построен композитный алгоритм размещения на основе новых механизмов свертки, начального размещения и распаковки. Это позволяет обрабатывать большие массивы (п> 10й, где п- число размещаемых элементов) входной информации и получать локально-оптимальные результаты за полиномиальное время.

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

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

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

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

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

Публикации но теме диссертации

Публикации в изданиях, рекомендованных ВАК РФ

1. Бушнн СЛ.. Курсйчик В.В. Генетический алгоритм размещения разногабаритных элементов. Известия ЮФУ. Технические науки, 2009, Xsl2(83). С. 22 -27.

2. Бушин С.А., Ковалев A.B. Модели энергопотребления асинхронных функциональных блоков КМОП СБИС' Известия ЮФУ. Технические науки, 2009, №12(83). С. 198-200.

3. БушипС.А.. КурейчмкВ.В. Размещение узлов и блоков РЭА и ЭВА на основе бионических методов Программные продукты и системы, 2010. № 1(89). С. 12-15.

4. Бушин СЛ., Ковалев A.B. Эволюционный метод размещения разногабаритных блоков СБИС Известия ЮФУ. Технические науки, 2010, №17(83). С. 45-53.

5. Бушнн СЛ., Малюков С.П. Анализ и состояние проблемы размещения компонентов СБИС. Дсп. в ВИНИТИ № 190-В от 22.04.2011.

Публикации но теме диссертации п других изданиях

6. Бушин СЛ. Об одном подходе к размещению узлов и блоков РЭА и ЭВА. Перспективные информационные технологии и интеллектуальные системы,- Таганрог. №2 (35-36)/ 2009, -С. 1 -20.

7. Бушин СЛ. Метод снижения энергопотребления в асинхронных блоках СБИС. Материалы X ВНТК студентов и аспирантов Техническая кибернетика, радиоэлектроника и управление. Т.2. Таганрог: Изд-воТТИЮФУ, 2010. С. 37-38.

8. Бушин СЛ., Ковалев A.B. Эволюционный метод распределения задач в системах-на-крнсталле для снижения энергопотребления Труды Международных научно-технических конференций «Интеллектуальные системы» и «Интеллектуальные САПР». -М.: Физматлит. 2010, Т.1. С. 102-103.

9. Малюков СЛ., Бушин С.А. Разработка алгоритма размещения для компонентов СБИС // Труды Международных научно-технических конференций «Интеллектуальные системы)> и «Интеллектуальные САПР». -М.: Физматлит, 2011, Т.З. С. 291-294.

Личный вклад диссертанта в работы, опубликованные в соавторстве:

[1] - анализ и построение моделей эволюции.

[2] - новые алгоритмы построения генетических операторов.

[3.41 - структура интеллектуальных систем поддержки принятия решений.

[5] - анализ автоматизированных систем представления знаний.

[8, 9] - элементы динамических экспертных систем и алгоритмы при принятии

решений.

Тип. ТТИ ЮФУ Заказ № тир. 100 Экз.

Издательство Технологического института Южного федерального университета в г. Таганроге ГСП - 17А, Таганрог, 28, Некрасовский, 44 Типография Технологического института Южного федерального университета в г. Таганроге Таганрог, 28, ГСП 17А, Энгельса, 1

61 12-5/1303

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ В Г. ТАГАНРОГЕ

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

БУШИН Сергей Алексеевич

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

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

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

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

д-р техн. наук Малюков С.П.

Таганрог 2011

Содержание

ВВЕДЕНИЕ..........................................................................................................3

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

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

IЛ. Проблемы конструкторского проектирования СБИС...........................9

1.2. Краткий обзор и анализ алгоритмов размещения................................19

1.3. Постановка задачи размещения.............................................................30

1.4. Краткие выводы.......................................................................................39

2. ГЛАВА 2. ПОСТРОЕНИЕ МОДЕЛЕЙ СБИС......................................40

2.1. Разработка графовых моделей................................................................40

2.2. Построение моделей, схем ж монтажно-коммутационного пространства в виде специальных графов......................................................49

2.3. Использование методов эволюционного моделирования при размещении........................................................................................................59

2.4. Краткие выводы.......................................................................................63

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

3.1. Модели энергопотребления асинхронных функциональных

блоков КМОП СБИС.........................................................................................65

3.2. Описание биоинспирированных методов задач размещения.............71

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

3.4. Разработка алгоритма решения задач и размещения на основе модифицированной агрегации фракталов......................................................88

3.5. Разработка комплексного гибридного генетического алгоритма размещения элементов................................................................................•••• Ю5

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

3.7. Разработка проблемно-ориентированного генетического алгоритма...............................................................................•••■•......................Ю6

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

3.9. Краткие выводы.....................................................................................112

4. ГЛАВА 4. РЕЗУЛЬТАТЫ ВЫЧИСЛИТЕЛЬНОГО ЭКСПЕРИМЕНТА...........................................................................................114

4.1. Краткое описание программного комплекса.....................................114

4.2. Краткие результаты вычислительного эксперимента........................118

4.3. Краткие выводы.....................................................................................122

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

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

ВВЕДЕНИЕ

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

Быстрый прогресс в технологии сверхбольших интегральных схем обуславливает потребность в новых средствах автоматизированного проектирования. Разработчикам СБИС необходимы интеллектуальные программные системы, позволяющие реализовывать схемы с миллионами транзисторов на одном кристалле. Такие высокие характеристики достигаются за счет совместной оптимизации топологии проектов и мега библиотек. Это позволяет перевести на новый уровень такие ключевые характеристики объектов проектирования, как мощность, быстродействие, занимаемая площадь. Количественный рост сложности объекта проектирования привел к качественным изменениям в методологии проектирования, к повышению роли всех обеспечений САПР. Это позволяет в области синтеза топологии СБИС выйти на следующий уровень проектирования систем на кристалле в нанометровом диапазоне (2009-32нм, 2011-22нм и прогноз на 2013- 15нм и 2015-11нм) [1]. Причем при создании СБИС возможен переход от 8, 9 слоев металлизации к одному слою. Процесс проектирования современных СБИС состоит из трех основных относительно независимых частей: логическое проектирование, тестирование и верификация, синтез топологии. Системная интеграция данных этапов позволяет реализовывать платформы на «чипах» и переходить к созданию атомных процессоров. Межсоединения на кристаллах все более сложными поэтому возрастает проблема синтеза топологий. В этой связи разработка

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

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

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

построение графовых и гиперграфовых моделей коммутационных схем топологий и размещаемого пространства;

разработка эвристических поисковых методов размещения моделей коммутационных схем в заданной области ЧИПа;

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

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

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

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

2. Предложенна модель оценки энергопотребления и задержки асинхронными элементами для оптимизации и сравнения КМОП-элементов асинхронной логики.

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

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

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

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

Реализация результатов работы. Материалы диссертации использованы в госбюджетных научно исследовательских работах Технологического института Южного федерального университета в г. Таганроге (ТТИ ЮФУ), а также в научно-исследовательских работах, выполненных по грантам Российского фонда фундаментальных исследований (НИР № 12353, 12388, 12380). Результаты этих работ внедрены и используются в учебном процессе на кафедрах КЭС и САПР в ТТИ ЮФУ. Акты о внедрении и использовании результатов работы приведены в приложении к диссертации.

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

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех разделов, заключения, изложенных на 163 страницах, 72 рисунков, 10 таблиц, списка литературы из 126 наименований и приложения.

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

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

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

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

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

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

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

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

В приложении даны копии актов внедрения.

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

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

1.1. Проблемы конструкторского проектирования СБИС

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

Как известно [1-7], проектирование - это процесс преобразования информации, находящейся в техническом задании на разрабатываемое изделие, в информацию, необходимую для его изготовления и контроля на технологическом и контрольно-измерительном оборудовании. Для качественного выполнения проекта используют следующие основные принципы[8,9]:

1. Принцип «бритвы Оккама» не усложняй систему проектирования без необходимости.

2. Принцип декомпозиции «разделяй и властвуй». Разбиение сложной задачи проектирования на более простые части.

3. Иерархический принцип проектирования по этапам.

4. Итерационный принцип проектирования. Это последовательное приближение к выполнению требований ТЗ и оптимизация заданных критериев на каждом этапе.

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

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

7. Принцип контролируемости и диагностирования каждого этапа проектирования.

Результатам проектирования является выпуск проектной документации. При этом используют следующие методы проектирования [2,3, 10-12]: макетирование; физическое моделирование; расчет по аналитическим выражениям; математическое моделирование и построение топологии.

Топология, как известно[2,7], это аналог электрической схемы в виде набора геометрических образцов слоев кристалла. Разработка топологии БИС включает: относительное взаимное размещение компонентов с минимальным числом пересечений; размещение компонентов в системе координат на кристалле с учетом схемотехнических, технологических, нормативных ограничений и требований по энергосбережениям; трассировку (проведение внутрисхемных соединений); подготовку информации для изготовления фотошаблонов. Процент «выхода годных» БИС зависит от площади кристалла, задержки сигнала, напряжения в узлах решетки. Основной тенденцией при проектировании БИС является постоянное уменьшение минимального расстояния, в пределах которого может быть достигнуто успешное формирование элементов на пластине. При проектировании БИС задаются не абсолютные размеры, а используются единицы, кратные некоторому параметру размера. Этот параметр приблизительно равен максимальному значению случайного смещения границы топологического элемента, которое может возникнуть при его формировании на пластине. Наряду с другими факторами этот параметр ограничивает ширину проводника. Технологический уровень изготовления БИС характеризуется именно этим параметром, значение которого за последние десять лет изменялось следующим образом: (2-1,5-1,0-0,7- 0,5-0,35-0,18-0,08) мкм [1,2,13].

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