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

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

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

Специальность: 05 13.12 - системы автоматизации проектирования

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

Москва - 2007

Работа выполнена в Институте проблем проектирования в микроэлектронике Российской академии наук (ИППМ РАН)

Официальные оппоненты.

доктор технических наук, профессор Норенков И П доктор технических наук, профессор Казенное Г.Г. доктор технических наук, профессор Лебедев Б.К.

Ведущая организация: ОАО "Ангстрем-М"

Защита состоится 20 декабря 2007 года в 12 часов на заседании диссертационного совета Д 002.078 01 при Институте проблем проектирования в микроэлектронике Российской академии наук (ИППМ РАН) по адресу: 124681, г. Москва, Зеленоград, ул. Советская д.З

С диссертацией можно ознакомиться в библиотеке ИППМ РАН

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

Ученый секретарь

диссертационного совета Д 002.078.01 кандидат технических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Актуальность темы.

Основной тенденцией развития интегральных микросхем является постоянное уменьшение минимальных размеров, в пределах которых может быть достигнуто успешное формирование элементов и межсоединений на кристалле Ключевым параметром в современных технологиях является минимальный размер затвора транзистора, который уменьшается примерно в 1,5 раза каждые два года На рубеже тысячелетий началось производство с применением технологических норм 130, 90 и 65 нм К 2007 году ведущие западные микроэлектронные компании освоили массовое производство для технологий с нормой 65нм, начали разработки проектов для технологий с нормой 45нм, а также разработку перспективных библиотек и функциональных блоков для технологий с нормой 32нм

Аналогичные тенденции также находят свое выражение в планах развития отечественной микроэлектроники В подпрограмме "Развитие электронной компонентной базы" Федеральной целевой программы "Национальная технологическая база" на 2007-2011 г г

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

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

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

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

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

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

• Большие вычислительные затраты при точном анализе проектов на электрическом и топологическом уровне

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

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

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

Цель диссертационной работы.

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

Объект исследования.

Объектом исследования является задача автоматизации проектирования интегральных микросхем Предметом исследования является процесс автоматизированного проектирования цифровых СБИС

Задачи исследования.

Основная задача работы состоит в разработке и исследовании методов логического и логико-временного анализа КМОП СБИС,

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

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

1) Разработка и исследование эффективных методов анализа логических корреляций в КМОП-схеме, в том числе для схем на транзисторном уровне, восстановленных из топологии

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

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

4) Разработка производительных методов характеризации библиотек, в том числе с учетом вариаций различных параметров, а также с использованием современных форматов описания

библиотечных элементов, ориентированных на уточнённый анализ межсоединений

5) Разработка новых методов логико-электрического анализа быстродействия на основе современных стандартов проектирования библиотек элементов, ориентированных на уточненный анализ межсоединений

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

Методы исследования.

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

Научная новизна.

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

- Предложен новый метод анализа логических ограничений в КМОП-схеме на основе правила резолюций, включающий в себя правила формирования исходной системы логических ограничений на транзисторном уровне, в том числе для схем, восстановленных из топологии, правила редукции системы логических ограничений, эффективный алгоритм сложности 0(Ы log(N)) для быстрого распространения логических ограничений вдоль схемы

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

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

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

- Разработан алгоритм формирования характеристической ЯОВОО для кластера узлов схемы и нахождения максимально возможной помехи, индуцируемой в "узле-жертве"

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

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

1) Новый подход к анализу логических ограничений в КМОП-схеме на основе метода резолюций, обеспечивающий поиск логических ограничений на транзисторном уровне, в том числе для схем, восстановленных из топологии.

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

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

4) Новые производительные методы характеризации библиотек, в том числе с учетом вариаций различных параметров, а также с использованием современных форматов описания библиотечных элементов, ориентированных на уточнённый анализ межсоединений

5) Новые методы логико-электрического анализа быстродействия на основе современных стандартов проектирования библиотек элементов, ориентированных на уточненный анализ межсоединений

Реализация научно-технических результатов работы.

Разработанные алгоритмы доведены до программной реализации Проведен цикл численных экспериментов На основе

и

полученных результатов разработан комплекс программ для анализа цифровых КМОП-схем, внедренный на ряде предприятий электронной промышленности, в том числе на предприятиях ОАО "Ангстрем-М", ФГУП "НПО Измерительной Техники", ФГУП НИИМА "Прогресс", а также в учебный процесс МГИЭТ (ТУ) Достоверность результатов.

Достоверность результатов, представленных в работе, подтверждается согласованностью с известными подходами, опубликованными в литературе, адекватностью математических моделей, многочисленными результатами экспериментальной проверки предложенных методов с использованием разработанного на их основе программного обеспечения, согласованностью результатов работы разработанного программного обеспечения с результатами других систем автоматизированного проектирования, такими как Synopsys (Prime Time, Design Compiler), Cadence (Celtic, Encounter) Практическая ценность

Результаты работы могут найти применение при проектировании широкого класса заказных и матричных микросхем на этапах логического и логико-временного анализа, а также на этапе верификации схем с учетом топологической реализации Предложенные алгоритмы могут быть использованы в комбинации с другими средствами САПР СБИС для повышения эффективности, улучшения качества и надежности проектирования, главным образом для СБИС, разрабатываемых на основе глубоко субмикронных и нанометровых технологий с размером транзистора 180, 130, 90 нм и

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

Апробация работы.

Основные результаты работы докладывались и обсуждались на научных семинарах в ИППМ РАН, на Европейской конференции по проектированию и тестированию интегральных схем "ED&TC" (Франция, Париж, 1997), 3-й международной конференции "Микроэлектроника и информатика" (Москва, 1997), 1-м международном семинаре по проектированию мульти-архитектурных низкомощных интегральных схем "MALOPD" (Москва, 1999), Международном семинаре по помехоустойчивости интегральных схем "Signal Integrity Workshop" (США, Остин, 2000), 3-й международной конференции "Электроника и информатика - XXI век" (Москва,

2000), Международной конференции по компьютерному проектированию интегральных схем "ICCAD" (США, Сан-Хосе,

2001), Международном симпозиуме по качественному проектированию интегральных схем "ISQED" (США, Сан-Хосе,

2002), Международной конференции по компьютерному проектированию интегральных схем "ICCAD" (США, Сан-Хосе,

2003), Европейской конференции по проектированию и тестированию интегральных схем "DATE" (Франция, Париж, 2004), Международной

конференции по компьютерному проектированию интегральных схем "ICCAD" (США, Сан-Хосе, 2004), на Всероссийской научно-технической конференции "Проблемы разработки перспективных микроэлектронных систем - 2005" (МЭС) (Москва, 2005), Международной конференции по интегральным системам и схемам "ACISC" (США, Остин, 2006), Всероссийской научно-технической конференции "Проблемы разработки перспективных микроэлектронных систем - 2006" (МЭС) (Москва, 2006), Международном симпозиуме корпорации Intel по проектированию интегральных схем и технологическим решениям (Израиль, Хайфа, 2007)

Публикации.

Список опубликованных по теме диссертации научных трудов составляет 35 работ, в их числе одна монография и 7 статей в научных журналах, входящих в Перечень периодических изданий, рекомендованных ВАК РФ для публикаций основных результатов диссертаций на соискание степени доктора наук

Структура и объем работы.

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

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

Во введении обоснована актуальность проблем логического и логико-временного анализа цифровых КМОП-схем для современных глубоко субмикронных технологий с проектной нормой 100 нм и ниже Определена цель диссертационной работы Сформулирована

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

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

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

цифровых схем в терминах булевой алгебры, теории графов и теории множеств Вводится ряд новых определений для формализации и решения новых задач в области логического и логико-временного анализа В частности, дается формальное определение КМОП-схемы, объединяющее в себе схемотехническую и логическую информацию КМОП-схема определяется как упорядоченная шестерка Т = (2,Х,Г,1,Ую,У<и), где

• 2 - множество переменных, называемых узлами,

• X с 2 - множество первичных входов,

• 7 с 2 - множество первичных выходов,

• е? - выделенный узел земли,

• У^ б2 - выделенный узел питания,

• - множество элементов, определяющих логические отношения (р(1} ) следующего вида (1)-(3).

(1) <р(Яг) г=>(з = с1), gz2, зМе2\Х - для 14-МОП транзистора,

