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

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

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

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

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

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

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

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

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

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

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

Рыжов А.П.

Оглавление

ГЛАВА 1 11

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

1.1 Введение 11

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

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

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

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

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

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

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

1.6 Ток утечки в ячейках 21

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

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

1.8.1 Общие понятия УВГ 26

1.8.2 Рассматриваемые ограничения 28

1.8.3 Определение УВГ 30

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

1.10 Постановка задачи 34

1.11 Выводы по главе 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.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) или разрушение фоторезисторного шаблона.

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

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

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

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

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

1.8.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 (1.4)

P Pmax

T Tmax

A Amax

Y Ymin

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

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

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

ГЛАВА 2

НАУЧНО-МЕТОДИЧЕСКИЕ ПОЛОЖЕНИЯ ПО

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

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

2.1 Задача многокритериального выбора

2.1.1 Основные определения

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

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

Обозначим через

f(х) = (f1(x), f2{x),..., fm(х)) e Rm (2.1)

векторного критерия /при определенном х е X именуют векторной оценкой возможного решения х. Все возможные векторные оценки образуют множество возможных оценок

(возможных векторов)

Наряду с множеством выбираемых решений удобно ввести в рассмотрение множество выбираемых векторов (выбираемых оценок)

представляющее собой некоторое подмножество критериального пространства Rm.

2.1.2 Лицо принимающее решение

Процесс выбора невозможен без наличия того, кто осуществляет этот выбор, преследуя свои цели. Человека (или целый коллектив, подчиненный достижению определенной цели), который производит выбор и несет полную ответственность за его последствия, называют лицом, принимающим решение (сокращенно: ЛПР). Сама природа ЛПР при решении задачи выбора, как правило, не имеет особого значения. Таким образом, говоря о ЛПР в контексте задачи выбора, мы будем иметь в виду не его целиком, а лишь ту его «часть», те его характеристики, которые так или иначе связаны с процессом выбора. Если различные индивиды в одних и тех же ситуациях выбора ведут себя одинаковым образом, то с точки зрения теории принятия решений они ничем не отличаются друг от друга, т. е. представляют собой одно и то же ЛПР. Для наших целей ЛПР является инженер-проектировщик библиотечных эелементов.

2.1.3 Задача многокритериального выбора

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

Рассмотрим два возможных решения х' и х". Предположим, что после предъявления ЛПР этой пары решений, оно выбирает (отдает предпочтение) первому из них. В этом случае пишут х' >х х". Знак >х служит для обозначений предпочтений данного ЛПР и называется отношением строгого предпочтения или, короче, отношением предпочтения. Следует отметить, что не всякие два возможных решения х' и х" связаны соотношением х' >х х"-> либо соотношением х" >х х'- Иначе говоря, не из любой пары решений ЛПР может сделать окончательный выбор. Вполне могут существовать такие пары, что ЛПР не в состоянии отдать предпочтение какому-то одному решению этой пары, даже если это пара различных решений. Описанная ситуация вполне соответствует реальному положению вещей. Отношение предпочтения >х, заданное на множестве возможных решений, естественным образом

индуцирует (порождает) отношение предпочтения >Y на множестве возможных векторов Y. Тем самым, вектор у' = f(x') является предпочтительнее вектора у" = f(x") (т. е. у' >Y y") тогда и только тогда, когда решение х' предпочтительнее решения х" (т. е. X' >ХХ").

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

• множество возможных решений X,
• векторный критерий f вида 2.1,
• отношение предпочтения >х, заданное на множестве воз можных решений.

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

2.2 Множество недоминирующих решений

2.2.1 Определения

Отношение предпочтения >х, которым ЛПР руководствуется в процессе выбора, представляет собой строгий порядок, т. е. является иррефлексивным, ассиметричным и транзитивным.

Как указано в разд. 2.1.3, решение задачи многокритериального выбора заключается в отыскании множества выбираемых решений Sel X.

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

