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


Скачать 240.49 Kb.
НазваниеМетоды и алгоритмы многокритериальной оПТимизации стандартных ячеек в субмикронных технологиях проектирования сбис
Дата05.11.2012
Размер240.49 Kb.
ТипАвтореферат

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




Мелик-Адамян Арег Фрикович


Методы и алгоритмы многокритериальной

оПТимизации стандартных ячеек в субмикронных технологиях ПРОЕКТИРОВАНИЯ СБИС


Специальность: 05.13.01 — Системный анализ, управление и обработка информации


АВТОРЕФЕРАТ

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

кандидата физико-математических наук


Работа выполнена в Институте точной механики и вычислительной техники им. С. А. Лебедева РАН


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

Рыжов Александр Павлович


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

профессор Семенов Николай Александрович;

доктор физико-математических наук,

профессор Ульянов Сергей Викторович


Ведущая организация: Институт точной механики и вычислительной техники им. С.А Лебедева РАН.


Защита состоится 17 декабря 2009 г. в 14:00 часов на заседании диссертационного совета Д 212.263.02 при Тверском государственном университете по адресу: 170100, г. Тверь, ул. Желябова, д. 33, ауд. 52.

С диссертацией можно ознакомиться в библиотеке Тверского государственного университета. 170000, г. Тверь, ул. Володарского, д. 44а.

Текст автореферата и объявление о защите размещены на сайте Тверского государственного университета http://university.tversu.ru/aspirants/abstracts/


Автореферат разослан 03 ноября 2009 г.


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

доктор физико-математических наук, профессор Михно В.Н.

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

Актуальность темы диссертационного исследования.

В настоящее время современные субмикронные технологии производства СБИС достигли такой степени интеграции, что минимальный размер топологического объекта меньше длины волны, используемой при фотолитографии. В частности, за последние 30 лет длина затвора МОП-транзистора уменьшилась в 250 раз, с 10 мкм в начале 70-х годов до 40 нм в наши дни, а длина волны всего примерно, в 10 раз с 2 мкм до 193 нм. Как следствие этого, к известным технологическим ограничениям на минимальное расстояние и размер объектов топологии добавились новые, более сложные правила, зависящие, например, от конфигурации объектов, геометрических размеров, взаимного расположения объектов топологии и особенностей процесса производства. Кроме того, для создания объектов меньше чем длина волны применяются специальные приемы, позволяющие улучшить разрешающую способность технологического оборудования. Например, засветка противоположными фазами с разных сторон проводника, или оптическая коррекция близости1.

С другой стороны, известно, что с уменьшением геометрических размеров транзисторов снижается площадь кристалла, уменьшаются паразитные ёмкости, улучшается быстродействие и снижается энергопотребление СБИС. Тем не менее, это влечет за собой экспоненциальный рост утечек тока на единицу площади. Например, на пороговые утечки приходиться до 50% от общего объема энергии для портативных приложений, разработанных для 65нм технологии (рис. 1)2. Дальнейшее развитие технологии, масштабирование размеров, толщины подзатворного окисла приведет к значительному росту туннельного тока, что еще больше усугубляет проблему утечки.



Рисунок 1: Графики соотношения видов энергопотребления

в СБИС по технологическим нормам


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

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

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

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

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

Для достижения этой цели необходимо решить следующие задачи:

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

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

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

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

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

Объектом исследования является топология стандартных ячеек.

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

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

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

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

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

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

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


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

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

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

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

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

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

Реализация полученных результатов работы. Результаты диссертационной работы использованы в ряде научно-исследовательских проектов в ИТМ и ВТ, а именно:

  • В проекте «Ардон» – разработка инструментальной среды генерации стандартных библиотек.

  • В проекте «Ардон-2» – разработка системы генерации и оптимизации стандартных библиотек.

  • В оптимизации промышленных библиотек для «Микрон-НИИМЭ».

Апробация результатов исследования. Основные результаты диссертационной работы опубликованы в работах [1-7], из них в изданиях, рекомендованныx Перечнем ВАК Министерства образования и науки Российской Федерации – 3 работы [1-3]. Результаты неоднократно докладывалась на научных конференциях и семинарах, в частности:

  • на 51-ой Научной конференции МФТИ, 2008;

  • на конференции по автоматизации физического проектирования Ментор Графикс, 2008;

  • на семинарах факультета ВМиК МГУ 2008;

  • на семинарах ИТМиВТ 2006-2008.