(2) (р(Рг) = 8^2, 8^е2\Х - для Р-МОП транзистора,

(3) <р( Л,) х = у х,у<а2 - для повторителя напряжения или линейного сопротивления

Теоретико-графовая модель КМОП-схемы (КМОП-граф) определяется, как неориентированный граф О = (V ,Е), построенный

на основе Т -(2,Х, У, [, , Vм ) по специальным формализованным

правилам Цепь земли G0 -(V0,E0) и цепь питания Gj ~(V1,El) определяются как связные подграфы графа G, соединенные ответственно с Vss, V^ посредством пассивных элементов Для решения проблемы декомпозиции для схем с разветвленными шинами питания и земли вводятся формальное обобщенное определение подсхемы элементов, связанных по постоянному току (сокращенно DCCC - direct current connected component)

Пусть G = (V,E)- граф КМОП-двухполюсников, Gq = (Vg,Eq) - цепь земли графа G, Gj -(Vj,Ej) - цепь питания графа G и е0-(х0,у0), е0еЕ\(Е0иЕ1) - ребро графа G = (V,E), не входящее в цепи земли и питания. Тогда подсхемой элементов, связанных по постоянному току (сокращенно DCCC) для заданного ребра е0 будет называться подграф GD(e0) = (VD(e0),ED(e0)) графа G-(V,E), удовлетворяющий следующим условиям:

(1) заданное ребро принадлежит DCCC. е0 е Ed (е0 ),

(2) узлы всех двухполюсников, входящих в DCCC, принадлежат DCCC, те

если (х, у) е ED(e0 ), то xeVD(e0), y<=VD(e0),

(3) для всех узлов DCCC, кроме узлов цепей питания и земли, все ребра, инцидентные узлу DCCC, принадлежат DCCC, т е если xeVD(e0)\(V0vV1) и (x,y)eV, то (x,y)eVD(e0),

(4) x g Vd (eg ), (x, у J g Ed (e0 ) - тогда и только тогда, когда они могут быть добавлены в DCCC на основе правил (1), (2),(3) На основе предложенных формализмов строится обобщенный алгоритм DCCC-декомпозиции КМОП-схем на случай разветвленных шин питания и земли Модифицированный алгоритм декомпозиции позволяет решать задачи логико-электрического моделирования с учетом особенностей современных технологий для разводки шин питания и земли, включая анализ вариаций скачка напряжений (IR-drop) в шинах питания и земли

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

Известно, что даже ответ на вопрос о существовании или отсутствии какого-либо одного конкретного логического ограничения представляет собой проблему большой сложности Такая проблема известна в литературе, как SAT-проблема (Satisfactory problem) Известно, что k-SAT проблема является NP-полной при к>2 и имеет полиномиальную сложность при к=2 Есть много подходов для решения этой проблемы, например, метод проб с возвратами

(Backtracking), метод локальных проб (Smallmark), метод рекурсивного обучения (Recursive Learning) и др Однако все алгоритмы полного решения SAT-проблемы эффективны лишь для схем небольшой размерности

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

В основе предлагаемого подхода лежит метод резолюций, ранее известный из теории автоматического доказательства теорем (J A Robmson, J.Hembrand, C.L Chang, R C.T.Lee, С Ю Маслов) Применение метода резолюций для систем большой размерности затруднено главным образом из-за экспоненциального роста числа ограничений с ростом размерности задачи Для адаптации этого метода к цифровым КМОП-схемам большой размерности в диссертационной работе решаются следующие задачи

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

- разработка алгоритма редукции системы логических ограничений,

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

Для вывода новых ограничений предложено использовать правило резолюции в конъюнктивной форме

а В = 0, ~а С — 0 н* В С = 0 где В, С - произведения литералов

В целях сокращения опускается "=<?" Таким образом, например, система ограничений для вентиля AND будет записываться как (х a b, х а, х Ь), а правило резолюции может быть записано

как (а-В, а-С\-*В-С)

Система логических ограничений на транзисторном уровне формируется на основе КМОП-схемы (определение в главе 1) по следующим правилам

• Для каждого МОП-транзистора N-типа (.у - исток, g - затвор, d - сток) на основе соотношения g (s = d) добавляются два

ограничения g s d, g s-d

• Для каждого МОП-транзистора Р-типа на основе соотношения g =>fs = d) добавляются два ограничения g s d, g s-d

• Для каждого линейного сопротивления (х,у - выводы сопротивления) на основе соотношения (х-у) добавляются два

ограничения х у, х у

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

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

Для преодоления проблем экспоненциального роста числа ограничений предложен эффективный алгоритм распространения логических ограничений вдоль схемы В основе предлагаемого алгоритма - последовательное применение правила резолюций к узлам схемы с целью получения новых простых логических импликаций (ПЛИ), или другими словами - новых простых логических ограничений из двух переменных Показано, что такой алгоритм имеет вычислительную сложность 0(N lo2.CN)) Это достигается, в частности, за счет следующих новых правил распространения логических ограничений

• В отличие от ранее известного метода распространения ПЛИ (ВоЬЬа Б, На^ IN ), транзитивный закон и правило объединения не используются Остальная часть алгоритма модифицирована таким образом, чтобы не хранить ПЛИ, которые можно получить применением транзитивного закона к существующим ПЛИ

• При распространении ПЛИ через сложное ограничение а1 а2 ап > применяется следующее правило пересечения если

существуют ПЛИ а0 а1, а0 -а2, , а0 ап_} , то, последовательно

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

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

Другая проблема, относящаяся к разработке алгоритмов поиска логических ограничений, заключается в разработке модели для эффективной работы с системой логических ограничений. Проблема осложняется большой размерностью задачи, связанной с решением проблем на транзисторном уровне с учетом топологии межсоединений Для решения этой проблемы предложено использовать гиперграф Я = (У,Е), в котором вершины из множества V соответствуют узлам схемы, а множество гиперребер графа ^сКиГхГиКхГхКи описывает логические ограничения

произвольного размера- г?' г/ , где п = 1,2, -длина терма и

Для описания степеней ai,ci2, ,ап в логическом ограничении

z"' z°2 ■••■Zn" предлагается маркировка гиперребер на основе специального кода, который назван B-кодом. Заданное логическое ограничение Г-zf' z/: z^" описывается А-кодом,

представляющим собой целочисленную кодировку двоичного вектора а = |а/, а2, , ап |Т > определяемую по следующей формуле

1=1

В свою очередь, В-код для заданной системы логических ограничений Т1,Т2, Д)с определяется на основе А-кода следующим образом:

/ к

^ (1, если ЪТГ} = 1, ,к А(Т})-т

т [0 -в противном случае

В работе показано, что такая кодировка является наиболее эффективной для хранения и поиска различных логических ограничений при реализации в системе команд ЭВМ

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

Решение задачи статического временного анализа (СВА) является традиционным подходом к оперативной оценке

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

В настоящее время наиболее распространенные подсистемы для анализа критических путей - это Prime Time фирмы Synopsys и СТЕ Encounter фирмы Cadence Попытки решить задачу истинности или ложности критического пути не нашли широкого применения в коммерческих системах, поскольку сама задача является NP-полной, и не существует эффективных алгоритмов для схем большой размерности Для преодоления этой проблемы в системах Prime Time, Encounter предусмотрен интерфейс ручного указания ложных путей, который не может быть эффективен для сложных схем большой размерности

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

распространения логических корреляций, предложенных во второй главе Группами помеченных узлов являются в этом случае узлы критических путей, и метод резолюций работает избирательно с целью выявления логических ограничений, необходимых для более достоверной оценки длины критического пути и отсева логически противоречивых путей. Тем самым решается проблема сокращения экспоненциальной сложности алгоритма до 0(N log(N)) Экспериментальные результаты показали, что новый метод позволяет сократить задержку критического пути в ряде случаях до 60% и более процентов по сравнению с исходной верхней оценкой в системе Synopsys Prime Tune И даже в том случае если не удалось доказать, что самый критический путь является ложным, с помощью нового метода можно удалить часть путей из списка первой тысячи наиболее критических путей

Наряду с необходимостью учета логических корреляций другой существенной проблемой при переходе на глубоко субмикронные и нанометровые технологии является возрастающая роль вариаций технологических и схемных параметров В связи с этим, за последние 2-3 года широкое распространение получили методы блочного статистического временного анализа с оценкой вариаций задержек (Kalafala К, Pilleggi LT, Clark СЕ и др) в линеаризованной форме по отношению к вариациям глобальных ( ДАГу ) и локальных параметров ( ARj )•

D=EP+Jay Mj+rj-Щ

J

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

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

- во-вторых, отсутствуют эффективные методы характеризации библиотечных элементов с учетом статистических вариаций

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

В современных САПР (Synopsys, Cadence, и др) наиболее распространенной и широко используемой моделью для характеризации библиотечных элементов является так называемая нелинейная модель задержки - Non-Lmear Delay Model (NLDM) в формате Liberty (Synopsys) Модель NLDM представляет собой нелинейные зависимости задержек выходных сигналов Dout от длительности фронта входного сигнала Ттр и емкости нагрузки

Сои( в форме двумерных таблиц Dout (Т^пр, Clout), к<=[1 NTJ, I е [1 Nc ] Аналогичными таблицами представляются и

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

переменных Тш(Т^пр,С1ои1), kefl NT], lefl Nc] Емкость

нагрузки Cout в свою очередь зависит от входных емкостей Cmp m

нагружающих вентилей Поскольку Тшр и Cmpm также имеют

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

выходной нагрузки Cout - ^ Cmp m и входных емкостей

m

нагружающих вентилей Cinp m согласно следующей формуле

J [ m P' J

„ т „ dD

где >j d'"p ~ 'TTZ,-- чувствительность задержки к входному

О Т гпр

фронту при номинальном значении входного фронта, g С out _ —-- чувствительность задержки к вариации

D ее,

out

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

-'mp т

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

входных емкостей Стр т, составляющих нагрузку рассматриваемого вентиля

Реализация предлагаемого подхода обеспечила существенное повышение точности блочного статистического анализа в реальных проектах, разрабатываемых на основе КЫЖ-моделей библиотечных элементов

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

Для перспективных глубоко субмикронных и манометровых технологий до 60-80% полной емкости межсоединений составляет емкость межпроводниковых связей Это приводит к резкому возрастанию помех (паразитных сигналов), индуцируемых в проводниках другими (соседними) проводниками Эта тенденция приводит к возрастающей потребности в алгоритмах и программах анализа помех в цифровых СБИС

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

одном направлении Однако получаемая при этом оценка максимальной помехи обычно является чрезмерно пессимистической Она может быть уточнена различными способами В коммерческих САПР реализованы методы, основанные на результатах статического временного анализа (Celtic-NDC (Cadence), PnmeTime-SI(Synopsys)). Более сложные методы учитывают логику работы схемы

Ранее разработанные методы анализа помехоустойчивости, основанные на логических импликациях, были эффективными применительно к комбинационным цифровым схемам, состоящим из относительно небольших DCCC (DC connected component, или подсхема, связанная по постоянному току) Однако при применении этих методов к промышленным схемам возникал ряд проблем

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

• Проблема экстракции логики для DCCC со многими выходами и DCCC большого размера

• Огромное количество ПЛИ (простых логических импликаций), особенно в присутствии резистивных деревьев (сеток) и деревьев инверторов/буферов

• Трудности, связанные с учетом импликаций более сложных, чем ПЛИ (3 -ЛИ, 4-ЛИ, , N-ЛИ)

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

• Увеличение эффективности на основе использования более общих моделей данных и математических методов

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

• Достижение эффективности метода применительно к промышленным схемам большого размера

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

После того, как выполнена генерация ПЛИ, анализ помех производится отдельно для каждого кластера и соответствующего типа помехи Для анализа помех в кластере предложен алгоритм генерации характеристической ШЭЬШВ Предположим, что кластер содержит "узел-жертву" V и "узлы-агрессоры" а¡, ,ап Характеристическая функция кластера ,а„) - это функция,

которая равна 1 для совместимых комбинаций своих аргументов (комбинаций, удовлетворяющих всем ограничениям), и равна 0 во

всех остальных случаях Для формирования характеристической ЫОЕЮО, те ЯОВБО для характеристической функции кластера, используются найденные логические ограничения

а1

а4

а2

а3

1Я

Г\ V ЬомИ

V а4,у а5,

а1 а4, а2 а4, а2 а3 -а5, а1 а2 а4, а2 а} а5,

