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

Методы и алгоритмы

многокритериальной оП­­­тимизации

стандартных ячеек В субмикронных

технологиях ПРОЕКТИРОВАНИЯ СБИС

Специальность: 05.13.01 Системный анализ,

управление и обработка информации

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

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

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

дoктор технических наук, доцент

Рыжов А.П.

Оглавление

ВВЕДЕНИЕ 4

Системный анализ стандартных КМОП-элементов 11

1.1 Эволюция технологии производства КМОП изделий 11

1.2 Утечки в нанометровых технологиях КМОП 13

1.3 Компоненты тока утечки 16

1.3.1 Обратный ток смещения перехода p-n (I1) 18

1.3.2 Слабая инверсия (I2) 19

1.3.3 Стоко-вызванная утечка через барьер DIBL (I3) 19

1.3.4 Утечка сток-затвор (I4) 20

1.3.5 Пробой (I5) 21

1.3.6 Эффект узкой ширины (I6) 21

1.3.7 Туннелирование оксида затвора (I7) 22

1.3.8 Иньекция горячих носителей (I8) 22

1.4 Токи утечки в ячейках 24

1.5 Методы борьбы с токами утечек 28

1.6 Уровень выхода годных и связанные с ним проблемы 29

1.7 Библиотеки стандартных ячеек 35

1.8 Быстродействие и площадь КМОП-схем Ошибка! Закладка не определена.

1.9 Постановка задачи 36

1.9.1 Математическая постановка 37

1.10 Выводы по главе 38

ГЛАВА 2 39

НАУЧНО-МЕТОДИЧЕСКИЕ ПОЛОЖЕНИЯ ПО ОПТИМИЗАЦИИ ЯЧЕЕК СТАНДАРТНЫХ БИБЛИОТЕК ЭЛЕМЕНТОВ 39

2.1 Методы оптимизации в задачах проектирования СБИС 39

2.1.1 Традиционные методы оптимизации 39

2.2. Эволюционные методы оптимизации 47

2.1 Математическая модель ячейки стандартной библиотеки элементов 66

2.1 Математические модели характеристик стандартных библиотек элементов 66

2.1.1 Характеристика площади 66

2.1.2 Характеристика статического энергопотребления 66

2.1.3 Характеристика динамического энергоптребления 66

2.1.4 Характеристика задержки 66

2.1.5 Характеристика уровня выхода годных 66

2.1.6 Характеристика длины трассировки 66

2.1.7 Характеристика плотности размещения 66

Выводы по главе 66

ГЛАВА 3 67

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

3.1 Программная система для решения задач многокритериальной оптимизации стандартный ячеек 67

3.1.2 Функциональная структура 68

3.1.3 Эксплуатация и применение программной системы 70

3.2 Задача принятия решений при оптимизации блоков для проектирования системы-на-кристалле 71

3.2.1 Общая постановка задачи принятия решений 71

3.1 сдфсдфсф 71

3.1 Компактизация 73

1 Algorithm Description 73

1.1 Initialization 73

1.2 Layout preprocessing 73

1.3 Layout graph construction 73

1.4 Constraint (graph edge) generation 75

1.4.1 Geometrical interpretation of graph edges 75

1.4.2 Constraint generation 76

1.5 Actual compaction 86

1.5.1 Dynamic slack finding for the nodes 86

1.5.2 Pushing of the cell boundary (origin node) towards the other boundary (origin) 89

1.6 Layout postprocessing 91

1.7 Finalizing 94

2 Compaction usage, issues and future perspectives 94

2.1 Usage 94

2.2 Issues 94

2.3 Future perspectives 95

3.1 сдфсдфсф 95

Выводы по главе 95

ЗАКЛЮЧЕНИЕ 97

ЛИТЕРАТУРА 99

ВВЕДЕНИЕ

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

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

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

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

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