Личный вклад автора заключается в:

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

  • участие в разработке метода комбинированного поискa [4];

  • в постановке обобщенной задачи пост-топологической оптимизации;

  • руководстве разработкой программной системы Cell Compiler для оптимизации и генерации стандартных ячеек;

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

Публикации. Основное содержание диссертации опубликовано в 6 работах, перечень которых приведен в списке литературы.

Структура и объем диссертации. Диссертация состоит из 120 страниц текста, содержит введение, четыре главы, заключение, список литературы из 160 наименований, приложение, 31 рисунков и 6 таблицы.

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

В первой главе диссертационной работы содержится обзор состояния исследований в области проектирования и оптимизации библиотек стандартных ячеек. Рассмотрены основные проблемы, соответствующие международной технологической дорожной карте по полупроводникам (ITRS – International Technology Roadmap for Semiconductors 2007). Детально рассмотрены проблема возникновения тока утечек в субмикронных технологиях. Определены его источники, причины возникновения, классифицированы типы токов утечек – 8 основных механизмов утечек. I1 – это ток утечки обратного смещения в стыке p-n, вызванный барьерной эмиссией, вместе с небольшим сдвигом носителей и межзонным сдвигом туннелирования от оксидно-поликремниевой поверхности, I2 – это слабо инверсионный ток, I3 это стоко-вызванная утечка через барьер (DIBL), I4 затворно-вызванная



Рисунок 2: Ток утечки в субмикронных транзисторах


утечка стока (GIDL), I5 – утечка канала, I6 – утечка через поверхность канала из-за узости канала, I7 – утечка через оксид, и I8 – утечка через затвор в следствии вхождения горячих носителей заряда. Токи I1I6 возникают, когда транзистор выключен, а I7 (туннелирование оксида) возникает в рабочем состоянии. I8 возникает как в выключенном состоянии, так и при переходном из включенного в выключенное.

Далее рассматривается уровень стандартных схем и рассматриваются токи утечек на схемном уровне. Рассматриваются уравнения SPICE, где все виды утечек приводятся в виде системы нелинейных уравнений. Показываются зависимости тока утечек в схемах от входных векторов на примерах ячеек инвертора и И-НЕ.

Приводиться обзор методов оптимизации токов утечки и обзор инструментария работы с ними. Представлены экспериментальные данные по нескольким сложным схемам, где показана целесообразность замены некоторых ячеек на ячейки с меньшим током утечки с сохранением остальных характеристик в пределах разрешенной вариации. Далее ставиться общая математическая постановка задачи. Пусть G = (N,E) направленный ациклический граф, соответствующий КМОП-схеме. Множествo N={1,…,n}, соответствующее множеству узлов в графе, отображается взаимно-однозначным образом на транзисторы в стандартной КМОП-схеме. Таким образом, транзистору i соответствует iN. Если ребро , то транзистор i соединен с транзистором j. Через хi обозначим длину транзистора i. Введем понятие критериальных функций. Таких функций у нас будет 4: P – статического энергопотребления, T – задержки, A – площади, Y – уровня выхода годных. Все эти функции зависят от множества параметров и детально будут рассмотрены в главе 2, но для наших исследований, существенными являются длины транзисторов. Таким образом, P = P(x1, x2,… xn), A = A(x1, x2,… xn), T = T(x1, x2,… xn), Y = Y(x1, x2,… xn). Функции P, T и Y характеризуются тем качеством, что точное значение может быть вычислено только с помощью либо SPICE моделирования для функций P, T, либо с помощью системы нелинейных уравнений для Y.

Задача ставиться следующим образом.

P → min,

(Т,А→ min, Ymax)

T ≤ Tmax

A ≤ Amax

Y ≥ Ymin


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

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

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

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

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

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

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

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


Рисунок 3: Метод кодирования

Обобщенная постановка задачи выглядит следующим образом: да­но (G, O),


най­ти L;

min σ2 (d);

max Y;

min P;