Рис 1 Пример схемы, набор логических ограничений и фрагмент характеристической ЯОВИБ

Для иллюстрации метода на рис 1 показан пример простой схемы с набором ограничений, необходимым для анализа помехи типа Ьом>Я в узле v, индуцируемой остальными пятью узлами схемы (ЬтмЯ - помеха, при которой "узел-жертва" находится в логическом 0, в то время как "узлы-агрессоры" переключаются из 0 в 1) Справа показана соответствующая часть характеристической ЛОВОй

Результаты численных экспериментов показали, что предложенный метод позволяет сократить суммарную оценку влияния помех на 30-50% по сравнению с распространенным консервативным

методов (Cadence Celtic) и на 20-30% по сравнению с методом, основанным на использовании только простых логических импликаций

Особое внимание в работе уделяется анализу высокопроизводительных схем типа "домино" "Домино"-схемы широко используются в высокопроизводительных микропроцессорах и имеют повышенную чувствительность к помехам Для корректной обработки схем типа "домино" в алгоритм анализа помехоустойчивости, основанный на методе резолюций, необходимо внести ряд модификаций Рассмотрим типичный вентиль типа "домино" (рис 2)

Рис 2 Пример "домино"-вентиля.

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

рекурсивного обучения Данный подход позволяет генерировать большое число дополнительных ограничений для схем с избыточным кодированием сигналов, широко используемых в высокопроизводительных АЛУ Результаты численных экспериментов показали высокую эффективность предложенного метода, способного исключить до 29% "узлов-агрессоров" из их полного числа

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

В пятой главе приведен анализ современных моделей быстродействия библиотечных ячеек с точки зрения решения новых проблем проектирования глубоко субмикронных и нанометровых цифровых СБИС, в том числе дан сравнительный анализ следующих моделей нелинейной модели задержки NLDM (Non-Linear Delay Model) и моделей на основе источника тока CCSM (Composite Current Source Model), ECSM (Effective Current Source Model)

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

Для того, чтобы удовлетворить новым требованиям, в компании Synopsys в 2004 был разработан новый формат на основе CCS-модели Компания Cadence в том же 2004 году анонсировала формат ECSM, а в 2006 году - его статистический вариант - sECSM (sensitivity Effective Current Source Model) В 2007 году анонсирован новый статистический стандарт - SI2-ECSM, как обобщение sECSM С 2005 года CCS-модель поддерживается подсистемой Synopsys PnmeTime В настоящее время ECSM поддерживают инструменты Cadence Encounter, Cadence First Encouter Появились также первые

средства характеризации новых моделей - Synopsys NanoChar, Cadence Signal Storm NDC, Magma SiliconSmart SI Однако на сегодняшний день использование новых моделей в промышленном проектировании затруднено Основная причина заключается в том, что новые модели имеют большую размерность по сравнению с NLDM, и как следствие требуют значительно больших ресурсов по времени счета и потребляемой памяти - как на этапе использования этих моделей, так и на этапе подготовки (характеризации) Другая проблема состоит в том, что практически единственной областью применения этих моделей остается статический временной анализ, и не существует алгоритмов для других типов анализа

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

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

нагрузочных емкостей Cout для заданных наборов этих величин

{Ттр},ке[1 NTJ, {Clout},l<=[l NCJ,

где значения NT и Nc обычно находятся в интревале 10-20 В

коммерческих системах характеризации (NanoChar, Cadence Signal Storm NDC, Magma SiliconSmart SI) такие зависимости строятся на основе многократного электрического моделирования (типа Spice)

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

ТкоШ, требующих до нескольких тысяч запусков электрического моделирования При переходе на новые статистические модели (зЕС8М, 812-ЕС8М) трудоемкость возрастает в десятки - сотни раз ввиду необходимости расчетов для различных вариаций технологических и схемных параметров

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

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

- встроенный алгоритм многократного электрического моделирования для разных вариантов входных фронтов и емкостей нагрузок для сокращения времени подготовки к моделированию (ргергосезвищ);

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

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

Для расширения сферы применения CCSM/ECSM моделей предлагаются два новых подхода

1) интеграция статического временного анализа на вентильном уровне с ускоренным электрическим моделированием RC-цепей с использованием CCSM/ECSM драйвера,

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

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

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

- систему анализа и генерации логических ограничений,

- систему временного анализа,

- систему анализа помехоустойчивости,

- систему ускоренного электрического моделирования и характеризации

Проведены численные эксперименты Показана эффективность разработанных алгоритмов

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

Перечисленные программные средства внедрены на ряде предприятий электронной промышленности, в том числе на предприятиях ОАО "Ангстрем-М", ФГУП "НПО Измерительной Техники", ФГУП НИИМА "Прогресс", а также в учебный процесс МГИЭТ (ТУ)

Заключение

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

развития научных основ создания систем автоматизации проектирования цифровых схем, разрабатываемых на основе перспективных КМОП-технологий с топологическими размерами в нанометровом диапазоне (100 нм и ниже).

Основные результаты диссертационной работе состоят в следующем

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

2) Разработана теоретико-графовая модель для эффективной работы с системой логических ограничений, включающая в себя, гиперграф системы ограничений, эффективный метод хранения системы ограничений на основе В-кода и бинарного сбалансированного дерева, эффективные алгоритмы обработки ограничений на основе А-кода

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

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

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

транзисторном уровне описания схемы Показано также, что использование резолюций является значительно более мощным инструментом, чем применявшаяся ранее генерация простых логических импликаций Разработан алгоритм формирования характеристической ЯОВБО для кластера узлов схемы и нахождения максимально возможной помехи, индуцируемой в "узле-жертве" Результаты тестирования предложенного метода свидетельствуют о его высокой эффективности по сравнению с методом, основанным на использовании только простых логических импликаций В частности, предложенный метод позволяет сократить количество ложных помех на 30-50% по сравнению с распространенным консервативным методом и на 20-30% по сравнению с методом импликаций

6) Предложен новый подход к анализу помехоустойчивости высокоскоростных "домино"-схем посредством учета корреляций между сигналами, налагающих запрет на одновременное переключение "узлов-агрессоров", индуцирующих помеху в "узле-жертве" Эффективность предлагаемого подхода основана на учете возможности одновременного непроводящего состояния верхней и нижней цепей "домино"-вентиля Метод резолюций обобщен путем включения в него алгоритма рекурсивного обучения Данный подход позволяет генерировать большое число дополнительных ограничений для схем с избыточным кодированием сигналов, широко используемых в высокопроизводительных АЛУ и за счет этого приводит к значительному снижению пессимизма в оценке максимальной помехи Результаты численных экспериментов показывают высокую эффективность предложенного метода,

способного исключить до 29% "узлов-агрессоров" из их полного числа

7) Исследованы методы анализа влияния помех на задержку распространения сигналов в путях цифровых СБИС на основе анализа логических ограничений в схеме Для решения задачи поиска максимально-реализуемого набора "агрессоров" (МРНА) предложено несколько эвристических алгоритмов для повышения достоверности в оценке влияния помех на время задержки распространения сигналов цифровых СБИС с большими наборами "узлов-жертв" в путях, в том числе, эвристический алгоритм на основе независимого множества "агрессоров" максимального веса (НММВ) и более точный алгоритм на основе метода ветвей и границ