• справедливо соотношение х' >х х"-> а соотношение х" >х х' не выполняется;
• справедливо соотношение х" >х х\ а соотношение х' >х х" не выполняется;
• не выполняется ни соотношение х' >х х"> ни соотношение X >х X.

В первом указанном выше случае, т. е. при выполнении соотношения х' >х х'\ говорят, что решение х' доминирует решение х" (по отношению >х)- Во втором случае х" доминирует х'. Если же реализуется третий случай, то говорят, что решения х' и х" не сравнимы по отношению предпочтения.

Пусть для некоторого возможного решения х" найдется такое возможное решение х', что выполнено соотношение х' >х х". Тогда

для х', х" е X.

Это приводти к следующей аксиоме.

Аксиома 1 (исключение доминируемых решений). Если для некоторой пары решений х',х" е X имеет место соотношение.

Можно показать [ ], что обратное условие Кондорсе [ ] влечет выполнение аксиомы 1, но не наоборот.

В аксиоме 1 участвует не только отношение предпочтения >х-> которым руководствуется ЛПР в процессе принятия решений, но и множество Sel X. Это означает, что данное требование следует рассматривать как определенное ограничение на множество выбираемых решений. А именно, любое множество выбираемых решений не должно содержать ни одного такого решения, для которого может найтись более предпочтительное решение.

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

Определение. Множество недоминируемых решений обозначается N dom X и определяется равенством

Ndom X = {х* е X | не существует такого х е X, что х >х х*}.

Таким образом, Ndom X представляет собой определенное подмножество множества возможных решений X. В зависимости от вида множества X и конкретного типа отношения предпочтения >х множество недоминируемых решений может:

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

Лемма. Для любого непустого множества выбираемых решений Sel X, удовлетворяющего аксиоме 1, справедливо включение

SelX C NdomX (2.2)

Доказательство.Если предположить, что включение (2.2) для некоторого непустого множества Sel X не имеет места, то среди элементов этого множества найдется решение х" е Sel X, для которого выполнено соотношение х" не е NdomX. Тогда, по определению множества недоминируемых решений, существует такое решение x' e X, что х' >х х". Отсюда, используя аксиому 1, получаем х" не е Sel X Это противоречит начальному предположению о том, что х" — выбранное решение.

Замечание. В формулировке леммы (2.1) утверждается, что включение 2.2 выполняется для произвольного непустого множества выбираемых решений. Если Sel X = 0, то включение (2.2) также имеет место, поскольку, как принято в теории множеств, пустое множество содержится в качестве подмножества в любом множестве. Поэтому условие непустоты множества выбираемых решений в формулировке леммы 1.2 можно было бы опустить; при этом справедливость рассматриваемой леммы не нарушается. Но тогда при доказательстве следовало бы специально оговаривать этот «вырожденный» случай, который с практической точки зрения интереса не представляет (если нет выбора, то и нет смыслаизучать законы такого выбора). По этой причине здесь и всюду далее в подобных ситуациях, когда речь пойдет о включениях, содержащих множество выбираемых решений (или множество выбираемых векторов), мы будем подчеркивать непустоту этих множеств, чтобы сразу исключить из рассмотрения бессодержательные с практической точки зрения случаи.

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

Когда Sel X /= 0 и множество недоминируемых решений состоит из единственного элемента, задача выбора в принципе решена, поскольку это единственное недоминируемое решение в силу включения 2.2 является выбираемым решением и остается только найти его. Следует, однако, заметить, что подобного рода ситуации в практике встречаются крайне редко. Чаще всего, тех сведений, которые имеются об отношении предпочтения, оказывается недостаточно не только для нахождения множества выбираемых решений, но и для построения множества недоминируемых решений.

Наряду с множеством недоминируемых решений удобно ввести в рассмотрение множество недоминируемых векторов (недоминируемых оценок)

= /(NdomX) =