Другой, не менее важной проблемой является задача повышения уровня выхода годных (УВГ, 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 таблицы.

ГЛАВА 1

Системный анализ проектирования СБИС на основе КМОП-технологии

1. Введение

КМОП (комплементарная логика на транзисторах металл-оксид-полу­проводник; англ. CMOS, Complementary metal-oxide semi­conductor) — технология построения электронных схем, использующая полевые транзисторы с изолированным затвором с каналами разной проводимости. Отличительной особенностью функционирования схем КМОП по сравнению с биполярными технологиями является очень малое энергопотребление в статическом режиме (до недавнего времени этим фактором пренебрегали). А отличительной особенностью структуры КМОП является наличие как n-, так и p-канальных полевых транзисторов, что приводит к более высокому быстродействию и меньшему энергопотреблению. Однако при этом характеризуются более сложным технологическим процессом изготовления.

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

2. Маршрут проектирования СБИС

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

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

Рис. Типичный маршрут проектирования СБИС и уровни абстракции

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

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

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

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

3. Эволюция технологии производства КМОП изделий

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

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

Рисунок 2: Графики соотношения видов энергопотребления в СБИС по технологиям

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

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

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

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

4. Проблема утечек в субмикронных технологиях КМОП

1. Основные проблемы

Для технологий комплементарного МОП-транзистора (КМОП), при их дальнейшем усовершенствовании, роль новых физических явлений, становится существенным, особенно для технологий энергосбережения [ ]. В работах [ ] указывается, что энергопотребление станет одним из важнейшич факторов в технологических нормах проектирования 45нм и ниже. На конференции DAC’2008 вошел в обиход и стал устоявшимся термин Design for Power (DFP) – проектирование с учетом энергосбережения. Международная дорожная карта по полупроводниковой технологии (International Technology Roadmap for Semiconductors (ITRS) [ ]), указывает на основные проблемы в области борьбы с энергопотреблением

1. Подпороговые утечки
2. Туннельные токи
3. Статистическая дисперсия материала
4. Истощение поликремния и квантовые эффекты

Далее, вкратце, рассмотрим все эти проблемы и связанные с ними вопросы проектирования изделий и возможные решение проблем.

2. Основные вехи развития – дорожная карта ITRS

Переход от одной технологии к другой, масштабированием физических размеров, всегда был, и остается основным способом уменьшения энерго­потрeбления. Oсновные паразитические емкости (вентили и взаимосвязи) уменьшаются, активный ток увеличивается, и следовательно, сопоставимую производительность можно получить при меньшем напряжении питания. Переход на новые технологии уменьшает значения напряжения питания (Vdd), порогового напряжения (VT) и толщины оксида вентиля (TOx). Начиная с технологии 0.18 мкм оказалось, что изготовление транзистора с хорошим активным током (Ion) и маленьким током утечки (Ioff) становиться все труднее. Для этого былы введены два семейства транзисторов: высокоскоростных и малотекущих. Пороговые напряжения для этих двух семейств формируются разным образом, благодоря различным методам допирования канала транзистора. Но оказалось, что и два семейства недостаточно для совремнных приложений. Тогда, ITRS в 2001 году ввела три основные группы транзисторов:

1. Высокопроизводительные (HP – High Performance)

2. Малоточные (LOP – Low Operating Power)

3. Малотекущие (LSTP – Low Standby Power)

На этом этапе не только допирование канала разное, но и толщина оксида затвора тоже. Таблица ? суммирует основные характеристики текущих и будущих транзисторов.

5. Ток утечки в МОП-транзисторе

Ток утечки транзистора в состоянии выключен (Iоff), это ток текущий через сток, когда напряжение затвор-исток равен нулю. Существуют два основных вида утечек – подпороговый ток утечки и утечки затвора.

1.5.1 Подпороговый ток утечки

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

где a – некая константа, – эффективная длина затвора, – напряжение затвора, VТ – пороговое напряжение, kT/q – напряжение тепловых шумов. В типичном сценарии уменьшения геометрических размеров, электрические поля сохраняются при уменьшении напряжения и геометрических размеров на один и тот же множитель и увличении уровня допирования на тот же множитель. Несмотря на то что Iоff экспоненциально увеличивается при уменьшении VТ, статическое энергопотребление имеет некую нижнюю грань понижения, при уменьшении порогового напряжения транзистора. И несмотря на то, что динамические характеристики транзистора непосредственно связаны с отношением VDD /VТ, напряжение питания тоже не понижается так легко. Соответственно, в дорожной карте ITRS напряжение питания не уменьшается с той же скоростью, что и геометрические размеры затворса. Это влечет за собой невозможность иметь транзистор одновременно с хорошым активным током и током утечки. Для уменьшения активного тока используется понижение частоты, разные напряжения питания и другие методы управления током утечки [][]

1.5.2 Ток утечки затвора

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

Рис. Ток утечки, показывающий DIBL, GIDL, слабую инверсию и p-n

обратный стыковой компонентны в 0,13 мкм технологии

На рис. Показаны графики зависимости тока утечек в затворе (ID) относительно напряжения затвора (VG). Значение ID относительно VG является важной величиной в состояниях насыщения и линейного смещения. Измеряемые транзисторы были взяты из процесса TSMC 130нм, КМОП технология, с Leff < 100нм, и номинальным напряжением 1,2В [ ].

Существуют 8 механизмов тока утечки затвора показанные на рис..

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

I1 это утечка при обратном смещении в стыке p-n, вызванная барьерной эмиссией вместе с небольшим сдвигом носителей и межзонным сдвигом туннелирования от оксидно-поликремниевой поверхности, I2 это слабо инверсионный ток, I3 это стоко-вызванная утечка через барьер (DIBL), I4 затворно вызванная утечка стока (GIDL), I5 – утечка канала, I5 – утечка через поверхность канала из-за узости канала, I7 – утечка через оксид, и I8 – утечка зерез затвор вследсвтии вхождения горячих носителей заряда. Токи I1 – I6 возникают, когда транзистор выключен, а I7 (туннелирование оксида) возникает в рабочем состоянии. I8 возникает как в выключенном состоянии, так и при переходном из включенного в выключенное. Более детально механизмы воникновения токов утечек рассмотрены в [].

1.5.3 Компоненты тока утечки

Рис. показывает экспоненциальную зависимость тока утечки от эффективной длины канала затвора.

Рис. Зависимость утечки от эффективной длины канала

- подпороговые утечки, - утечки затвора

Рис. показывает относительный вклад каждой компоненты в статический ток утечки для типичной КМОП технологии 130 нм. Мы видим, что при номинальном напряжении 1.5В, DIBL является основным компонентом тока утечки (он повышает подпороговоый ток и ток слабой инверсии). При предельном напряжении 2.2В, доминирует GIDL.

6. Ток утечки в ячейках

В этом параграфе рассмотрим методы расчета и аппроксимации тока утечки для основных КМОП ячеек. КМОП ячейки составляются серией параллельной комбинации сети МОП транзисторов. Это означает, что ток утечки зависит также от входного вектора значений и состояния ячейки: при изменении входов, цонфигурация транзисторов также меняется. Если рассматривать только подпороговые утечки, то зависимости хорошо изучены и представлены в работах [ ], включая хорошо известный эффект стекирования. Но при учитывании токов затвора, расчет тока утечки затрудняется зависимостью подпорогового и затворного тока от состояния ячейки. Как было показано выше, подпороговый ток утечки ISUBTH и ток утечки затвора IG взаимозависимы, и должны анализироваться вместе. В настоящее время этот вопросу посвещены множество работ [ ].

На уровне ячейки энергопотребление для каждого входного вектора вычисляется на основ SPICE моделирования [] с использованием моделей транзисторов BSIM4 с добавлением антипараллельных источников тока с экспоненциальной зависимостью [] такая модель очень полезна, также для выявления токов протекающих через несколько затворов. Другие модели описанные в [ ] выдают аналогичный результат. Например, рассмотрим цепочку из нескольких инверторов на рис. 7. Представлены две возможные ситуации : входной VG низкий (первый инвертер) и входной VG высок (второй инвертер). Все туннелированные пути также показаны. В данном случае для инвертора с высоким VG, подпороговый ток n-трансизтора соединяется с током затвора предыдущего транзистора, тогда как предыдущие,

Рис.. Серия из транзисторов показывающая токи утечек

транзисторы с высоким VG комбинируют подпороговый ток p-транзистора с током затовра следующего транзистора. В данном случае подпороговый и затворные токи могут быть вычисленные независимо.

Проанализируем поведение двухвходовой НЕ-И (NAND) ячейки, рис. 9. Вход 11 приводит к выходу 0, и ток утечки есть простая сумма подпорогового тока и тока I4 для n и p транзисторов. Ток утечки течет от VDD к земле GND.

Рис. 8. Ячейка НЕ-И с токами утечки и анти-параллельными источниками токов

Для входов 00-01-10 выход равен 1. В этом случае, путь до GND блокирован одним или двумя транзисторами. Рассмотрим варианты более детально.

1. AB = 10. Транзистор N1 (соединенный с землей) включен, а транзистор N2 (соединенный с VDD через P транзистор) выключен. В этом случае туннельные токо и подпороговеы токи могут быть опять вычислены отдельно. Заметьте, что управляющий вентиль и НЕ-И вентиль совместно используют один и тот же ток.

2. AB = 01. Транзистор N1 (соединенный с землей) выключен, а транзистор N2 (соединенный с VDD через P транзистор) включен. В этом случае, сток транзистора N1 держиться на значении VDD – VТ. Таким образом, напражение применяемое к истоку тока IGS (N2) на порядок меньше предыдущего случая, тогда как, IGD (N1) который тоже равен VDD – VТ, не смотря на то, что тоже меньше предыдущего случая не может быть опущен.

3. AB = 00. Оба транзистора выключены. В этом случае, подпороговый ток проходит через стековый эффект, и внутренние узлы имеют напряжение в диапазоне от ·VDD = 60-100 мВ ( моделирует DIBL эффект). Туннельные токи IGD (N1) и ISG (N2) на порядок меньше чем в слуае 11, и могут быть опущены.

Анализ случаев для трехвходового НЕ-И, аналогичен рассмотренному выше, кроме случая 010. В этом случае, детально рассмотренным в [ ], ток в стеке повышает внутреннее напряжение, что приводит к понижению подпорогового тока, оставляющий общий ток утечки относительно незименным. Эти примеры показывают, что токи утечки существенно могут повлиять на производительность ячейки и анализ токов утечки должен быть обязательным условием проектирования ячейки.

Существуют разные методы оценки и анализа подпороговых и затворных токов утечки, относительно состояния ячейки [ ]. В целом, для очень больших схем, было выявлено, что структурные зависимости между ячейками, и следовательно между токами утечек уменьшаетя с расстоянием вентилей друг от друга. А также, что распределение токов утечки в больших схемах Гауссово или близко к Гауссовому [ ]. Другими словами, для больших схем с подпороговым током утечки, как основным, некоторые части могут быть независимо установлены в некоторое логическое состояние и контролировать утечки [ ]. С введением в рассмотрение затворных токов, возникают новые трудности. Во-первых, существенная зависимость от состояния ячейки, так как, значение подпорогового тока зависит только от количества транзситоров, затворный ток зависит от расположения выключенного транзистора в стеке [ ]. Во-вторых, вопрос о токах протекающих в больших схемах, со сложными ячейками, и структурными зависимостями между частями не исследован достаточно для хороших оценок.

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

7. Методы борьбы с токами утечек

Существует множество методологий проектирования для уменьшениия токов утечек и энергосбережния (Design for Power) []. Они применимы на разных уровнях абстракции, начиная с систмного уровня, далее на архитектурном, логическом, структурном и топологическом. Чем выше абстракция, тем больше можно влиять и больше выиграть в энергопотреблении. Но все методы на высоком уровне абстракции сильно зависят от приложения, и наоборот, чем ниже уровень абстракции тем меньше можнo выиграть, но тем универсальнее методы.

В основном используются такие методы как понижение напряжения питания [], уменьшение паразитных емкостей [ ], острова напряжения [], многопороговое проектирование [], clock gating [], динамическое управление питанием[ ]. Эти техники являются стандартными и показали свою эффективность. Для реализации этих техник, в основном, используются программные маршруты проектирования от компаний Synopsys, Cadence и Magma. Эти инструменты могут работать на всех уровнях маршрута проектирования: уровня регистровых передач (RTL) до топологического уровня (GDSII). Для эффективной работы эти инструменты должны быть интегрированы и должны распознавать сложные взаимосвязи в проектах. Так как в работе используются инструменты размещения и трассировки, логического синтеза, временной проверки, анализа целостности и т.д., они должны использовать одни и те же данные и должны иметь доступ к единой системе хранения и обработки данных о проекте. Изменения, производимые одним инструментом, должны быть немедленно доступны другим.

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

8. Уровень выхода годных и связанные с ним проблемы

1. Общие понятия УВГ

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

Ytotal = Yline Ybatch,

где: Yline – процент полупроводниковых подложек, которые были успешно произведены на производственной линии, а Ybatch – процент ИС на подложке, которые полностью функциональны. Чем выше УВГ, тем больше подложек может производить фабрика. Если компонента Yline контролируется фабрикой-производителем, то Ybatch может управлятся также инженером, с помощью соответствующего инструментария САПР.

Компонента Ybatch состоит из следующих частей:

• Существенная потеря УВГ (catastrophic yield loss). Эта часть состоит из функциональных дефектов в следствие которых ИС полностью неработоспособен. Причиной таких проблем являются ошибки типа замыкание (short defect) или размыкание (open defect). Ошибки такого рода могут быть предсказаны с помощью аппарата критических площадей [];
• Параметрическая потеря УВГ. Ошибки такого рода, означают, что ИС функционально работоспособна, однако не удовлетворяет критериям энергопотребления или быстродействия. Причиной таких ошибок являются вариации в параметрах ИС, такие что их специфическое распределение в ИС приводит к отклонению от спецификации. Например, некоторая часть ИС может функционировать в узком диапазоне напряжения питания VDD, но не в специфицированном диапазоне. Другим примером, является частичная функциональность из-за токов утечек, которые могут возникать из-за вариаций параметров процессов производства. Примером ИС, которые сильно подвержены параметрическим потерям УВГ, являются микропроцессоры. Во время тестирования они микропроцессоры сортируются по быстродействию и энергопотреблению. Заказные ИС (ASIC - Application Specific Integrated Circuit), с другой стороны не могут быть классифицированы, так как должны удовлетворять спецификациям. Такие интегральные схемы проектируюся с большим запасом прочности для функциональных параметров.
• Третьим источником потери УВГ является потеря УВГ из-за проблем тестирования. Практические тесты не могут идентифицировать все дефекты илипотенциальные дефекты, и поэтому попадают в отдельный класс дефектов приводящих к потере УВГ. Здесь мы не будем рассматривать этот аспект, так как он не связан с вопросами физического проектирования ИС.

Рис. Таксономия потери УВГ. (перевести на русиш)

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

• Случайные дефекты. Это случайно распределенные дефекты, возникающие из-за попадания пылевых частичек на подложку.
• Систематические дефекты. Этот тип дефектов предсказуем, и состоит, например, из ошибок химическо-механической полировки (CMP – chemical mechanical polishing) или разрушение фоторезисторного шаблона.

Важно понимать что и случайные и систематические дефекты могут быть причиной как параметрической, так и существенной потери УВГ. Например, литографическая вариация [ ], которая попадает в класс систематических ошибок, может привести к недостаточному образованию контура затвора (кремний на диффузионном слое) МОП-транзистора, что может привсти к функциональной ошибке.

2. Рассматриваемые ограничения

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

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

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

3. Определение УВГ

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

УВГ ИС с учетом случайных дефектов определяется уравнением:

где, Yi УВГ случайных дефектов связанный с i-тым шагом производства []. В дальнейшем мы будем опускать индекс и тракторвать как УВГ отдельного шага производства. Есть несколько моделей расчета УВГ случайных дефектов: таких как модели Сида, модели Пуассона, отрицательной биномиальной модели, модели Мерфи и т.д. [ - ]. Основным различием между моделями является выбор статистика покрывающая распределение дефектов на площади ИС. Например, с помощью Пуассоновской модели, УВГ определяется следующим образом:

где:

d – среднее количество дефектов на единицу площади;

Ac – критическая площадь;

– параметр кластеризации, исправляющая эффект кластеризации дефектов;

Ac критическая площадь, обозначающая чуствительность ИС к случайным дефектам, вычисляемая следующим образом []:

где:

D(r) – функция плотности размера дефекта;

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

Функция плотности обычно определяется следующим образом []:

,

где:

p,q – вещественные числа;

C – (q–1)(p+1)/(q+p);;

r0, – минимально допустимая дистанция между элементами топологии.

Рис. Примеры потерь УВГ. Все типы (перевести на русиш)

Рис ? иллюстрирует пониятие критической плщади для двух проводников.

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

9. Библиотеки стандартных ячеек

Стандартные библиотеки ячеек, это коллекция ячеек предоставляющих базовые логические функции с базовыми ячейками хранения состояний. В типичной стандартной библиотеке существуют 400 и более разновидностей ячеек. Такие библиотеки предоставляют все полупроводниковые фабрики, как основу проектирования []. А также сторонние компании, которые предоставляют для полупроводниковых фабрик оптимизированные по применениям библиотеки [ ]. Эти применения обычно подразумевают наличие нескольких высокоскоростных библиотек, энергосберегающих библиотек, и малоточных библиотек. Причем модели транзисторов могут использоваться как стандартные, предоставляемые фабрикой, так и заказные.

Для инженера очевично, что САПР на разных уровнях абстракции, где используется библиотека стандартных ячеек может сильно влиять на характеристики проектируемого СБИС. Так, например, на уровне логического синтеза, характеристики СБИС можно улучшить, при наличии выбора однотипных ячеек с разными параметрами внутри библиотеки. Так, компания Интел активно использует такой подход при проектировании процессоров.[]

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

Рис. Характеристики проектируемых ИС при применении

стандартной и оптимизированных библиотек

В стандартном маршруте проектирования библиотеки стандартных элементов являются неизменяемыми объектами. Они поставляются извне и используются при проектировании как есть. Это связано с тем, что библиотеки сильно зависят от технологического процесса производства. Фабрики производители тестируют библиотеки перед их выпуском на разные параметры и удостоверяют, что выпущены библиотеки соответствуют критериям произовдства. Однако основным примитивом произвдства для фабрики является транзистор. Модель транзистора поставляется в составе библиотек и все его характеристики вычисляются на основе программ типа SPICE []. Возникает возможность изменения библиотек на основе модели транзисторов. Такой подход нов, и позволяет изменять характерстики СБИС не возвращаясь на более высокие уровни абстракции. Это так называемая пост-топологическая оптимизация. Пионерами в этой области являются компании Blaze DFM с САПР BlazeMO и компания Nangate с САПР Design Optimizer[][].

Как было показано выше, оптимизацию характеристик СБИС можно проводить на разных этапах маршрута проектирования. Этим вопросам уделено много внимания и публикаций, см., например [][][][]. Однако, как известно целевые характеристики СБИС, такие как энергопотребление, площадь, производительность ухудщаются, по мере снижения абстракции по ходу продвижения по маршруту проектирования. Результирующая топология может по характеристикам в разы отличаться от целевых. Этому вопросу и применению более точных методик оценок и проектирования посвящены множество публикаций и разработанных методологий проектирования [ ][] [ ]. Их метод основан на идентификации критических путей в топологии и оптимизации некритических ячеек на уровне поликремния утолщением на заданный технологический шаг транзисторов, например для технологии 65нм шаг 2 нм. Так, как известно [][] что понижение энергопотребления, положительно влияет на уровень выхода годных, уменьшая критические площади, то такой подход жизнеспособен и на практике доказал свою применимость. Однако как было показано в [ ][ ] геометрические операции на уровне поликремния, с нарушением топологических правил проектирования, могут как улучшить, так и ухудшить уровень выхода годных, и как следствие, косвенным образом ухудшить энергопотребление и производительность. В предлагаемой методике, инженер лишен возможностей контроля и оценок изменений, и всю ответственность берет на себя выпускающая фабрика. Однако сама идея оптимизации топологии для энергосбережения на уровне поликремния, хоть и стара, но актуальна, так как позволяет существенно улучшать характеристики СБИС, особенно в технологиях ниже 90нм.

Оптимизация характеристик СБИС с помощью изменений в библиотеке является хотя и нестандартной, но актуальной темой исследований[][].

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

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

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

Для постановки задачи рассмотрим следующие ограничения на стандартную ячейку:

• Мы будем рассматривать только вариации внутри подложки, на которые можно влиять с помощью инструментов САПР физического уровня. Это соотвествует значением p=3, q=1 в функции распределения (?) [].
• В модели УВГ (?) используется обратная биномиальная модель.
• Вместо интегрирования в (?) используется простое суммирования от r0 до 6r0.
• Не будем рассматривать стекированные транзисторы внутри ячейки, что позволит упростить модель тока утечки.

Сопоставим ячейке ненаправленный ациклический граф G = (N,E) следующим образом. Введем нумерацию на множестве транзисторов. Множество N={1,…,n}, соответсвующее множеству узлов в графе, отображается взаимнооднозначным образом на множество транзисторов в ячейке. Таким образом транзистору i соответствует iN. Если транзистор i соединен с транзистором j, то ребро,. Через хi обозначим длину транзистора i.

Рис. Схема ячейки 2И-НЕ и соостветсвующий ему граф

Введем понятие критериальных функций. Таких функций у нас будет 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,

А min,

Y max

P Pmax

T Tmax

A Amax

Y Ymin

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

11. Выводы по главе

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

ГЛАВА 2

НАУЧНО-МЕТОДИЧЕСКИЕ ПОЛОЖЕНИЯ ПО ОПТИМИЗАЦИИ ЯЧЕЕК СТАНДАРТНЫХ БИБЛИОТЕК ЭЛЕМЕНТОВ

В первой главе была рассмотрена…

2.1 Методы оптимизации в задачах проектирования СБИС

2.1.1 Традиционные методы оптимизации

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

Под оптимизационной задачей понимается задача, в ко­торой необходимо найти решение, в некотором смысле наи­лучшее или оптимальное. Отметим, что наилучшего решения во всех смыслах быть не может. Оно может быть признано оптимальным на основе критерия (меры оценки исследуемого явления) или целевой функции (ЦФ). Существует большое количество оптимизационных задач. Они могут иметь различный характер. Однако постановка всех оптимизационных задач имеет много аналогий. Во-первых, в оптимизационных задачах часто указывается исходное множество альтернативных вариантов решений. Из этого множества выбирается оптимальное решение. Это исход­ное множество решений называется пространством решений. В дальнейшем его будем обозначать через М.

Во-вторых, некоторые решения априорно отвергаются в каче­стве «плохих». Другими словами, в пространстве решений зада­ются ограничения, которым должны удовлетворять оптимальные решения. Эти ограничения позволяют выделить в пространстве решений М некоторое подмножество М' тех решений, которые удовлетворяют заданным ограничениям Б.

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

Согласно [ ], критерий оптимальности — тот признак, по которому функционирование системы признается наилучшим из возможных вариантов ее функционирования. Дру­гими словами, критерий оптимальности — показатель, выража­ющий предельную меру экономического эффекта принимаемого решения для сравнительной оценки возможных альтернатив и выбора наилучшего из них. Критерий оптимальности носит количественный характер для того, чтобы качественный признак решения, выражаемый нечетким поня­тием «лучше-хуже», переводить в количественное определение «больше-меньше». Критерию оптимальности соответствует мате­матическая форма — целевая функция. Возможным выражени­ем критерия оптимальности является шкала оценок полезности, ранжирования, предпочтений и т. п.

Обозначим критерий следующим образом:

Q : М' R,

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

.

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

Решение, удовлетворяющее требованию оптимизации, называется оптимальным [ ].

Целью оптимизационной задачи является выбор допустимого или оптимального решения из множества альтернатив для до­стижения поставленной цели. Оптимизационная задача должна удовлетворять двум основным требованиям:

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

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

• область применения;
• содержание задачи;
• класс математических моделей.

Классификацию математических моделей проводят:

(а) по элементам модели: детерминированные и случайные; (b) по искомым переменным: непрерывные и дискретные; (с) по зависимостям, описывающим ЦФ, ограничениям и гра­ничным условиям: линейные и нелинейные. Комбинации элементов математических моделей приводят к различным классам оптимизационных задач. Наиболее про­стые — линейные оптимизационные задачи, однако, на практике чаще всего встречаются нелинейные. При решении оптимизаци­онных задач возможна одна из двух постановок:

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

— при заданном результате минимизировать используемые ре­сурсы.

В параграфе 3 рассмотрим также и многокритериальную оптимизационную задачу, где критериальное ограничение есть также кортеж из функций.

Максимум и минимум значения ЦФ в оптимизационных за­дачах объединяют определением экстремума. Наибольшее или наименьшее значение функции без учета того, где находится та­кое значение — внутри заданного интервала или на его границе, называют не экстремумом, а оптимумом. Оптимум — более об­щее понятие, чем экстремум. Экстремум есть не у всех функций, а в оптимизационных задачах оптимум есть всегда. Оптимум может быть локальным и глобальным.

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

Оптимальное решение называется точкой локального минимума (локальным решением), если для любой -окрестности точ­ки х*, истинно высказывание. Оптимальное значение называется точкой гло­бального минимума (глобальным решением), если ни в одной другой точке области допустимых решений функция Q(x) не принимает меньших значений. Следова­тельно, глобальный минимум — это наименьший из всех локаль­ных минимумов. Тогда квазиоптимальное решение — это одно из множества решений, попадающих в локальный экстремум, близкий к глобальному.

Экономичность математической модели характеризуют за­тратами вычислительных ресурсов ЭВМ при ее реализации. Ос­новными из таких ресурсов являются время выполнения Т и объем исполь­зуемой памяти V. Математическая модель считается тем экономичнее, чем меньше значения Т и V. Величину Т определяют как усредненное число операций, выполняемых при однократном обращении к модели. Величину V определяют в основном числом перемен­ных математической модели. Сравнение математических моделей по экономичности состоит в сравнении значений и В.

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

Обзор и анализ существующих подходов выявил следующее: многими авторами предприняты попытки сведения указанных выше задач к задачам целочисленного программирования. Были получены математические модели задач, к которым применялись стандартные методы оптимизации, такие как методы линейного, нелинейного, динамического программирования и др. [ ]. В данной постановке теоретически возможно получение глобального результата. В связи с тем, что стандартные мето­ды оптимизации не исключают возможности полного перебора, данные методы оказываются неприемлемыми даже для задач малой размерности (n > 102, где п — число транзисторов) при выполнении на рабочей станции инженера.

Одним из мощных методов целочисленного программирова­ния является метод ветвей и границ [ ].

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

В общем случае процесс поиска оптимального решения по схеме метода ветвей и границ выполняется следующим образом. Пусть на множестве решений А задан критерий оптимизации F и пусть цель оптимизации — нахождение минимума F. Процесс поиска заключается в последовательном целенаправленном раз­биении и усечении исходного множества решений А [ ].

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

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

Итак, на каждом шаге а множество не подвергавшихся ветвлению вершин объединяет­ся в множество Ва, называемое фронтом поиска.

Детально МВГ описан в [][][]

Отличительными особенностями метода ветвей и границ яв­ляются:

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

Это позволяет сделать эффективной методику отсечки в про­цессе поиска решения. Данные алгоритмы отличаются большой трудоемкостью и не гарантируют получения оптимального ре­зультата за полиномиальное время [ ].

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

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

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

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

Поиск решений в пространстве состояний удобно представить в виде ориентированного графа G = (Х,U), где X = {1,2,...,n} — множество вершин, каждая из которых отож­дествляется с одним из состояний. Наличие дуги свидетельствует о существовании некоторого оператора, преобразующего состояние, соответствующее вершине, в со­стояние, соответствующее вершине хj. Если дуга направлена от вершины хi к вершине хj, то говорят, что вершина хj является приемником или дочерней вершиной, а хi — родительской.

Разработка алгоритма поиска решений в пространстве состо­яний сводится к построению трех компонент (А, В, С).

Компонент А представляет собою структуру данных, описы­вающих конкретное состояние объекта проектирования.

Компонент В — это множество операторов, с помощью кото­рых производится переход от одного состояния к другому. Для каждого оператора имеется предварительное условие, которому это состояние либо удовлетворяет, либо нет. Если предваритель­ные условия выполняются, то оператор может быть применен. Использование этого оператора изменяет состояние объекта про­ектирования.

Компонент С — это стратегия поиска в пространстве состоя­ний.

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

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

Рисунок здесь

Рис. 2.2 Стратегия поиска.

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

2.2. Эволюционные методы оптимизации

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

2.2.1 Моделирование отжига.

В 1953 г. в работе [ ] предло­жена вычислительная процедура, воспроизводящая механизм от­жига металлов, для моделирования состояния равновесия слож­ных систем при заданной конечной «температуре». Идея переноса механизма отжига металлов на решение оптимизацион­ной задачи состоит в том, что процесс оптимизации связывают с некоторой температурой. На каждом шаге поиска случайным образом осуществляется малое изменение состояния объекта и вычисляется изменение Е энергии системы. Новая конфи­гурация системы принимается с вероятностью 1, если Е < 0, и с вероятностью, равной ехр(–Е/kt), если Е > 0. Эта проце­дура переносится на решение оптимизационных задач. При этом состояния физической системы заменяются изменением критерия качества, а значение Е заменяется обобщенным понятием «тем­пература» Т, которая может рассматриваться как управляющий параметр оптимизационной процедуры.

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

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

Задаются параметры, названия которых отражают историю возникновения метода. Это Tн, Tк — начальная и конечная тем­пература, t — интервал изменения температуры. Температура T меняется от Тн до Тк с интервалом t. Начальные значения Тн — высокое, Тк — низкое, обычно Тк = 0. При каждом значении Т выполняется заданное множество итераций. На каждой итерации выполняются действия, представленные на рис. 2.4. С помощью некоторого оператора D осуществляется пробное изменение со­стояния (решения).

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

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

Рис. 2.2. Алгоритм моделирования отжига

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

2.2.2 Генетические алгоритмы.

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

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

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

Отличительной особенностью генетических алгоритмов яв­ляется следующее. Оперирование производится не с решения­ми, а с их кодами. Каждому решению соответствует одна или несколько хромосом, которые представляют собой закодирован­ный генетический материал. Хромосомы состоят из генов. Каж­дый ген имеет свой локус или позицию в хромосоме. Гены могут иметь различные значения: число, строка, сектор, массив и др. Генетические алгоритмы работают на основе популяции, т.е. на множестве индивидуальностей. Решение получается на основе декодирования хромосом. Особенности строения хромосом и ге­нов, а также их значения, образуют генотип индивидуальности. Построенный на основе декодирования хромосом (индивидуаль­ности) объект образует фенотип [ ].

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

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

Рис. 2.3. Структура генетического алгоритма

Селекция — это процесс, посредством которого хромосомы, имеющие более высокое функциональное значение, получают большую возможность для репродукции, чем «слабые» хромосо­мы. Элементы, выбранные для селекции, обмениваются генети­ческим материалом, создавая потомков. Существует несколько основных видов селекции [ ].

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

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

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

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

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

Основной недостаток методов генетического поиска — большой объем вычислений на каждой итерации.

3. Методы альтернативной адаптации. В задачах САПР особый интерес представляет поисковая адаптация, основан­ная на использовании гибридных: итерационных и последовательных алгоритмов.

Трудности использования такого подхода связаны в первую очередь с проблемой представления исходной формулировки за­дачи в виде ???? системы [ ].

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

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

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

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

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

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

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

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

Для увеличения скорости генетического поиска осуществля­ется

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

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

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

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

После отработки генетического алгоритма в популяции, полу­ченной на последней генерации, отбирается несколько решений

(может быть, одно — лучшее), затем подключается адаптивный обучаю

Использование рассмотренных средств и методов поисковой адаптации позволяет синтезировать новые эффективные алгорит­мы автоматизированного проектирования [ ].

Early analogies between the mechanism of natural selection and a learning

(or optimization) process led to the development of the so-called "evolutionary

algorithms" (EAs)3, in which the main goal is to simulate the

evolutionary process in a computer. The use of EAs for optimization tasks

has become very popular in the last few years, spanning virtually every

application domain22'44'25'4.