8) Разработан новый подход к характеризации логических элементов и элементов памяти, включающий в себя автоматическую генерацию сглаженных фронтов источников напряжений на основе сплайн-аппроксимации, встроенный алгоритм многократного электрического моделирования для разных вариантов входных фронтов и емкостей нагрузок; встроенные алгоритмы вычисления интегральных параметров схемы (задержек, фронтов, потребляемой мощности, времени удержания и установления для элементов памяти) Предлагаемый подход обеспечивает повышение быстродействия характеризации по сравнению со стандартным маршрутом характеризации в 10-15 раз для логических вентилей и в 30-50 раз для элементов памяти при сохранении точности моделирования в пределах 10% по сравнению с обычным электрическим моделированием

9) Разработаны новые методы логико-электрического моделирования на основе токовых моделей вентиля CCSM/ECSM В отличие от известных методов смешанного моделирования предлагаемый подход основан на адаптации моделей, используемых в коммерческих системах Synopsys, Cadence, и благодаря этому обеспечивает интеграцию с промышленными маршрутами проектирования и не требует какой-либо дополнительной характеризации макромодели вентиля

10) Разработан комплекс программных средств для логического, логико-электрического и логико-временного анализа цифровых глубоко субмикронных КМОП-схем, включающее в себя следующие программные системы- систему анализа и генерации логических ограничений,

- систему временного анализа,

- систему анализа помехоустойчивости,

- систему ускоренного электрического моделирования и характеризации

Проведены численные эксперименты Показана эффективность разработанных алгоритмов

11) Разработанные программные средства внедрены на ряде предприятий электронной промышленности, в том числе на предприятиях ОАО "Ангстрем-М", ФГУП "НПО Измерительной Техники", ФГУП НИИМА "Прогресс", а также в учебный процесс МГИЭТ (ТУ)

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

1 Гаврилов С В , Егоров Ю Б, Кононов А Н, Урахчин А Ф Подсистема кремниевой компиляции традиционной САПР СБИС // Электронная промышленность. - 1988 - № 9 (177) -С 6-8

2 Гаврилов С В., Кононов А Н. Инфологическая модель данных подсистемы кремниевой компиляции традиционной САПР СБИС // Электронная промышленность - 1988 - № 9 (177) -С 8-10

3 Гаврилов С В., Надежин Д Ю, Урахчин А Ф Входные языки функционально-структурного описания для подсистемы кремниевой компиляции САПР СБИС // Электронная промышленность - 1988. - №9 (177) - С 10-12

4 Гаврилов С В, Дьяков Ю.Н Алгоритмы трассировки в кремниевом компиляторе // Электронная техника, серия 3 "Микроэлектроника" - 1989 - № 2 (131) - С. 52-53

5 Гаврилов СВ., Назаров СМ, Кононов АН Процедурные возможности языка генераторов модулей // Электронная техника, серия 3 "Микроэлектроника". - 1989 - № 2 (131) -С 61-62

6 Gavnlov S , Gorlatch Е Detail Layout Optimization for Standard Cells of Arbitrary Heigh // Proc. 4-th International Design Automation Workshop (IDAW) - Moscow, June, 1994 - P 49-51

7 Gavnlov S , Glebov A, Rusakov S., Blaauw D , Jones L, Vyayan G. Fast Power Loss Calculation for Digital Static CMOS Circuits // Proc of ED&TC - Pans, 1997 - P. 411-415

8 Гаврилов С В , Глебов A JI, Лопатников С Ю Алгоритм быстрого расчета мощности для цифровых КМОП схем // 3-я международная научно-техническая конференция "Микроэлектроника и информатика" - Москва, 1997 - С 51

9 Gavnlov S, Glebov A., Pullela S, Moore S, Vyayan G, Dharchound-hury A, Panda R, Blaauw D Library-Less Synthesis for Static CMOS Combinational Logic Circuits // Proc of IEEE/ACM International Conference on Computer Aided Design

(ICCAD-97) - San Jose, CA, USA, November 9-13, 1997 -P 658-662

10 Gavrilov S, Glebov A BDD-based Circuit Level Structural Optimization for Digital CMOS // Proc of MALOPT - Moscow, Russia, September 13-14, 1999. - P 45

11 Gavrilov S., Glebov A Use of logic implications for cross-coupling noise analysis // Signal Integrity Workshop, Austin, 2000

12 Гаврил об CB, Глебов АЛ Алгоритм логического синтеза цифровых КМОП схем на проходных транзисторах // Материалы конференции - М : МГИЭТ, ноябрь 2000 - С 220

13 Gavrilov S., Glebov A, Blaauw D, etal False Noise Analysis using Logic Implications//Proc of ICCAD, 2001 -P 515

14 Gavrilov S , Glebov A, Blaauw D., et al False Noise Analysis using Resolution Method//Proc of ISQED, 2002 -P 437

15 Гаврилов С В , Глебов А Л , Стемпковский А Л Структурная оптимизация цифровых КМОП схем // Информационные технологии и вычислительные системы. - 2002 № 4 - С 34-44

16 Гаврилов СВ, Глебов АЛ, Стемпковский А,Л. Быстрый алгоритм расчета мощности в цифровых КМОП схемах // Электроника, Наука, Технология, Бизнес - 2002 - № 6

С 40-47

17 Гаврилов СВ, Глебов АЛ, Стемпковский АЛ Анализ помехоустойчивости цифровых схем на основе логических импликаций // Электроника, Известия ВУЗов - 2002 - № 5. -С 60-67

18 Gavrilov S , Glebov A., Blaauw D , et al False-Noise Analysis Using Logic Implications // ACM Trans On Design Automation of Electronics Systems -July 2002. - V 7. - Issue 3 - P 474-498

19 Gavrilov S, Zolotov V, Glebov A, Blaauw D, etal SOI transistor model for fast transient simulation // Proc of ICCAD, 2003 -P 120-127

20 Gavnlov S., Zolotov V, Glebov A, et al False-Noise Analysis for Domino Circuits // Proc of DATE - Pans, Feb 2004 - P. 784789

21 Gavnlov S, Glebov A, Soloviev R, Becer M , et al Delay Noise Pessimism Reduction by Logic Correlations // Proc of ICCAD, 2004.-P 160-167

22 Гаврилов С В, Глебов A JI, Стемпковский A JI Анализ фатальных помех в цифровых схемах на основе метода резолюций // Электроника, Известия ВУЗов - 2004 - № 6 - С 64-72

23 Гаврилов С В , Глебов A J1, Стемпковский А Л Анализ помехоустойчивости цифровых схем типа "домино" // Информационные технологии и вычислительные системы -2004 - № 10 2-7

24 Гаврилов С В., Глебов А Л, Соловьев Р А Анализ помех влияющих на задержку прохождения сигнала в цифровых СБИС, на основе логических ограничений // Электроника, Известия ВУЗов -2005 -№6 - С. 61-67

25. Гаврилов С В , Глебов А Л. Анализ помехоустойчивости цифровых схем с учетом логических ограничений // Проблемы разработки перспективных микроэлектронных систем - 2005 сб научных трудов / под общ ред. А Л Стемпковского - М ИППМ РАН, 2005 - С 72-78

26 Гаврилов С В, Соловьев Р А Анализ помех влияющих на задержку с помощью графа парных ограничений // Проблемы разработки перспективных микроэлектронных систем - 2005. сб научных трудов / под общ ред А Л Стемпковского - М ИППМ РАН, 2005 - С. 79-85

27 Gavnlov S, Glebov А, Sundareswaran S, Panda R, et al Accurate Input Slew and Input Capacitance Variations for Statistical Timing Analysis // Proc of Austin Conference on Integrated Systems & Circuits, 2006

28 Gavrilov S., Zolotov V, Glebov A, Egorov U, etal Fast Simulation of Circuitry having SOI Transistors // Motorola Patent SC12227TS, - US Patent N7127384, issued 10/24/2006.

29 Гаврилов С В , Глебов А Л , Соловьев Р А Статический временной анализ с обнаружением ложных проводящих путей на основе логических импликаций // Проблемы разработки перспективных микроэлектронных систем - 2006 сб научных трудов / под общ. ред А Л Стемпковского - М ИППМ РАН, 2006 - С 22-28

30 Гаврилов С В , Глебов А Л, Соловьев Р А Использование результатов характеризации реальных библиотек логических вентилей в статистическом временном анализе // Проблемы разработки перспективных микроэлектронных систем - 2006 сб научных трудов / под общ. ред А Л Стемпковского - М ИППМ РАН, 2006 - С 29-34

31 Гаврилов СВ, Глебов АЛ, Стемпковский АЛ Статистический подход к временному анализу цифровых схем // Известия ВУЗов Электроника - 2006 - №5 - С 99-106.

32. Гаврилов С В , Глебов А Л , Стемпковский А Л Методы повышения эффективности временного анализа СБИС // Информационные технологии - 2006 - № 12. - С. 2-12

33 Гаврилов С В , Глебов А Л, Соловьев Р А Обнаружение ложных путей в цифровой схеме на основе логических импликаций // Известия ВУЗов. Электроника - 2007 - № 2. -С. 78-84

34 Гаврилов С.В , Глебов А Л, Егоров Ю.Б, Стемпковский А Л Методы многоуровневого анализа быстродействия цифровых КМОП СБИС // Известия ВУЗов Электроника - 2007. - № 4 -С 28-36