= \f(x*) ? Y | не существует такого х е Х9 что х >х х*} =

= {у* е Y | не существует такого у е Y, что у >Y 37*}-

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

Аксиома 1 (исключение доминируемых векторов). Если для некоторой пары векторов у fy у" е Yвыполнено соотношение у' >Y У", то у" 0 Sel Y

Лемма 2.2. (в терминах оценок). Для любого непустого множества выбираемых векторов Sel Y, удовлетворяющего аксиоме 1, справедливо включение

Sel Y с Ndom Y.

2.2.1 Алгоритм построения множества недоминирующих решений

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

Итак, пусть множество возможных решений X состоит из конечного числа элементов, а отношение предпочтения является иррефлексивным и транзитивным. Для построения множества недоминируемых решений Ndom X прежде всего следует перенумеровать все возможные решения. Пусть, например,

X = X1 = {х1, х2,..., хп}.

Первый шаг алгоритма заключается в последовательном сравнении первого решения х1 со всеми остальными х2,..., хn. Это сравнение заключается в проверке справедливости соотношения x1 >x xi и соотношения xi >х х для каждого i = 2,..., n. В случае истинности для некоторого i первого соотношения х1 >х xi доминируемое решение xi следует удалить из множества Х1 и продолжить указанную проверку для следующего за xi решения.