min Т;

min А;

при (2)

μ(d) ≤ μmax

π(G) ≤ πmax


где,

1. G есть мно­же­ст­во всех тран­зи­сто­ров и gi G;

2. O есть мно­же­ст­во вы­хо­дов ячей­ки, OG;

3. L = {l1, l2, . . . , ln}, где li дли­нa варьируемой области;

4. μ(x) ма­те­ма­ти­че­ское ожи­да­ние ;

5. σ2 (x) дис­пер­сия слу­чай­ной ве­ли­чи­ны x;

6. di за­держ­ка i-то­го вы­хо­да ячей­ки, i O;

7. π(G) пло­щадь ячей­ки со­дер­жа­щее все тран­зи­сто­ры из G;

8. πmax и μmax мак­си­маль­ное до­пус­ти­мые пло­щадь и ма­те­ма­ти­че­ское ожи­да­ние за­дер­жек вы­хо­дов ячей­ки.

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

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

В параграфе 3.1 анализируется, почему оп­­т­и­­ми­­з­а­­ционная за­да­ча с ис­поль­зо­ва­ни­ем толь­ко од­но­го кри­те­рия име­ет не­дос­тат­ки для применения в маршруте проектирования САПР микроэлектроники:

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

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

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

Та­ким об­ра­зом, не­об­хо­дим ме­тод ко­то­рый:

  • од­но­вре­мен­но оп­ти­ми­зи­ру­ет по не­сколь­ким кри­те­ри­ям;

  • мак­си­маль­но не тре­бу­ет вме­ша­тель­ст­ва поль­зо­ва­те­ля;

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

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

В параграфе 3.2 рассматривается генетический алгоритм многокритериальной оптимизации.

Ал­го­ритм 1 ГА Ал­го­ритм

pop = GenerateInitialPopulation

while generation ≤ max generation do

rank = Ranking(pop)

fitness = Fitness (pop, rank)

for i = 1 to N step 2 do

parent1 = Selection(pop, fitness)

parent2 = Selection(pop, fitness)

(child1, child2) = Crossover(parent1, parent2)

newpopi = Mutation(child1)

newpopi+1 = Mutation(child2)

end for

pop = newpop

generation = generation + 1

end while

final rank = Ranking(pop)

Solutions = popi, i final ranki == 1

return Solutions


Ал­го­ритм 1 пред­став­ля­ет схе­му ге­не­ти­че­ско­го ал­го­рит­ма мно­го­кри­те­ри­аль­ной оп­ти­ми­за­ци­он­ной за­да­чи (2)

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