35 Гаврилов С В , Глебов А Л, Стемпковский А Л Методы логического и логико-временного анализа цифровых КМОП СБИС-М Наука, 2007, 221с (в печати)

Введение.

Глава 1. Обзор и формализация основных моделей логического и логико-. временного анализа.

1.1. Основные понятия, термины, определения.

1.2. Формализация модели КМОП-схемы.

1.3. Обобщенный метод декомпозиции КМОП-схемы с разветвлёнными цепями земли и питания.

1.4. Формирование многоуровневой графовой модели КМОП-схемы.

1.5. Структурная интерпретация графа булевых функций в классе стандартных КМОП-вентилей.

1.6. Обобщение булевой алгебры для многозначной логики.

1.7. Разработка метода рекурсивно-вычисляемых атрибутов для анализа числовых характеристик ИС.

1.8. Выводы.

Глава 2. Анализ логических корреляций в цифровых схемах.

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

2.2. Преимущества и недостатки метода импликаций.

2.3. Адаптация метода резолюций для анализа логики цифровой КМОП-схемы

2.4. Редукция системы логических ограничений на основе обобщенного метода исключений Гаусса.

2.5. Модифицированная генерация логических импликаций в методе резолюций.

2.6. Разработка графовой модели логических ограничений КМОП-схемы

2.7. Разработка алгоритма генерации списков импликаций в методе 109 резолюций.

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

2.9. Полный алгоритм генерации ограничений на основе метода резолюций.

2.10. Экспериментальные результаты применения метода резолюций.

2.11. Выводы.

Глава 3. Разработка методов временного и логико-временного анализа цифровых КМОП-схем.

3.1. Обнаружение ложных путей в статическом временном анализе на основе логических импликаций.

3.2. Разработка алгоритмов быстрого анализа задержек для межсоединений.

3.3. Разработка алгоритмов статистического временного анализа с учетом вариаций фронтов и нагрузок.

3.4. Выводы.

Глава 4. Анализ помех в цифровых КМОП-схемах, основанный на методе резолюций.

4.1. Метод резолюций, модифицированный для анализа помех цифровой КМОП-схемы.

4.2. Анализ помехоустойчивости цифровых схем типа "домино".

4.3. Анализ помех, влияющих на задержку в цифровых СБИС.

4.4. Выводы.

Глава 5. Разработка методов многоуровневого анализа быстродействия цифровых КМОП СБИС.

5.1. Обзор современных стандартов проектирования библиотек элементов СБИС.

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

5.3. Разработка эффективных алгоритмов характеризации элементов памяти.

5.4. Статический временной анализ на основе CCS / ECSM моделей.

5.5. Разработка алгоритмов электрического моделирования на основе CCS ECSM моделей вентиля.

5.6. Реализация и практические результаты.

5.7. Выводы.

Глава 6. Характеристика программного обеспечения и экспериментальные результаты.

6.1. Состав разработанного программного комплекса.

6.2. Экспериментальные результаты по применению алгоритмов анализа и генерации логических ограничений.

6.3. Экспериментальные результаты по применению логических ограничений для анализа ложных путей.

6.4. Экспериментальные результаты по анализу задержек в межсоединениях.

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

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

6.7.Результаты анализа помех для "домино"-схем.

6.8. Результаты анализа помех, влияющих на задержку.

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

6.10. Выводы.

Актуальность темы.

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

Основной тенденцией развития интегральных микросхем является постоянное уменьшение минимальных размеров, в пределах которых может быть достигнуто успешное формирование элементов и межсоединений на кристалле. Ключевым параметром в современных технологиях является минимальный размер затвора транзистора, который уменьшается примерно в 1,5 раза каждые два года [1]. На рубеже тысячелетий началось производство с применением технологических норм 130, 90 и 65 нм. К 2007 году ведущие западные микроэлектронные компании освоили массовое производство для технологий с нормой 65нм, начали разработки проектов для технологий с нормой 45нм, а также разработку перспективных библиотек и функциональных блоков для технологий с нормой 32нм.

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

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

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

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

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

• Большие вычислительные затраты при точном анализе проектов на электрическом и топологическом уровне.

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

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

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

Состояние проблемы.

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

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

Противоположными свойствами обладают специализированные методы логического уровня, ориентированные на анализ верхней возможной оценки той или иной характеристики схемы. К числу таких характеристик относятся, в частности, максимально-возможная задержка, максимально-возможная помеха, максимально-возможная потребляемая мощность, максимально-возможный скачок напряжений (IR-drop) и др. Речь идет о методах, ориентированных на анализ худшего случая, гарантирующих оценку сверху, какими бы ни были входные воздействия. В последние несколько лет специализированным методам такого класса уделялось много внимания в литературе. Наибольшее распространение в реальных маршрутах проектирования получили следующие подсистемы, основанные на таком подходе:

• подсистемы статического временного анализа (СВА) для верхней оценки задержек на основе поиска критических путей (PrimeTime фирмы Synopsys и СТЕ Encounter фирмы Cadence);

• подсистемы для оценки влияния помех емкостных связей межсоединений на логику работы и быстродействие схемы (Celtic-NDC (Cadence), PrimeTime-Sl(Synopsys)).

Статический временной анализ (СВА) предназначен для оперативной оценки быстродействия комбинационных блоков в синхронных цифровых схемах. Цель СВА - найти множество критических путей [77] в комбинационных блоках для последующей оценки периода и частоты функционирования схемы. СВА является реальной возможностью решить указанную задачу, хотя решение и является зачастую излишне пессимистичным, т.е. приводит к завышенным оценкам, поскольку не учитывается логика работы схемы. В ряде публикаций [71-76] предпринимались попытки учесть логику, т.е. решить задачу истинности или ложности критического пути. Однако эти методы не нашли широкого применения в коммерческих системах, поскольку сама такая задача является NP-полной, и не существует эффективных алгоритмов для схем большой размерности. Для преодоления этой проблемы в системах Prime Time, Encounter предусмотрен интерфейс ручного указания ложных путей, который не может быть эффективен для сложных схем большой размерности.

Аналогичная проблема связана с анализом влияния емкостных связей межсоединений на логику работы и быстродействие схемы. Для перспективных глубоко субмикронных и нанометровых технологий до 60-80% полной емкости межсоединений составляет емкость межпроводниковых связей. Это приводит к резкому возрастанию помех (паразитных сигналов), индуцируемых в проводниках другими (соседними) проводниками. Эта тенденция приводит к возрастающей потребности в алгоритмах и программах анализа помех в цифровых СБИС [91-94]. При анализе помех узел, в котором рассматривается помеха, обычно называют "узлом-жертвой", тогда как соседние узлы, индуцирующие помеху, называют "узлами-агрессорами". "Узел-жертва" и группа "узлов-агрессоров" вместе образуют кластер. Наиболее простой вид анализа помех исходит из предположения о том, что все "узлы-агрессоры" могут переключаться одновременно и в одном направлении [91, 93]. Однако получаемая при этом оценка максимальной помехи обычно является чрезмерно пессимистической. Она может быть уточнена различными способами. В коммерческих САПР реализованы методы, основанные на результатах статического временного анализа (Celtic-NDC (Cadence), PrimeTime-SI(Synopsys)). Первые попытки учесть логику работы схемы при анализе помехоустойчивости были предприняты в работах [92, 95-96], однако они не были реализованы в промышленных системах из-за большой вычислительной сложности.

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

В этой связи одной из главных задач диссертации является разработка комплекса математических алгоритмов, ориентированных на повышение достоверности и надежности логико-временного анализа и логического анализа с учетом влияния помех межсоединений. Задача решается на основе метода анализа и распространения логических ограничений в схеме, предложенного в работах с участием автора [3-10, 78, 80, 118-119].

Известно, что даже ответ на вопрос о существовании или отсутствии какого-либо одного конкретного логического ограничения представляет собой проблему большой сложности. Такая проблема известна в литературе, как SAT-проблема (Satisfactory problem) [56-59, 127]. Известно, что k-SAT проблема является NP-полной при к>2 [56-59] и имеет полиномиальную сложность при к=2 [56]. Есть много подходов для решения этой проблемы, например, метод проб с возвратами (Backtracking) [60], метод локальных проб (автор метода - Smallmark), метод рекурсивного обучения (Recursive Learning) [61,62, 107] и др. Однако все алгоритмы полного решения SAT-проблемы эффективны лишь для схем небольшой размерности.

В диссертационной работе предлагается иной подход. А именно, вместо решения NP-полной проблемы для конкретных ограничений, предлагаются быстрые методы целенаправленного поиска и генерации большого количества логических ограничений для решения конкретных прикладных задач оценки задержек и помех. Прообразом такого подхода послужил метод распространения простых логических импликаций (ПЛИ), предложенный в работах Bobba S., Hajj I.N. [103] для учета логики работы схемы при решении задачи оценки максимального суммарного пикового тока в схеме. Дальнейшее развитие метод простых логических импликаций получил в работах с участием автора при первых попытках учесть логику работы схемы в анализе помехоустойчивости [4, 78]. Была показана эффективность таких методов применительно к комбинационным цифровым схемам, состоящим из относительно небольших DCCC (DC connected component, или подсхем, связанных по постоянному току). Однако при применении этих методов к промышленным схемам возникал ряд проблем:

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

• Проблема экстракции логики для DCCC со многими выходами и DCCC большого размера.