При выполнении второго соотношения xi >x х удалению подлежит первое решение х1 после чего сразу же следует перейти ко второму шагу. Если же ни одно из двух приведенных соотношений хх >х xt и xt ^x х\ не является истинным, ничего удалять не нужно. В том случае, когда сравнения решения х{

были проведены со всеми остальными решениями хъ..., хп, и ни

для какого / = 2,..., п не оказалось выполненным соотношение

xt >х хь первое решение следует запомнить как недоминируе-

мое и удалить его из (оставшегося) множества возможных реше-

ний. Указанные действия описывают первый шаг алгоритма.

Если после выполнения первого шага во множестве возмож-

ных решений не осталось ни одного решения (т. е. все оказались

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

ти будет храниться одно недоминируемое решение х{. Оно и пред-

ставляет собой множество недоминируемых решений. В против-

ном случае (т. е. когда не все решения оказались удаленными),

необходимо перейти ко второму шагу.

Обозначим множество, оставшееся после выполнения пер-

вого шага Хъ

Второй шаг полностью аналогичен первому. А именно, сна-

чала нужно перенумеровать элементы множества Х2. После этого

следует провести последовательное сравнение первого решения

этого множества со всеми остальными его элементами. При этом

сравнение осуществляется совершенно аналогично тому, как это

было описано на первом шаге. Выполнение сравнений на вто-

ром шаге либо закончится удалением первого решения множе-

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

дет. Во втором случае это решение следует запомнить как недо-

минируемое, а затем удалить его из множества Х2. Если после

32 ГЛАВА 1. НАЧАЛЬНЫЕ ПОНЯТИЯ МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА

этого во множестве возможных решений не останется ни одного

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

множество недоминируемых решений. В противном случае к ос-

тавшемуся непустому множеству возможных решений нужно

применить аналогичный третий шаг алгоритма и т. д. В результате,

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

множество всех недоминируемых решений l) Ndom X.

На каждом шаге алгоритма происходит удаление, по крайней

мере, одного возможного решения. Следовательно, после выпол-

нения некоторого конечного числа шагов будут удалены все воз-

можные решения кроме некоторого одного и алгоритм закончит

свою работу, так как оставшееся решение не с чем будет сравнивать

и потому оно также будет недоминируемым. Это рассуждение

доказывает конечность приведенного алгоритма.

Применение описанного алгоритма к произвольному конеч-

ному множеству возможных решений за конечное число шагов

приведет к отысканию, по крайней мере, одного недоминируе-

мого решения. Действительно, недоминируемым запоминается

лишь первое решение из множества, которое участвует в выпол-

нении очередного шага алгоритма. Если на всех предыдущих шагах

(кроме последнего) не было выявлено ни одного недоминируе-

мого решения, то таковым должно быть последнее решение, по-

скольку его не может доминировать ни одно из всех остальных

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

Теорема 1.1. Пусть множество возможных решений X (множе-

ство возможных векторов Y) состоит из конечного числа элементов.

Если отношение предпочтения >хявляется иррефлексивным и тран-

зитивным, то множество возможных решений {векторов) содер-

жит хотя бы одно недоминируемое решение (один недоминируемый

вектор), т. е. Ndom X ^ 0 (Ndom Y ^ 0).

Чаще всего в практических задачах выбора отношение пред-

почтения задано лишь частично, либо вообще не задано и его сле-

дует построить прежде, чем приступать к решению задачи. В таких

случаях схему приведенного выше алгоритма можно использовать

для опроса ЛПР с целью выявления его отношения предпочте-

ния и одновременного построения множества недоминируемых

решений. Для этого ЛПР сначала предлагают выбрать предпоч-

тительное решение из каждой пары, содержащей первое решение.

При этом доминируемые решения, по мере их выявления, сразу

1) Следует отметить, что это высказывание имеет место не только благода-

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

отношения предпочтения.

1.4. МНОЖЕСТВО ПАРЕТО 33

же удаляются. Далее, для сравнения предлагаются все пары, со-

держащие первое решение из множества, оставшегося после

первого шага, и т. д.

Кроме того, необходимо отметить, что схема приведенного

выше алгоритма может быть использована для построения мно-

жества Парето (см. следующий разд.).

1.4. Множество Парето

1. Дальнейшие требования, предъявляемые к отношению пред-

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

ется векторный критерий/ = (/ь/г,...,/»*)• Каждая компонента ft

векторного критерия, как правило, характеризует определенную

цель ЛПР, а стремление достичь этой цели в математических тер-

минах нередко выражается в условии максимизации (или мини-

мизации) функции ft на множестве X.

Необходимо отметить, что в некоторых задачах могут встре-

титься критерии, которые не обязательно следует максимизиро-

вать или минимизировать. Например, иногда требуется получить

некоторое среднее значение критерия или «удержать» его значе-

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

более гибким инструментом являются не критерии fb а («част-

ные») отношения предпочтения yt (см. [32, 33]). Однако, как ус-

тановлено, например, в [32], во многих важных с практической

точки зрения случаях (т. е. при некоторых «разумных» требова-

ниях к >-г и X) существует функция полезности иь адекватно опи-

сывающая данное «частное» отношение предпочтения: для всех

х\х" е X верна эквивалентность х' >t x" <^> ut{x') > ut{x").

Эти результаты показывают, что многие задачи, в которых изна-

чально не требуется максимизация (или минимизация) критериев,

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

рода экстремальным задачам 1).

В соответствии со сказанным будем считать, что ЛПР заин-

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

компоненты ft векторного критерия / В рамках многокритериаль-

ной задачи приходится ограничиваться уровнем строгости сфор-

мулированного допущения в том виде, в котором оно приведено

выше. Однако внимательный анализ показывает его некоторую

неопределенность, расплывчатость. Придадим обсуждаемому до-

пущению строгую форму.

1) Следует заметить, что последующее изложение можно обобщить на слу-

чай «частных» отношений предпочтения.

34 ГЛАВА 1. НАЧАЛЬНЫЕ ПОНЯТИЯ МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА

Для этого перейдем к оценкам и напомним, каким образом

определяется бинарное отношение >Y-> заданное на множестве

возможных векторов Y = f(X), Y с Rm\

f(x')>Yf(x") & х'>хх" №ях',х"еХ.

Всюду далее будем считать выполненным следующее допу-

щение, формулируемое в терминах векторов критериального про-

странства.

Аксиома 2 (продолжение отношения предпочтения 1)). Су-