Существенным отличием от известных алгоритмов является опе­ра­тор GenerateInitialPopulation. Этот про­цесс ге­не­ри­ру­ет мас­сив pop, раз­мер­но­сти N×P, ко­то­рая со­дер­жит N (раз­мер по­пу­ля­ции) чле­нов, ка­ж­дая из ко­то­рых яв­ля­ет­ся век­то­ром дли­ны P. Обыч­но по­пу­ля­ция соз­да­ет­ся с по­мо­щью рав­но­мер­но рас­пре­де­лен­ных слу­чай­ных ве­ли­чин, при ус­ло­вии, что ка­ж­дая xj [x'j, x''j ]. Од­на­ко вы­бор на­чаль­ной по­пу­ля­ции мо­жет су­ще­ст­вен­но ус­ко­рить схо­ди­мость про­цес­са. Из рав­но­мер­но рас­пре­де­лен­ных слу­чай­ных ве­ли­чин, мы для ре­ше­ния на­шей за­да­чи вы­би­ра­ем ЛПτ-по­сле­до­ва­тель­но­сти Со­бо­ля4. Как по­ка­зы­ва­ют ис­сле­до­ва­ния, ос­нов­ное свой­ст­во ЛПτ-по­сле­до­ва­тель­но­сти за­клю­ча­ет­ся в том, что они хо­ро­шо по­кры­ва­ют ма­ло­мер­ные про­ек­ции мно­го­мер­но­го ку­ба. На­при­мер, про­ек­ции на все трёх­мер­ные гра­ни сто­мер­но­го ку­ба пер­вых 128 чле­нов ЛПτ-по­­с­­ле­­д­о­ва­­т­ель­но­сти хо­ро­шо по­кры­ва­ют ка­ж­дую трёх­мер­ную грань, но пло­хо по­кры­ва­ют сам куб в си­лу его боль­шой раз­мер­но­сти. С пра­­к­­ти­­че­с­кой то­­ч­ки зре­ния, это оз­на­ча­ет, что ЛПτ-по­­с­­ле­­д­о­ва­­т­ель­но­сти хо­ро­шо сра­ба­ты­ва­ют для оты­ска­ния экс­тре­му­мов функ­ций, су­ще­ст­вен­но за­ви­ся­щих от не­боль­шо­го чи­­с­ла сво­их ар­гу­мен­тов, т.е. , что функ­ция


P(l1, l2,… ln) = P*(li1, li2,… lik) + g(l1, l2,… ln), (1)


где k<n, и P*>>g. Так­же, в си­лу сво­ей рав­но­мер­ной рас­пре­де­лён­но­сти, они обес­пе­чи­ва­ют луч­шую схо­ди­мость, чем псев­до­слу­чай­ные по­­с­­ле­­д­о­ва­­т­ель­но­сти.

По­ка­зывается, что, ин­те­ре­сую­щие нас функ­ции об­­л­а­­дают свой­ст­вом (1). Для та­кой функ­ции ре­ше­ние за­да­чи по­ис­ка экс­тре­му­ма бли­­з­ко к ги­пер­п­ло­ско­сти. Это по­зво­лит ГА бы­ст­рее схо­дит­ся и да­же при от­сут­ствии Па­ре­то-оп­ти­маль­ных ре­ше­ний, дать при­ем­ле­мые для ин­же­не­ра-про­ек­ти­ров­щи­ка ре­ше­ния. При­водятся ал­го­рит­мы бы­ст­рой ге­не­ра­ции ЛПτ-по­­с­­ле­­д­о­ва­­т­ель­но­стей и их срав­не­ние с дру­ги­ми рав­но­мер­но рас­пре­де­лен­ны­ми по­сле­до­ва­тель­но­стя­ми слу­чай­ных ве­ли­чин.

В параграфе 3.3 рассматривается расширение алгоритма 1 в виде клеточного многокритериального генетического алгоритма, расширения алгоритма NSGAII, эффективно используемого для параллельной реализации.

Алгоритм 2: Параллельный ГА

1. proc Evolve(mocell)

2. Pareto front = Create PFront()

3. while !StopCondition() do

4. for individual 1 until mocell.popSize do

5. neighbors GetNeighbors(mocell,position(individual));

6. parents Select(neighbors);

7. offspring Recombination(mocell.Pc,parents);

8. offspring Mutation(mocell.Pm,offspring);

9. Evaluate(offspring);

10. Insert(position(individual),offspring,mocell,aux population);

11. InsertInParetoFront (individual, Pareto front);

12. end for

13. mocell.population aux population;

14. mocell.population Feedback (mocell,Pareto Front);

15. end while

16. end proc Evolve;

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

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

В параграфе 4.1 перечисляются программные компоненты, реализованные при работе над диссертацией: LPtau – модуль ЛП-поиска, GAO – генетическая оптимизация, LME – Layout modification engine, модуль реализующий комбинированный алгоритм, а также реализующий компактизацию после мидификации топологии, LGE – Layout Generation Engine, модуль реализующий генерацию топологии по оптимизированному списку цепей, DB – хранилище данных, DRC&LVS – модуль финальной проверки на соответствие технологическим нормам проектирования, SPICE – модуль стыковки моделирования на уровне списка цепей.

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

Параграф 4.3 посвящен реализации ЛП-поиска и генетического алгоритмов.

В параграфе 4.4 описана интеграция модулей в единую программную систему.

Параграф 4.5 посвящен оценке экспериментальных результатов от реализации предложенных методов. Экспериментальные результаты проводились на промышленной библиотеке TSMC 0.13мкм с 400 ячейками, по технологии обычный КМОП. Наибольший эффект получался при оптимизации комбинационных схем.

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

Ячей­ка

Кол-во тран­зист.

Пло­щадь

max(σ/μ)

Энерго­потребл.

Вре­мя раб. с

1

6

26.17

0.07

0.0914

3.76







33.51

0.04

0.0851










53.82

0.02

0.0746










72.61

0.01

0.0701










95.98

0.01

0.0672




2

160

768.61

0.05

6.1245

56.34







1053.99

0.03

5.1341










2132.12

0.01

3.2515










2912.14

0.01

3.0101










3134.45

0.01

2.8642




Таблица. 1. Пример оптимизации для двух ячеек.

Результаты общей оптимизации показывают, что

  • для 20% ячеек, энергопотребление может снижаться до 20%

  • для 25-30 % ячеек – до 10-12%

  • и менее 10% для остальных.

Данные результаты позволяют конкурировать на рынке посттопологической оптимизации с такими инструментами как BlazeDFM МО.


В Заключении сформулированы основные результаты работы:

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

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

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

4. Разработаны при участии автора в качестве руководителя или исполнителя следующие подсистемы программного комплекса Cell Compiler: LPtau, GA, LGE, DRC&LVS.


По теме диссертации опубликованы следующие работы:

В изданиях, рекомендованныx Перечнем ВАК Министерства образования и науки Российской Федерации:

  1. Мелик-Адамян А.Ф. Многокритериальная оптимизация КМОП-схем в субмикронных технологиях. Известия ТТИ ЮФУ, №3, 2009. – с. ?? – ??.

  2. Рыжов А.П., Мелик-Адамян А.Ф. Применение генетических алгоритмов в некоторых задачах многокритериальной оптимизации проектирования СБИС. // Нечеткие системы и мягкие вычисления. № 3, 2008, – с. ?? – ??

  3. Meлик-Адамян А.Ф. Применение генетических алгоритмов в задачах оптимизации физического проектирования микроэлектроники. // Научно-техническая информация. Серия 2, № 8 Информационные процессы и системы / Всероссийский институт научной и технической информации, – с. 143-153, – 2009.

Другие публикации

  1. Мелик-Адамян А.Ф., Кондратьева А.К., Халимов А.К. Оптимизация статического тока утечки для библиотечных КМОП-схемах в субмикронных технологиях. // Научные исследования № 1 (1), Труды российских ученых, 2008.

  2. Мелик-Адамян А.Ф., Кондратьева А.К., Халимов А.К. Оптимизация стандартных ячеек ЛПτ-последовательностями. // В трудах 51-ой Научной конференции МФТИ, 2008.

  3. Мелик-Адамян А.Ф. Автоматизированная система генерации и оптимизации стандартных ячеек Cell Compiler. // ИТМ и ВТ РАН, 2008

  4. А. Aslyan, A. Melik-Adamyan, On Method of Yield Optimization via Compac­tion // Proceedings of Journal of Physical Design Automation (to be published), Mentor Graphics, 2009.

  5. Мелик-Адамян А.Ф. Методы многокритериальной оптимизации в задачах физического проектирования микроэлектроники. // Радиоэлек­тронная промышленность России, 2009.



Лиц. на издат. деят. Б848421 от 03.11.2000 г. Подписано в печать 14.11.2008 г.

Формат 60x90 1/16 усл. печ. л. Компьютерный набор.

Гарнитура Times New Roman.

Отпечатано на ризографе. Усл. печ. л. – 1,3. Уч.-изд. л. – 1,1.

Тираж 100 экз. Заказ № 259


ИПК БГПУ 450000, г. Москва, ул. Октябрьской, 3а

1 V. Oklobdzija, Digital Design and Fabrication, CRC Press, 2008.


2 C. Piguet, Low Power Electronics Design, CRC Press, 2007.

3 M. Pan, N. Chu, H. Zhou, Timing yield estimation using statistical static timing analysis, in ISCS, 2005.

4 Соболь И.М, Статников, Р.Б. Выбор оптимальных параметров в задачах со многими критериями. – , с.160, - Москва, Дрофа, 2006.

Тверь — 2009

Добавить документ в свой блог или на сайт

Похожие:

Разместите кнопку на своём сайте:
cat.convdocs.org


База данных защищена авторским правом ©cat.convdocs.org 2012
обратиться к администрации
cat.convdocs.org
Главная страница