• Огромное количество ПЛИ (простых логических импликаций), особенно в присутствии резистивных деревьев (сеток) и деревьев инверторов/буферов.

• Трудности, связанные с учетом импликаций более сложных, чем ПЛИ (3-ЛИ, 4-ЛИ,., N-ЛИ).

Теоретическое развитие, обобщение и внедрение в практику логического и логико-временного анализа метод учета логического ограничений в сочетании с точными моделями библиотечных элементов получил в работах автора, вошедших в диссертацию [3-10, 41-43, 48, 80, 97, 105, 108, 118-119].

Цель диссертационной работы.

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

Объект исследования.

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

Задачи исследования.

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

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

1)Разработка и исследование эффективных методов анализа логических корреляций в КМОП-схеме, в том числе для схем на транзисторном уровне, восстановленных из топологии.

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

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

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

5) Разработка новых методов логико-электрического анализа быстродействия на основе современных стандартов проектирования библиотек элементов, ориентированных на уточнённый анализ межсоединений.

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

Методы исследования.

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

Научная новизна.

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

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

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

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

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

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

- Разработан алгоритм генерации логических ограничений в динамических схемах типа "домино". Эффективность предлагаемого алгоритма основана на учете возможности одновременного непроводящего состояния верхней и нижней цепей "домино"-вентиля.

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

На защиту выносятся следующие положения и научные результаты:

1) Новый подход к анализу логических ограничений в КМОП-схеме на основе метода резолюций, обеспечивающий поиск логических ограничений на транзисторном уровне, в том числе для схем, восстановленных из топологии.

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

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

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

5) Методы логико-электрического анализа быстродействия на основе современных стандартов проектирования библиотек элементов, ориентированных на уточнённый анализ межсоединений.

Реализация научно-технических результатов работы.

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

Достоверность результатов.

Достоверность результатов, представленных в работе, подтверждается согласованностью с известными подходами, опубликованными в литературе, адекватностью математических моделей, многочисленными результатами экспериментальной проверки предложенных методов с использованием разработанного на их основе программного обеспечения, согласованностью результатов работы разработанного программного обеспечения с результатами других систем автоматизированного проектирования, такими как Synopsys (Prime Time, Design Compiler), Cadence (Celtic, Encounter), Spice.

Практическая ценность.

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

Апробация работы.

Основные результаты работы докладывались и обсуждались на научных семинарах в ИППМ РАН, на Европейской конференции по проектированию и тестированию интегральных схем "ED&TC" (Франция, Париж, 1997), 3-й международной конференции "Микроэлектроника и информатика" (Москва, 1997), 1-м международном семинаре по проектированию мульти-архитектурных низкомощных интегральных схем "MALOPD" (Москва, 1999), Международном семинаре по помехоустойчивости интегральных схем "Signal Integrity Workshop" (США, Остин, 2000), 3-й международной конференции "Электроника и информатика - XXI век" (Москва, 2000), Международной конференции по компьютерному проектированию интегральных схем "ICCAD" (США, Сан-Хосе, 2001), Международном симпозиуме по качественному проектированию интегральных схем "ISQED" (США, Сан-Хосе, 2002), Международной конференции по компьютерному проектированию интегральных схем "ICCAD" (США, Сан-Хосе, 2003), Европейской конференции по проектированию и тестированию интегральных схем "DATE" (Франция, Париж, 2004), Международной конференции по компьютерному проектированию интегральных схем "ICCAD" (США, Сан-Хосе, 2004), на Всероссийской научно-технической конференции "Проблемы разработки перспективных микроэлектронных систем -2005" (МЭС) (Москва, 2005), Международной конференции по интегральным системам и схемам "ACISC" (США, Остин, 2006), Всероссийской научно-технической конференции "Проблемы разработки перспективных микроэлектронных систем - 2006" (МЭС) (Москва, 2006), Международном симпозиуме корпорации Intel по проектированию интегральных схем и технологическим решениям (Израиль, Хайфа, 2007).

Публикации.

Список опубликованных по теме диссертации научных трудов составляет 35 работ, в их числе монография и 7 статей, опубликованных в научных журналах, входящих в Перечень периодических изданий, рекомендованных ВАК РФ для публикаций основных результатов диссертаций на соискание степени доктора наук [6,9-10,78,80,118-119].

Структура и объем работы.

Диссертация состоит из введения, шести глав, заключения и списка литературы из 127 пунктов.

Основные результаты шестой главы:

1) Разработано программное обеспечение для логического, логико-электрического и логико-временного анализа цифровых субмикронных КМОП-схем, включающее в себя следующие программные системы:

- систему анализа и генерации логических ограничений;

- систему временного анализа;

- систему анализа помехоустойчивости;

- систему ускоренного электрического моделирования и характеризации.

2) Проведены численные эксперименты. Показана эффективность разработанных алгоритмов.

Заключение Основные результаты диссертации:

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

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

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

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

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

6. Предложен новый подход к анализу помехоустойчивости высокоскоростных "домино"-схем посредством учета корреляций между сигналами, налагающих запрет на одновременное переключение "узлов-агрессоров", индуцирующих помеху в "узле-жертве". Эффективность предлагаемого подхода основана на учете возможности одновременного непроводящего состояния верхней и нижней цепей "домино"-вентиля. Метод резолюций обобщен путем включения в него алгоритма рекурсивного обучения. Данный подход позволяет генерировать большое число дополнительных ограничений для схем с избыточным кодированием сигналов, широко используемых в высокопроизводительных АЛУ и за счет этого приводит к значительному снижению пессимизма в оценке максимальной помехи. Результаты численных экспериментов показывают высокую эффективность предложенного метода, способного исключить до 29% "узлов-агрессоров" из их полного числа.

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

8. Разработан новый подход к характеризации логических элементов и элементов памяти, включающий в себя: автоматическую генерацию сглаженных фронтов источников напряжений на основе сплайн-аппроксимации; встроенный алгоритм многократного электрического моделирования для разных вариантов входных фронтов и емкостей нагрузок; встроенные алгоритмы вычисления интегральных параметров схемы (задержек, фронтов, потребляемой мощности, времени удержания и установления для элементов памяти). Предлагаемый подход обеспечивает повышение быстродействия характеризации по сравнению со стандартным маршрутом характеризации в 10-15 раз для логических вентилей и в 30-50 раз для элементов памяти при сохранении точности моделирования в пределах 10% по сравнению с обычным электрическим моделированием.

9. Разработаны новые методы логико-электрического моделирования на основе токовых моделей вентиля CCS/ECSM. В отличие от известных методов смешанного моделирования предлагаемый подход основан на адаптации моделей, используемых в коммерческих системах Synopsys, Cadence, и благодаря этому обеспечивает интеграцию с промышленными маршрутами проектирования и не требует какой-либо дополнительной характеризации макромодели вентиля.

10.Разработан комплекс программных средств для логического, логико-электрического и логико-временного анализа цифровых глубоко субмикронных КМОП-схем, включающее в себя следующие программные системы:

- систему анализа и генерации логических ограничений;

- систему временного анализа;

- систему анализа помехоустойчивости;

- систему ускоренного электрического моделирования и характеризации.

4.3.5. Заключение

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

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

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

1. Moore G.E. Cramming more components onto integrated circuits // Electronics, 1965. Vol. 38, N8. P. 114-117.

2. Казенное Г.Г. Основы проектирования интегральных схем и систем // Бином, Лаборатория знаний, 2005, 295 с.

3. Gavrilov S., Zolotov V., Glebov A. et.al. False-noise analysis for domino circuits // Proc. of DATE, Paris Feb. 2004. P. 784-789.

4. Gavrilov S., Glebov A., Soloviev R. et.al. Delay noise pessimism reduction by logic correlations // Proc. of ICCAD, 2004. P. 160-167.

5. Гавршов С.В., Глебов A.JI., Стемпковский A.J1. Анализ помехоустойчивости цифровых схем типа "домино" // Информационные технологии и вычислительные системы. 2004. № 10. С. 60.

6. Гавршов С.В., Глебов А.Л., Соловьев Р.А. Анализ помех влияющих на задержку прохождения сигнала в цифровых СБИС, на основе логических ограничений // Изв. вузов. Электроника. 2005. № 6. С. 61-67.

7. Гавршов С.В., Соловьев Р.А. Анализ помех влияющих на задержку с помощью графа парных ограничений // Там же. С.79-85.

8. Гавршов С.В., Глебов А.Л., Стемпковский А.Л. Методы повышения эффективности временного анализа СБИС // "Информационные технологии".2006. № 12. С. 2-12.

9. Гавршов С.В., Глебов А.Л., Соловьев Р.А. Обнаружение ложных путей в цифровой схеме на основе логических импликаций // Изв. вузов. Электроника.2007. № 2. С. 78-84.

10. Brown F.M. Boolean reasoning. The logic of Boolean equations // Boston; Dordrecht; London: Kluwer Academic Publishers, 1990. 273 p.

11. Meinel Ch. Theobald Th. Algorithms and data structures in VLSI design // Berlin: Springer-Verlag, 1998. 268 p.

12. Клини C.K. Математическая логика // M.: УРСС, 2005. 480 с.

13. Мендельсон Э. Введение в математическую логику // М.: Наука, 1984. 320с.

14. Керниган Б., Ритчи Д., Фьюэр А. Язык программирования СИ // М.: Финансы и Статистика, 1985. 279 с.

15. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции // М.: Мир, 1978. Т. 1, 2. 612+486 с.