ществует продолжение > на все критериальное пространство Rm

отношения yY, причем это продолжение у является иррефлексив-

ным и транзитивным отношением.

Суть этого требования (не считая обязательную иррефлек-

сивность и транзитивность) заключается в постулировании «рас-

ширенных» возможностей ЛПР сравнивать оценки по предпоч-

тительности. В соответствии с ним для любых двух векторов

у\у" Е Rm выполняется одно и только одно из следующих трех

соотношений

- У у у»;

- У" > У*\

- не имеет места ни у' > у", ни у" > у'.

При этом отношение предпочтения >- на множестве возмож-

ных векторов Y совпадает с отношением yY, которое самым

непосредственным образом связано с отношением >х-

Поскольку иррефлексивность и транзитивность отношения >-

означает наличие аналогичных свойств у отношения yY, что, в свою

очередь, влечет иррефлексивность и транзитивность отношения ух,

необходимость требования иррефлексивности и транзитивности

отношения >-х(см. п. 1 разд. 1.3) с данного момента отпадает. Это

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

аксиомы 2.

2. Согласование отношения предпочтения с критериями. Со-

вершенно очевидно, что в задаче многокритериального выбора

отношение предпочтения, равно как и критерии оптимальности,

выражают интересы одного и того же ЛПР. Поэтому они должны

быть каким-то образом взаимосвязаны (сопряжены) друг с другом.

Настало время обсудить эту взаимосвязь.

1) В этом требовании для обеспечения справедливости формулируемого ниже

принципа Эджворта-Парето можно предполагать существование продолжения

отношения >- не на все пространство Rm, а лишь на декартово произведение

множеств, являющихся значениями имеющихся критериев (см. [22]).

1.4. МНОЖЕСТВО ПАРЕТО 35

Будем говорить, что /-й критерий ft согласован с отношением

предпочтения >, если для любых двух векторов у',у" Е Rm, та-

ких, что

у" = (у[ у! 1 / у' у1 ) у'Уу"

У \УЪ •••' Уг-Ъ У 1ч Уг+Ъ •••? Ут)ч Уг ^ Уг '

следует у' >- у".

Содержательно согласованность данного критерия с отно-

шением предпочтения как раз и означает, что ЛПР при прочих

равных условиях заинтересовано в получении по возможности

больших значений этого критерия.

Взаимосвязь отношения предпочтения данного ЛПР с кри-

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

