27

Размещено на http://www.allbest.ru/

Автореферат

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

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

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

Гаврилов Сергей Витальевич

Москва - 2007

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

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

доктор технических наук, профессор Норенков И.П.

доктор технических наук, профессор Казеннов Г.Г.

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

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

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

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

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

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

диссертационного совета Д 002.078.01

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

А.И. Корнилов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- Разработан алгоритм формирования характеристической 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 статей в научных журналах, входящих в Перечень периодических изданий, рекомендованных ВАК РФ для публикаций основных результатов диссертаций на соискание степени доктора наук.

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

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

2. Основное содержание работы

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

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

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

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

· - множество первичных входов;

· - множество первичных выходов;

· - выделенный узел земли;

· - выделенный узел питания;

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

(1) - для N-МОП транзистора,

(2) - для P-МОП транзистора,

(3) - для повторителя напряжения или линейного сопротивления.

Теоретико-графовая модель КМОП-схемы (КМОП-граф) определяется, как неориентированный граф , построенный на основе по специальным формализованным правилам. Цепь земли и цепь питания определяются как связные подграфы графа , соединенные ответственно с посредством пассивных элементов. Для решения проблемы декомпозиции для схем с разветвленными шинами питания и земли вводятся формальное обобщенное определение подсхемы элементов, связанных по постоянному току (сокращенно DCCC - direct current connected component):

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

(1) заданное ребро принадлежит DCCC: ;

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

(3) для всех узлов DCCC, кроме узлов цепей питания и земли, все ребра, инцидентные узлу DCCC, принадлежат DCCС, т.е.: если и , то;

(4) , - тогда и только тогда, когда они могут быть добавлены в DCCC на основе правил (1), (2),(3).

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

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

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

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

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

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

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

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

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

В целях сокращения опускается “=0”. Таким образом, например, система ограничений для вентиля AND будет записываться как , а правило резолюции может быть записано как ().

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

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

· Для каждого МОП-транзистора P-типа на основе соотношения добавляются два ограничения: .

· Для каждого линейного сопротивления (x,y - выводы сопротивления) на основе соотношения добавляются два ограничения: .

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

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

· В отличие от ранее известного метода распространения ПЛИ (Bobba S., Hajj I.N.), транзитивный закон и правило объединения не используются. Остальная часть алгоритма модифицирована таким образом, чтобы не хранить ПЛИ, которые можно получить применением транзитивного закона к существующим ПЛИ.

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

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

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

Для описания степеней в логическом ограничении предлагается маркировка гиперребер на основе специального кода, который назван B-кодом. Заданное логическое ограничение описывается A-кодом, представляющим собой целочисленную кодировку двоичного вектора , определяемую по следующей формуле:

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

, где

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

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

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

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

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

Наряду с необходимостью учета логических корреляций другой существенной проблемой при переходе на глубоко субмикронные и нанометровые технологии является возрастающая роль вариаций технологических и схемных параметров. В связи с этим, за последние 2-3 года широкое распространение получили методы блочного статистического временного анализа с оценкой вариаций задержек (Kalafala K., Pilleggi L.T., Clark C.E. и др.) в линеаризованной форме по отношению к вариациям глобальных () и локальных параметров ():

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

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

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

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

В современных САПР (Synopsys, Cadence, и др.) наиболее распространенной и широко используемой моделью для характеризации библиотечных элементов является так называемая нелинейная модель задержки - Non-Linear Delay Model (NLDM) в формате Liberty (Synopsys). Модель NLDM представляет собой нелинейные зависимости задержек выходных сигналов D_out от длительности фронта входного сигнала T_inp и емкости нагрузки C_out в форме двумерных таблиц , k [1: Ns], l [1: Nc]. Аналогичными таблицами представляются и зависимости длительности фронта выходного сигнала T_out от тех же переменных: , k [1: Ns], l [1: Nc]. Емкость нагрузки C_out в свою очередь зависит от входных емкостей C_inp,l нагружающих вентилей. Поскольку T_inp и C_inp также имеют вариации, зависящие от вариаций глобальных и локальных параметров, они вносят непрямую составляющую в чувствительности задержки вентиля и длительности его выходного фронта. Основная идея предлагаемого подхода заключается в линеаризации вариаций выходной задержки D с учетом вариаций входных фронтов , выходной нагрузки и входных емкостей нагружающих вентилей согласно следующей формуле:

,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

После того, как выполнена генерация ПЛИ, анализ помех производится отдельно для каждого кластера и соответствующего типа помехи. Для анализа помех в кластере предложен алгоритм генерации характеристической ROBDD Предположим, что кластер содержит “узел-жертву” v и “узлы-агрессоры” a₁,...,a_n. Характеристическая функция кластера f(v,a₁,...,a_n) - это функция, которая равна 1 для совместимых комбинаций своих аргументов (комбинаций, удовлетворяющих всем ограничениям), и равна 0 во всех остальных случаях. Для формирования характеристической ROBDD, т.е. ROBDD для характеристической функции кластера, используются найденные логические ограничения.

Рис. 1. Пример схемы, набор логических ограничений и фрагмент характеристической ROBDD

Для иллюстрации метода на рис.1 показан пример простой схемы с набором ограничений, необходимым для анализа помехи типа LowR в узле v, индуцируемой остальными пятью узлами схемы (LowR - помеха, при которой “узел-жертва” находится в логическом 0, в то время как ”узлы-агрессоры” переключаются из 0 в 1). Справа показана соответствующая часть характеристической ROBDD.

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

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

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

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

В пятой главе приведён анализ современных моделей быстродействия библиотечных ячеек с точки зрения решения новых проблем проектирования глубоко субмикронных и нанометровых цифровых СБИС, в том числе дан сравнительный анализ следующих моделей: нелинейной модели задержки 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. C 2005 года CCS-модель поддерживается подсистемой Synopsys PrimeTime. В настоящее время ECSM поддерживают инструменты Cadence Encounter, Cadence First Encouter, Cadence Celtic. Появились также первые средства характеризации новых моделей - Synopsys NanoChar, Cadence Signal Storm NDC, Magma SiliconSmart SI. Однако на сегодняшний день использование новых моделей в промышленном проектировании затруднено. Основная причина заключается в том, что новые модели имеют большую размерность по сравнению с NLDM, и как следствие требуют значительно больших ресурсов по времени счета и потребляемой памяти - как на этапе использования этих моделей, так и на этапе подготовки (характеризации). Другая проблема состоит в том, что практически единственной областью применения этих моделей остаётся статический временной анализ, и не существует алгоритмов для других типов анализа.

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

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

{ }, k [1: Ns], { }, l [1: Nc],

где значения Ns и Nc обычно находятся в интревале 10 - 20. В коммерческих системах характеризации (NanoChar, Cadence Signal Storm NDC, Magma SiliconSmart SI) такие зависимости строятся на основе многократного электрического моделирования (типа Spice). Особенно трудоемкой процедурой является процесс характеризации элементов памяти (ЭП), в частности триггеров. Дело не только в том, что схемы таких элементов, как правило, значительно сложней, чем схемы логических вентилей, но также в том, что для ЭП необходимо вычислять такие специфические параметры, как времена предустановки и удержания информационных сигналов - T_setup и T_hold, требующих до нескольких тысяч запусков электрического моделирования. При переходе на новые статистические модели (sECSM, SI2-ECSM) трудоемкость возрастает в десятки - сотни раз ввиду необходимости расчетов для различных вариаций технологических и схемных параметров.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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