16. Хантер Р. Проектирование и конструирование компиляторов // М.: Финансы и статистика, 1984. 231с.

17. Грис Д. Конструирование компиляторов для цифровых вычислительных машин // М.: Мир, 1975. 544 с.

18. Bryant R.E. Algorithmic aspects of symbolic switch network analysis // IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 1987. Vol. CAD-6(4). P. 618-633, July.

19. Bryant R.E. Boolean analysis of MOS circuits // Ibid. P. 634-649, July.

20. Математическая энциклопедия / Под ред. И.М Виноградова М.: Советская энциклопедия, 1977. Т. 1. 1152 с.

21. Bryant R.E. Graph-Based Algorithms for Boolean Function Manipulation // IEEE Trans, on Computers. 1986. Vol. 35. P. 677.

22. Brace K.S., Rudell R.L., Bryant R.E. Efficient Implementation of a BDD Package // Proc. of the 27th DAC. 1990. P. 40-45.

23. Bryant R.E. Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams // ACM Computing Surveys. 1992. Vol. 24, N 3. P. 293-318.

24. Ope О. Теория графов. M.: Наука, 1980. 336 с.

25. Харри Ф. Теория графов. М.: УРСС, 2003. 300 с.

26. Касьянов В.Н., Евстигнеев В.А. Графы в программировании. СПб: БХВ-Петербург, 2003. 1104 с.

27. Зыков А.А. Основы теории графов. М.: Наука. 1987. 382 с.

28. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука. 1990. 384 с.

29. Minato, S., Ishiura N., Yajima S. Shared Binary Decision Diagram with Attributed Edges for Efficient Boolean Functions Manipulation // Proc. of the 27th DAC. 1990. P 52-57.

30. Точчи Р.Дж., Уидмер H.C. Цифровые системы. Теория и практика. М.; С.Петербург; Киев: Вильяме, 2004. 1024 с.

31. Киносита К., Асада К., Карацу О. Логическое проектирование СБИС. М.: Мир, 1988. 309 с.

32. Токхейм Р. Основы цифровой электроники. М.: Мир, 1988. 392 с.

33. Koegst М., Franke G., Berndt Th, Feske К. FSM state assignment for low power and power estimation under user-specified input sequences // Baltic Electronics Conf., Oct. 1996, Tallin, Estonia, P. 385-388.

34. Bryant R.E. A Switch-Level Model and Simulator for MOS Digital Systems // IEEE Trans, on Computers, 1984. Vol.33, P.160.

35. Vladimirescu A., Zhang K., Newton A.R. et.al. SPICE Version 2G User's Guide // Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Ca., 94720; 1981.

36. Payer M. Partitioning and ordering of CMOS circuits for switch level analysis // Integration of VLSI journal, 1991. N 10. P.l 13-141.

37. Tsui C.Y., Pedram M., Despain A.M. Technology Decomposition and Mapping Targeting Low Power Dissipation // Proc. of 30st ACM/IEEE Design Automation Conf. (DAC), 1993. P.68.

38. Tiwari V., Ashar P., Malik S. Technology Mapping for Low Power // Ibid. P. 74.

39. GlebovA., Gavrilov S., Pullela S. et. al. Library-Less Synthesis for Static CMOS Combinational Logic Circuits // Proc. of IEEE/ACM Intern.Conf.on Computer Aided Design (ICCAD-97), San Jose, CA, USA, November 9-13, 1997. P.658-662.

40. Gavrilov S., Glebov A. BDD-based Circuit Level Structural Optimization for Digital CMOS // Proc. of MALOPT, Moscow, Russia, September 13-14, 1999. P. 45.

41. Гаврилов С.В., Глебов A.JJ. Алгоритм логического синтеза цифровых КМОП-схем на проходных транзисторах // 3-я Междунар. конф. "Электроника и информатика XXI век". М. МИЭТ. 2000. С. 220.

42. Kick В. Timing Correction in Logic Synthesis // Proc. of 1st Int. Conf. "VLSI and Computers", Hamburg, May 11-15, 1987. P. 299.

43. Глориозов E.JI. Метод структурного схемотехнического синтеза электронных схем // Изв. Вузов. Радиоэлектроника, 1979. Т. 22. № 6. С. 7.

44. Шагурин И.И. Основы формального схемотехнического синтеза цифровых микросхем на биполярных транзисторах // Микроэлектроника. 1979. Т. 8. № 2. С. 114.

45. Кармазинский А.Н. Синтез принципиальных схем цифровых элементов на МДП-транзисторах . М.: Радио и связь. 1983. 256 с.

46. Gavrilov S., Glebov A., Rusakov S. et. al. Fast Power Loss Calculation for Digital Static CMOS Circuits // Proc. of ED&TC, Paris, 1997. P. 411-415.

47. Blaauw D. Т., Zolotov V, Dasgupta A. Static Electromigration Analysis for On-Chip Signal Interconnects // IEEE Trans. On CAD. 2003. Vol. 22, N 1.

48. Swenson G. W., Higgins T.J. Direct-Current Network Analyzer for Solving Wave-Equation Boundary-Value Problems // J. Appl. Phys. 1952. Vol. 23. Issue 1. P. 126-131.

49. Van der Aalst W.M.P. The application of Petty nets to workflow management // J. Circuits, System and Computers, 1998. Vol. 8 (1). P.21-66.

50. Kishinevsky M., Kondratyev A., Taubin A., Varshavsky V. Concurrent hardware: The theory and practice of self-timed design // London: John Wiley and Sons, 1993.

51. Caisso J.-P., Cerny E., Rumin N. C. A recursive technique for Computing Delays in Series-Parallel MOS Transistors Circuits // IEEE Trans, on CAD, 1991. Vol.10, N 5. P. 589-595.

52. Palnitkar S. Verilog HDL: A Guide to Digital Design and Synthesis. Second ed. Prentice Hall 2003. 496 p.

53. Blaauw D.T., Saab D.G., Mueller-Thuns R.B. et. al. Automatic Generation of Behavioral Models from Switch-Level Descriptions // Proc. Of DAC 26th. 1989. P. 179184.

54. Gent I.P., Walsh Т. The SAT Phase Transition // Proc. of ECAI-94, London: John Wiley & Sons. 1994. P. 105-109.

55. Gent I.P., Walsh T. An Empirical Analysis of Search in GSAT // Journal of Artificial Intelligence Research. 1993. Vol. 1. P. 45-56.

56. Zhang L., Malik S. Validating SAT Solvers Using an Independent Resolution-Based Checker: Practical Implementations and Other Applications // Proc. of DATE, Paris, 2003. P. 880-885.

57. Li Bin, Hsiao M.S. Sheng Sh. A Novel SAT All-Solutions Solver for Efficient Preimage Computation // Proc. of DATE. Paris, 2004. P. 272-279.

58. Marques-Silva J.P, Sakallah A. Grasp: A search algorithm for prepositional satisfiability // IEEE Trans, on Computers -1999. Vol. 48. P. 506-521

59. Silva J.P., Glass T. Combinational equivalence checking using satisfiability and recursive learning // Proc. of DATE. 1999. P. 145-149.

60. Zhang L., Madigan C., Moskewicz M., Malik S. Efficient conflict driven learning in a Boolean satisfiability solver // Proc. of ICCAD. 2001, P. 279-285.

61. Chang C.L., R.C.T.Lee Symbolic Logic and Mechanical Theorem Proving // New York: Acad. Press, 1973.

62. Ченъ Ч., Ли P. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. 360 с.

63. Маслов С.Ю. Обратный метод установления выводимости для логических исчислений // Труды МИАН. 1968. Т. 98. С. 26-87.

64. Беклемишев Д.В. Курс аналитической геометрии и линейной алгебры. М.: Физматлит, 2003. 376 с.

65. ЛипскийВ. Комбинаторика для программистов. М.: Мир, 1988. 213 с.

66. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981. 323 с.

67. Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1989. 360 с.

68. Рейнгольд Э., Нивергелъд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 476 с.

69. Атоп Т., Borriello G. An approach to symbolic timing verification // DAC. 1992. P. 410-412.

70. Gladstone В. Accurate timing analysis holds the key to performance in today's system designs 11EDN. 1993.

71. Overhauser D. Fast timing simulation of MOS VLSI circuits // Ph.D. Thesis. -University of Illinois at Urbana-Champaign. 1989.

72. Dharchoudhury A., Kang S.M., Kim K.H., Lee S.H. Fast and accurate timing simulation with regionwise quadratic models of MOS I-V characteristics // ICCAD. 1994. P. 190-194.

73. Hitchcock R.B. Timing verification and the Timing analysis Program // DAC. 1982. P. 594-604.

74. Reddi R., Chen C. Hierarchical Timing Verification System // Computer Aided Design. Vol. 18. 9, November 1986. P. 467-477.

75. Yen S., Du D., Ghanta S. Efficient Algorithms for Extracting the К Most Critical Paths in Timing Analysis // DAC. 1989. P. 649-654.

76. Гаврилов С.В., Глебов A.JI., Стемпковский А.Л. Анализ помехоустойчивости цифровых схем на основе логических импликаций // Изв. вузов. Электроника. 2002. № 5. С. 60-67.

77. Robinson J.A. A Machine-Oriented Logic Based on the Resolution Principle // J. of the ACM. 1965. 12(1). P. 23-41.