Аксиома 3 (согласование критериев с отношением предпоч-

тения). Каждый из критериев/ь/*2,...,/w согласован с отношением

предпочтения >.

3. Аксиома Парето. Заинтересованность ЛПР в получении по

возможности больших значений всех компонент векторного кри-

терия / можно также выразить в терминах так называемой акси-

омы Парето [17, 26].

Аксиома Парето (в терминах решений). Для всех пар решений

х',х" е X, для которых имеет место неравенство fix1) > f(x"),

выполняется соотношение х' >х х"-

Напомним (см. разд. 1.3), что запись f{x') > f{x") означает

выполнение покомпонентных неравенств/ (х') ^ ft(x") для всех

/ = 1, 2,..., т, причем f{x') ^ f{x").

Лемма 1.3. Принятие аксиом 2 и 3 гарантирует выполнение

аксиомы Парето.

А Пусть неравенство f{x') > f{x") справедливо для двух про-

извольных возможных решений х\ х" е X. Не уменьшая общно-

сти рассуждений, можно считать, что здесь строгие неравенства

fk(x') > fk(x") имеют место для всех индексов к = 1,..., / при

некотором I e {1,2,..., т}. Для всех последующих индексов к,

к > I (при условии, что такие найдутся, т. е. при I < т), будем

предполагать выполненными соответствующие равенства.

Используя согласованность первых / критериев и указанные

выше строгие неравенства, получаем

36 ГЛАВА 1. НАЧАЛЬНЫЕ ПОНЯТИЯ МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА

(Мх'')9/2(х')9...,Мх')9...9Мх')) у

у (f1(x'f)9f2(x'')9...9fl(x')9...9fm(x'))9

(fi(x''TMx;'^

>" (/i (*"),/2 (*"),...,fl(xff),fM (*'),...,fm(x')).

Отсюда на основании транзитивности отношения >- следует

(fxix'^Mx'),...Jjix'),...,fm(x')) у

*(fi(xff)J2(xff),...,fi(x''),fM(xf),...,fm(x')) A.3)

Благодаря сделанному в начале доказательства предположению

имеют место равенства fk{x') = fk{x"), к = / + 1,..., т. Поэто-

му соотношение A.3) влечет

/(*') = (fi(xf),f2(xf),...,Мх'),...,/т(х')) у

>- ifi{x")J2{x")9...Jl(x")9...Jm(x")) = /(*"),

откуда, в свою очередь, по определению отношения >- вытекает

требуемое соотношение х' >х х"- ^

4. Множество Парето. Если для некоторой пары возможных

решений имеет место неравенство f(x') > f(x"), то благодаря

аксиоме Парето первое решение будет предпочтительнее второ-

го, т. е. х' >х х"- Тогда в соответствии с аксиомой 1 второе реше-

ние ни при каких обстоятельствах не может оказаться выбран-

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

принятия решений. Исключение всех подобного рода решений

приводит к множеству Парето.

Множество парето-оптимальных решений обозначается Р/(Х)

и определяется равенством

Р/{Х) = {х* g Х\ не существует такого х е X, что f(x) > /(х*)}.

Лемма 1.4. При выполнении аксиом 2 и 3 множество недомини-

руемых решений Ndom X удовлетворяет включению

NdomXc Pf(X). A.4)

А Пусть, напротив, для некоторого недоминируемого реше-

ния х е Ndom X выполнено соотношение х 0 Р/(Х). Тогда, по

определению множества парето-оптимальных решений, существу-

ет такое возможное решение х' е X, что f(x') > f(x). На осно-

вании леммы 1.3 в условиях доказываемого утверждения спра-

ведлива аксиома Парето. Поэтому полученное неравенство, в силу

аксиомы Парето, влечет соотношение х' >х х-> которое не совме-

стимо с начальным предположением х е NdomJf.V

1.4. МНОЖЕСТВО ПАРЕТО 37

Непосредственно из лемм 1.2 и 1.4 вытекает следующий прин-

ципиально важный для теории принятия решений результат.

Теорема 1.2. В условиях выполнения аксиом 1-3 для любого непу-

стого множества выбираемых решений Sel X справедливо включение

SelXc Pf(X). A.5)

Включение A.5) выражает собой так называемый принцип

Эджворта—Парето {принцип Парето), согласно которому

если ЛПР ведет себя достаточно «разумно» (т. е. в со-

ответствии с аксиомами 1—3), то выбираемые им реше-

ния обязательно являются парето-оптимальными.

Этот принцип демонстрирует особую, исключительно важ-

ную роль множества парето-оптимальных решений в теории при-

нятия решений.

Внимательный анализ доказательств приведенных утвержде-

ний, в совокупности приводящих к теореме 1.2, показывает, что

если хотя бы одна из аксиом 1, 2 или 3 нарушается, то выбирае-

мое решение не обязано быть парето-оптимальным 1). Отсюда

следует, что принцип Эджворта—Парето не является универсаль-

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

критериального выбора. Более того, на основе аксиом 1, 2 и 3

(точнее говоря, на основе отрицаний этих аксиом) при желании

можно сделать определенный вывод и о том, в каких именно

задачах этот принцип может «не работать».

Итак, применение этого принципа рискованно или же вооб-

ще недопустимо, если:

— отношение предпочтения, которым ЛПР руководствуется

в процессе выбора, не является транзитивным;

— отношение предпочтения ЛПР не согласовано хотя бы с од-