78. Гаврилов С.В., Глебов А.Л., Стемпковский А.Л. Анализ фатальных помех в цифровых схемах на основе метода резолюций // Изв. вузов. Электроника. 2004. № 6. С. 64-72.

79. Alpert С. J., Liu F., Kashyap С. V., Devgan A. Closed-form delay and slew metrics made easy // IEEE Trans, on CAD. 2004. Vol.23. P. 1661.

80. Kashyap C.V., Alpert C.J., Liu F., Devgan A. Closed Form Expressions for Extending Step Delay and Slew Metrics to Ramp Inputs // ISPD-2003. P.24.

81. Alpert C.J., Devgan A., Kashyap C.V. RC delay metrics for performance optimization // IEEE Trans, on CAD. 2001. Vol. 20, P.571.

82. О Brien P.R., Savarino T.L. Modeling the driving-point characteristic of resistive interconnect for accurate delay estimation // ICCAD-89. P.512.

83. Orshansky M., Keutzer К A general probabilistic framework for worst case timing analysis // DAC-2002. P. 556- 561.

84. Jess J.A.G., Kalafala K, Naidu S.R. et.al. Statistical timimg for parametric yield prediction of digital integrated circuits // DAC-2003. P. 932-937.

85. Visweswariah C., Ravindran K., Kalafala K. First-order parameterized block-based statistical timing analysis // TAU-2004. P. 17-24.

86. Le J., Li X., Pileggi L.T. STAC: Statistical timing analysis with correlation // DAC-2004. P. 343-348.

87. Devgan A., Kashyap C. Block-based static timing analysis with uncertainty // ICCAD-2003. P. 607-614.

88. Clark C.E. The greatest of a finite set of random variables // Operations Research. 1961. P. 145-162.

89. Levy R., Blaauw D., Braca G. et.al. ClariNet: A noise analysis tool for deep submicron design // DAC-2000. P. 233-238.

90. Chen P., Keutzer K. Towards True Crosstalk Noise Analysis // ICCAD-99. P. 132137.

91. Shepard K.L. Design methodologies for noise in digital integrated circuits // Proc. DAC. 1998. P. 94-99.

92. Shepard K.L. Design methodologies for noise in digital integrated circuits // DAC-98. P. 94-99.

93. Rubio A., Itazaki N., Xu X., Kinoshita K. An Approach to the Analysis and Detection of Crosstalk Faults in Digital VLSI Circuits // IEEE Trans, on CAD. 1994. Vol.13. N3. P. 387 -395.

94. Kirkpatrick D.A., Sangiovanni-Vincentelli A.L. Digital Sensitivity: Predicting Signal Interaction using Functional Analysis // ICC AD-96. P.536-541.

95. Glebov A., Gavrilov S., Blaauw D. et.al. False-Noise Analysis using Logic Implications // ICCAD-2001. P. 515-520.

96. Brown F.M. Boolean reasoning. Kluwer Acad. Publ.1990.

97. Hachtel G., Jacoby R., Moceyunas P., Morrison C. Performance Enhancements in BOLD using Implications // ICCAD-88. P. 94-97.

98. Kunz W., Menon P.R. Multi-Level Logic Optimization by Implication Analysis // ICCAD-94. P.6-13.

99. Bahar R.I., Burns M., Hachtel G.D. et.al. Symbolic Computation of Logic Implications for Technology-Dependent Low-Power Synthesis // ISPLED-96. P. 163168.

100. Long W., Wu Y.L., Bian J. IBAW: An Implication-Tree Based Alternative-Wiring Logic Transformation Algorithm //ASPDAC-2000. P. 415-422.

101. Bobba S., Hajj I.N. Estimation of maximum current envelope for power bus analysis and design // Int. Symp. on Phys. Des., 1998. P. 141-146.

102. Wroblewski A., Schimpfle C.V., Nossek J.A. Automated Transistor Sizing Algorithm for Minimizing Spurious Switching Activities in CMOS Circuits // ISCAS-2000. P.291-294.

103. Glebov A., Gavrilov S., Blaauw D„ Zolotov V. False-noise analysis using logic implications // ACM Trans, on Design Automation of Electronic Systems (TODAES).2002. Vol. 7. N3. P. 474-498.

104. Актуальные проблемы моделирования в системах автоматизации схемотехнического проектирования / Под ред. А.Л.Стемпковского. М.: Наука,2003. 429 с.

105. Kunz W., Pradham D.K. Recursive learning: a new implication technique for efficient solutions to CAD problems test, verification and optimization // IEEE Trans, on CAD. 1994. Vol.13. P. 1143-1158.

106. Glebov A., Gavrilov S., Blaauw D. et.al. False noise analysis using resolution method // ISQED 2002. P. 437-442.

107. Loukakis E., Tsouros C. An Algorithm for the Maximum Internally Stable Set in a Weighted Graph // Intern. J. Computer Math. 1983. Vol.13. P.l 17-129.

108. Library Compiler™ User Guide: Methodology and Modeling Functionality Technology Libraries, Version U-2003.03 // March 2003, Synopsys.

109. Liberty User Guide Reference Manual, Version 2006.06 // June 2006, Synopsys.

110. CCS Timing Technical White Paper, Version 2.0 // 2006, Synopsys.

111. Mekhtarian G. High Accuracy Delay Calculation for Deep Submicron Technologies // Compiler (Synopsys), May 2006

112. Open Source ECSM Format Specification. Version 1.2 // Sep. 2005, Cadence Design System

113. Premal Buch Understanding ECSM and CCSVM // MagmaWire Vol. 3. N 4. Nov. 2004.

114. Алберг Дж., Нилъсон Э., Уолш Дж. Теория сплайнов и ее приложения. М.: Мир, 1972. 318 с.

115. Пирумов У. Г. Численные методы. М.: Дрофа, 2003. 224 с.

116. Гаврилов С.В., Глебов А.Л., Стемпковский А.Л. Статистический подход к временному анализу цифровых схем // Известия ВУЗов. Электроника 2006. - № 5.-С. 99-106.

117. Гаврилов С.В., Глебов А.Л., Егоров Ю.Б., Стемпковский А.Л. Методы многоуровневого анализа быстродействия цифровых КМОП СБИС // Известия ВУЗов. Электроника. 2007. - № 4. - С. 28-36.

118. Ye X., Li P., Liu F. Practical Variation-A ware Interconnect Delay and Slew Analysis for Statistical Timing Verification // ICCAD-2006. P. 54-59.

119. Bhardwaj S., Ghanta P., Vrudhula S. A Framework for Statistical Timing Analysis Using Non-Linear Delay and Slew Models // ICCAD-2006. P. 225-230

120. Ramalingam A., Singh A. K., Nassif S. R., Nam G.-J., Orshansky M., Pan D. Z. An Accurate Sparse Matrix Based Framework for Statistical Static Timing Analysis // ICCAD-2006. P. 231-236.

121. Chopra K., Zhai В., Blaauw D., Sylvester D. A New Statistical Max Operation for Propagating Skewness in Statistical Timing Analysis //ICCAD-2006. P. 237-243.

122. Zhou S., Zhu Y., Ни Y., Graham R., Hutton M., Cheng C.-K. Timing Model Reduction for Hierarchical Timing Analysis //ICCAD-2006. P. 415-422.

123. Zhang M., Olbrich M., Seider D., Frerichs M., Kinzelbach H. , Barke E. CMCal: An Accurate Analytical Approach for the Analysis of Process Variations with Non-Gaussian Parameters and Nonlinear Functions // DATE-2007 .P.243-248.

124. Srivastava S., Roychowdhury J. Rapid and Accurate Latch Characterization via Direct Newton Solution of Setup/Hold Times //DATE-2007.P. 1006-1011.

125. Проектирование и конструирование ГО47"1к.т.н., доцент2 71

126. УТВЕРЖДАЮ" Генеральный Директор ОАО «Ангстрем-М»1. Машевич П.Р.1. О 22007 г.

127. АКТ ВНЕДРЕНИЯ Результатов диссертационной работы Гаврилова С.В. на соискание ученой степени доктора технических наук. Тема диссертации: "Методы логического и логико-временного анализа для

128. САПР нанометровых КМОП СБИС"

129. Эффективность предложенных в диссертационной работе алгоритмов и моделей представления проектной информации подтверждена практическим опытом проектирования реальных микросхем.1. Главный специалист1. А.П. Подобаев1. У. А

130. УТВЕРЖДАЮ" Генеральный Директор

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

132. Результаты диссертации применялись в рамках научно-исследовательских и опытно-конструкторских работ ФГУП НИИМА "Прогресс".

133. Первый зам. директора по науке1. Корнеев И.Л.

134. АКТ ВНЕДРЕНИЯ результатов диссертационной работы Гаврилова С.В. на соискание ученой степени доктора технических наук. Тема диссертации: "Методы логического и логико-временного анализа для

135. САПР нанометровых КМОП СБИС"

136. Ученый секретарь, д.т.н., профессор1. Козлов А.А./1. Начальник отдела1. Черный А.И.1. Начальник сектора, к.т.н.о1. Поварницына З.М.и-a1. УТВЕРЖДАЮ"1. Директор1. МЭИИТ МИЭМ>1. Соколов А. Б.2007 г.

137. Акт внедрения результатов докторской диссертации Гаврилова С.В. "Методы логического и логико-временного анализа для САПР нанометровых1. КМОП СБИС".