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

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

Соловьев Роман Александрович у

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

О

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

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

Москва - 2007

ООЗ159599

003159599

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

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

доктор технических наук Глебов А Л

Официальные оппоненты доктор технических наук, профессор Курейчик В В

кандидат технических наук, профессор Ермак В В

Ведущее предприятие

Институт проблем информатики Российской академии наук

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

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

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

Ученый секретарь диссертационног совета Д 002 078 01,

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

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

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

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

С переходом технологического процесса на глубоко субмикронные размеры, эффекты, влияние которых ранее не учитывалось, начинают вносить дополнительные задержки в общую задержку проводящих путей Одним из таких электрических эффектов является перекрестная помеха, вызываемая одновременным переключением соседних узлов Эффект перекрестных помех имеет значительное влияние на временные характеристики цифровых схем Влияние перекрестных помех все больше увеличивается с уменьшением размеров транзистора и увеличением тактовой частоты Увеличение (или уменьшение) задержки пути под влиянием электрических эффектов называется помехой задержки Так, например, для схем построенных на технологии 0 25 микрон помеха задержки может составить до 20% и более процентов от общей задержки проводящего пути Следовательно, даже небольшая переоценка влияния помехи на задержку может привести к нарушению временных ограничений для схемы

Некоторые современные САПР от крупных вендоров (Synopsys, Cadence) уже принимают во внимание перекрестные помехи во временном анализе Однако они не содержат эффективных средств для решения ряда проблем, связанных с более точным учетом помех и сокращением пессимизма в расчете помехи задержки Новые проблемы проектирования требуют учета информации о логике работы схемы и временных окнах для более точного расчета задержки критических путей Это приводит к необходимости разработки новых алгоритмов и методов для решения этой задачи

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

Для достижения поставленной цели в диссертационной работе решаются следующие задачи

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

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

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

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

5 проверка предложенных методов с помощью численных экспериментов

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

1) Разработан оригинальный метод для определения возможного сокращения пессимизма в оценке помехи задержки, основанный на попарном переборе входных воздействий и анализе реакции схемы на каждый из них Этот метод позволяет оценить предел эффективности алгоритмов анализа помехи задержки

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

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

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

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

включает использование аппарата теории графов, дискретной математики,

оптимизации, временного анализа КМОП схем и теории языков программирования

Реализация.

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

Практическая значимость

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

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

Результаты диссертации докладывались и обсуждались на 12-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика - 2005», 7-й Всероссийской научно-технической конференции молодых ученых и студентов «Современные проблемы радиоэлектроники», Всероссийской научно-технической конференции «Проблемы разработки перспективных микроэлектронных систем - 2005», международной конференции по компьютерному проектированию интегральных схем "ICCAD" (США, 2004), Всероссийской научно-технической конференции «Проблемы разработки перспективных микроэлектронных систем - 2006»

Публикации

По теме диссертации автором опубликовано 8 работ

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

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

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

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

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

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

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

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

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

Современные программы анализа помехоустойчивости (Synopsys Prime Time SI, Cadence Encounter) используют временные корреляции между сигналами, существующими в схеме Способ их учета был предложен учеными из университета Карнеги Меллон и исследовательской лаборатории «Интел» В этом методе идентифицируются ситуации, когда два узла-агрессора переключаются в различных тактовых периодах или когда один агрессор переключается в ранней части, а другой в поздней части одного и того же тактового периода

Начало

—► Расчет помехи задержки

Временные Изменения

окна задержек

Статический временной л—

анализ

1

Конец

Рис. 1. Схема временного анализа с учетом помехи задержки

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

Р Chen и К Keutzer показали, что в общем виде проблема сокращения пессимизма в оценке помехи задержки может быть представлена, как проблема

поиска наихудшей пары входных векторов, что может быть сформулировано, как оптимизационная задача с булевыми ограничениями Kirkpatrick и Sangiovanm-Vmcentelh для аналогичной цели предложили метод, основанный на CODC (compatible observation don't care set), те совместимого множества сигналов схемы, ошибка в значениях которых не влияет на значения выходов схемы Rubio и Itazaki предложили метод, основанный на подходе, традиционно используемом в задаче автоматической генерации тестов Однако все три указанных метода, несмотря на точность полученного решения, имеют очень высокую вычислительную сложность и не могут быть применены к задачам высокой размерности (тек реальным цифровым схемам)

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

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

Алгоритм состоит из следующих этапов

1) Чтение структурного описания схемы в формате Spice или Verilog

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

3) Чтение описания пути (набор узлов и их переключений) и набора кластеров для всех узлов, входящих в заданный путь

4) Поиск максимальной задержки, вносимой каждым из кластеров

5) Суммируются значения задержек для каждого из кластеров помехи, и находится помеха задержки на всем проводящем пути

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

Целью предварительных экспериментов являлась оценка возможного уменьшения пессимизма при вычислении помех, влияющих на задержку, посредством метода, основанного на рассмотрении путей Эксперименты проводились для схем с малым количеством входов (с 17, ent ones, cnf_zeros) Для таких схем мы можем перебрать все возможные входные переключения и вычислить максимальную задержку, как для каждого узла выбранного пути, так и для пути в целом Этот метод определения максимальной действительной помехи с помощью полного перебора всех возможных переключений входов схемы состоит из, следующих действий

1) Считываем в память программы spice-опиеание схемы и производим экстракцию логики, с целью нахождения набора логических вентилей, либо используем готовый Verilog-нетлист, состоящий из логических вентилей

2) Для всех возможных входных воздействий (для п входов получится 2" возможных значений) находим логическое значение проводящего сигнала на каждом из узлов схемы и сохраняем его в памяти

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

4) Для всех агрессоров, каждого из кластеров, мы отслеживаем направление их переключения и, если агрессор переключается в направлении противоположном направлению переключения жертвы, то мы добавляем его в «список воздействий»

5) Когда этот «список воздействий» готов для всего пути в целом, мы складываем значения всех агрессоров из этого списка и получаем «вес пути для данного переключения входов»

6) Если «вес пути для данного переключения входов» больше чем «максимальный найденный вес», то мы присваиваем «максимальному найденному весу» значение «веса пути для данного переключения входов»

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

Таблица 1

Результаты анализа помехи задержки различными методами

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

Вес пути с учетом всех агрессоров 2218 1640 802

% помеха 100 73 94 36 16

В таблице 1 приведены результаты анализа помехи задержки разными методами для одного из путей в схеме ent ones Из таблицы видно, что реальная помеха задержки составляет около 36% от полученной из консервативного анализа, т е эффективные методы для оценки помехи задержки могут значительно снизить пессимизм в расчетах времени прибытия сигнала в статическом временном анализе

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

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

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

В настоящее время, при современном уровне развития технологии, алгоритм статического временного анализа значительно усложнился В расчетах учитываются также некоторые аналоговые эффекты, которыми раньше пренебрегали в силу их малого влияния Задержки каждого вентиля не заданы изначально, а они зависят от времени переключения входного сигнала (Slew), емкости нагрузки (Cload), температуры (Temp), напряжения питания (VDD), длинны затвора транзистора (Leff) и других величин На практике, как правило, ограничиваются зависимостью от двух параметров от Slew и от Cload (рис 2) Обычно эти зависимости задаются с помощью таблицы или полинома

Slew Cload

Рис. 2. Зависимость задержки вентиля от времени переключения входного сигнала и емкости нагрузки

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

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

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

Во время формирования временного графа для заданной схемы, мы разделяем узел схемы N на два узла N_rise и N_fall (один для переключения из состояния 0 в 1 -rise и один для переключения из состояния 1 в состояние 0 - fall)

Определение 1 Пусть М - узел временного графа Conj(M) - это узел временного графа (узел сопряженный (conjugated) с М), который получается из того же узла схемы N, и составляет с М пару (N_rise, N_fall)

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

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

Определение 2 Пусть М1 и М2 - узлы временного графа Мы говорим, чт существует поздняя логическая импликация (пПЛИ) М1 -> М2, если существуе следующая ПЛИ между соответствующими узлами схемы N1 и N2' (ТЧ1=у1п) >(Ш=у2п), где VI п и у2п поздние логические значения узлов М1 и М соответственно

т

Рис. 3. Полный путь Р во временном графе и узлы, используемые для определения ложности пути

Пусть LI, , Ln это узлы, лежащие на некотором полном пути (пути от PIN до POUT) Р во временном графе для некоторой схемы Пусть М и N некоторые два узла на этом пути Сформулируем условия, при которых путь является ложным из-за наличия ПЛИ между N, М и некоторым другим узлом S (см рис 2)

Проводящий путь Р состоит из 3 подпутей PP¡N<N,PN м'^м.роиг Len(p) = Len( Ррт N) + Len(PNм ) + Len(Рм pQm), где Len(P) длина пути Р Пусть выполняется следующий набор условий

1) Существует ребро (S, М) не лежащее на пути Р, т е S - это вход сбоку на путь Р

2) Существует пПЛИ S -> М

3) Существует пПЛИ N -> S

4) Len( Ррт м ) > LAT(S) + D$M где Ds м - это задержка ребра временного графа (S, М)

В этом случае сигнал (переключение) идущий по пути Р не может быть на узле М позже, чем t = LAT(S) + DSM С другой стороны, время прибытия сигнала к узлу М идущему по пути Р точно равно Len( РРт м ) Таким образом, Р является ложным путем (сигнал идущий по этому пути никогда не дойдет до POUT)

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

Модифицированная версия алгоритма для поиска К самых длинных путей, содержит вызов двух дополнительных функций checkpath_falsity() - вызывается, перед тем как добавить путь в список длиннейших путей Если путь ложный, то он не добавляется в список максимальных путей check_search_continue() - вызывается для определения продолжать ли поиск путей в глубину дальше или оборвать обход на некотором узле N

Предложенные методы были реализованы во внутреннем программном обеспечении для статического временного анализа В таблице 2 представлены сравнительные результаты алгоритмов нахождения К максимальных путей классическим методом и с учетом логических импликаций Для тестирования использовались схемы из набора ISCAS85 (International Symposium on Circuits and Systems) и некоторые другие типовые схемы Для каждой из схем было получено 1000 самых длинных путей с помощью обычного статического анализа и 1000 самых длинных путей для статического анализа с учетом логических импликаций

Таблица 2

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

Названи Задержка Задержка Процент Число Процент

е максимальн максималь сокраще верхних сокращения

схемы ого ного ния ложных задержки для

критическо критическ задержк критичес тысячного

го пути без ого пути с и (%) ких критического

учета ПЛИ (не) учетом ПЛИ (не) путей пути(%)

С17 0 17 0 17 0 00 0 -

С432 2 05 0 89 56 68 > 1000 64 79

С499 1 04 0 95 8 78 > 1000 22 46

С1355 1 76 1 75 0 55 > 1000 3 66

С1908 1 91 1 91 0 00 0 -

С2670 1 85 1 40 24 45 > 1000 31 29

С3540 2 36 2 32 1 60 -500 -

С5315 2 49 2 47 0 88 -50 -

сп1:_0 1 24 1 24 ООО 0 -

СШ 1 1 29 1 29 0 00 0 -

сп^опеБ 1 32 1 31 0 65 1 -

ст гегоэ 1 20 1 20 0 00 0 -

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

Четвертая глава

анализа с учетом ограничений

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

На рисунке 4 представлен кластер и форма сигнала с дополнительной задержкой, индуцированной помехой Как уже отмечалось, помеху на «узел-жертву» наводят сразу несколько «узлов-агрессоров» В анализе помех принято использовать линейную модель для «агрессоров» и «жертв», вычисляя индуцированную помеху на основе принципа суперпозиции

1 грессор_1

Агрессору

ЛГ

Узеч-жертва

- ^Г

(А)

(Б)

Рис. 4. Воздействие помехи на задержку (А) Кластер (Б) Переключение на драйвере и ресивере узла-жертвы

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

может быть аппроксимирована линейным выражением д£>_ ® * д^ * д^ +

ок, " дн>„

(. умкирпый uu/п 7 «с палнхи

HimvtbL лш/етм I llumt7ьс nauexit 2

Переключение жираты nix) turjiKiiunuiu и rJtfVA tlfpetLVfMMf

Пе/Кк-иочапи. жираты iuk) nt'3t)eiiininue.4 vhiocn ii pevatpu

Рис 5. Форма совместного воздействия агрессоров на узел-жертву

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

Определим максимальный реализуемый набор «узлов-агрессоров» (МРНА) как совокупность «узлов-агрессоров» СБИС, которые могут переключиться одновременно и при этом не противоречат найденным логическим и временным корреляциям межу этими «узлами-агрессорами»

При распространении сигнала по пути Р, каждый узел V, в нем

рассматривается как «узел-жертва» с переключением из начального состояния х' в

конечное состояние Различают rise-переключение (0—> 1) и fall-переключение

(1-Я)) Путь сигнала Р представим как набор узлов и их переключений В этом случае МРНА представим как набор «узлов-агрессоров», которые могут переключиться одновременно, не нарушая логических состояний схемы, индуцирующих помеху в каждом «узле-жертве» пути Р и приводящих к максимальной задержке распространения сигнала

Для уточнения результатов статического временного анализа необходимо получить данные о временных и логических ограничениях в схеме Логические ограничения можно получить, используя эвристический алгоритм, основанный на применении метода резолюций Временные ограничения для анализа помехоустойчивости получают из результатов статического временного анализа Для каждого узла схемы с помощью СВА находят значение раннего времени прибытия сигнала (Earliest Arrival Time) и позднего времени прибытия сигнала (Latest Arrival Time) Эти два полученных значения определяют интервал, или временное окно, в котором может переключаться данный узел проводящего пути Очевидно, что если временные окна узла-жертвы и узла-агрессора не имеют пересечений, то агрессор не может воздействовать на жертву в силу своего стабильного состояния Аналогично

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

Положим, что каждый «узел-жертва» V, переключается из х\ в х[, а каждый «агрессор» а, ] переключается из у'] в у^ Пусть векторы начального и конечного

состояния узлов «жертв» X' и X' , а «агрессоров» У' и УР Из набора логических ограничений С, можно получить наборы С' и СР, подставляя начальные и конечные значения показателей «узлов-жертв» в С Тогда задача расчета ДЦшх может быть сформулирована как задача оптимизации ЛГ)|мл = шах ^АО, При современных размерах СБИС и достаточно большой

а,

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

Граф парных ограничений - это тройка О = (V, Е, м), где V - набор вершин, Е

- набор ребер и И7 - весовая функция вершин, такая

что м>{и) > 0, Ми е V и м>(К) = > где у

не а:

Для каждого анализируемого пути в схеме, строится свой граф парных ограничений (рис 6) Для формирования графа парных ограничений используются только ПЛИ В этом графе набору вершин соответствует набор «агрессоров» Аг

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

«узлом-агрессором» Помеха задержки вычисляется как максимальная разница между задержкой вентиля под влиянием агрессора и без его влияния Ребро

г- (а,, а;)<гЕ соответствует ПЛИ а" а ^, которая ограничивает «агрессоры» а, и а / от совместного влияния на проводящий путь, где а и /? - логическое состояние Задача нахождения независимого множества максимального веса (НММВ) для графа С? = (V, Е, М>) - ИР-полная, но в теории графов существуют эффективные методы ее решения при некоторых ограничивающих условиях

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

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

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

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

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

1) Агрессоры переключаются в одном направлении и имеют запрет на состояние 11

2) Переключаются в одном направлении и имеют запрет на состояние 00

3) Переключаются в разных направлениях и имеют запрет на состояние 10

4) Переключаются в разных направлениях и имеют запрет на состояние 01

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

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

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

исключаем а! включаем а1

иск тачаем а2 исключаем а2 вкуочаем а2

вк ночаем а2 ч

Рис. 7. Дерево решения для алгоритма ветвей и границ

Стратегию формирования ограничений для метода «ветвей и границ» позволяют

реализовать следующие свойства

Л) если набор А1 может индуцировать помеху задержки м>(Аг) и удовлетворяет логическим ограничениям С, то МРНА Ак будет индуцировать помеху задержки м>(Ак) равную ю(Аг) или большую м/(Аг)<м>(Ак),

2) пусть набор агрессоров Аг разделен на два не пересекающихся подмножества А1 и А2, так что реализуемые наборы А = А<[^А2 , Ап с /4,, А, с А, если выполняется неравенство -н>(Аг) > -и>(Аг]) + м(А2) (9), то МРНА А1{ не является подмножеством аг1[]а2 (АЯ(Х:А^[]А2)

3) С учетом этих свойств реализуется алгоритм метода ветвей и границ для (А ,1 ,АЬ,АК), входными данными которого является полный набор «узлов-агрессоров» А = {а,,а2, }, порядковый номер обрабатываемого агрессора,

текущие выбранные агрессоры As = {aS],aS2, } и текущий МРНА Л={«г1»аг2» }

Реализация рекурсивного алгоритма Branch_and_Bound представлена ниже

1 UNPROCESSED = {al+l,al+2, ,ап} и не равно пустому подмножеству, если добавление а1+1 к As не противоречит логическим ограничениям и w(As) + w(UNPROCESSED) > w(Ar), то A's = AS{J{al+,} Если w(A's)> w(Ar), то следует улучшить текущий МРНА Ar = A's Улучшение текущего МРНА Аг Ar - Branch _ and _ Bound(A, г +1, As, А,)

2 UNPROCESSED = {ai+2,ai+3, ,an} и не равно пустому подмножеству, то если w(As) + w(JJNPROCESSED) > w(Ar), то надо улучшить текущий МРНА А/ = Branch _ and _ Bound (A, i + 2,As,Al)

3 Возвращается Ar

Метод ветвей и границ позволяет достаточно точно определять МРНА, но для «наихудшего случая» время, на его выполнение, возрастает по экспоненте

Предлагается эвристическая модификация метода ветвей и границ таким образом, чтобы он постоянно улучшал приближение МРНА Тогда алгоритм использует вычисление верхней границы возможной помехи w(As) + w(UNPROCESSE D) > w(Ar) шаге

Во время выполнения алгоритм постоянно обновляет верхнюю границу для заданного набора «узлов-агрессоров» При остановке поиска алгоритм выдаст на выходе лучшее приближение для МРНА Полезным критерием остановки поиска является достижение полученной величиной помехи такого значения, когда полная задержка сигнала на выбранном пути меньше, чем требуемая Другой полезный критерий - это максимальная ошибка полученной аппроксимации е - w(As) + w(UNPROCESSED) - w(A,)

Еще один эвристический алгоритм может быть получен с помощью подхода для МРНА, позволяющего исключать любые логические ограничения То есть, можно исключить часть логических ограничений так, чтобы разделить полный набор агрессоров А на несколько непересекающихся подмножеств Ак, причем любые

логические ограничения включают в себя «узлы-агрессоры» только одного подмножества Так задача может быть разбита на независимые части

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

На основе предложенных алгоритмов для этапа временного анализа после экстракции из топологии разработано программное обеспечение Delay Noise Потоки данных в программе приведены на рисунке 8

Описание первичных входов и выходов схемы

Описание схемы в формате spice или в формате venlog

Описание времен Описание

активности кластеров

агрессоров и для всей

времени схемы

чувствительност

и жертвы

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

Описание Описание Тип анализа (с помощью

критических путей логических графа парных

ограничении ограничении, метод ветвей

в схеме и границ)

т

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

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

Рис. 8. Потоки данных в Delay Noise

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

Таблица 3

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

Схема Число транзи сторов в схеме Оставшаяся помеха в процентах от первоначальной (%)

Раздельны й анализ кластеров Эвристиче ский анализ Анализ с помощью НММВ Метод ветвей и границ

С499 1572 88 61 76 07 75 65 74 97

С1355 2260 87 91 78 90 75 65 75 48

С1908 3322 91 24 87 10 85 72 85 39

С2670 4990 88 65 86 45 85 65 85 44

спМ 350 68 83 35 59 33 29 27 98

спЫ) 340 70 28 44 67 40 42 33 46

сп1 опеэ 372 63 08 36 05 32 47 26 51

сп^гегоэ 352 69 23 43 40 37 75 33 78

с1а 1008 94 06 88 10 84 05 83 03

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ:

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

2) Проведена оценка максимально возможного сокращения пессимизма в анализе помехи задержки на небольших комбинационных ИС Показано, что анализ помехи задержки, сразу для всего проводящего пути, может значительно сократить численное значение помехи задержки, по сравнению с консервативным и покластерным методами (более чем на 60% и 30% соответственно),

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

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

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

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

7) По теме диссертации опубликовано 8 печатных работ, в том числе 2 работы опубликованы в журнале, рекомендованном ВАК Сделано 4 доклада на Всероссийских и международных конференциях,

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

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

следующих работах

1 Glebov А, GavrilovS, Solovyev R, Becer M, ZolotovV, Oh С, Panda R Delay Noise Pessimism Reduction by Logic Correlations // In Proc oflCCAD, 2004 -P 160167

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

3 Соловьев РА, Глебов АЛ Помехи, влияющие на задержку, и их анализ в цифровых СБИС с помощью логических ограничений // Современные проблемы радиоэлектроники сб науч тр -М Красноярск ИПЦКГТУ -2005. - С. 489-492

4 Соловьев РА Помеха задержки в СБИС и методы ее анализа на примере алгоритма ветвей и границ // 12-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика-2005» тезисы докладов -М МИЭТ, 2005 -С 114

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

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

7 Глебов А Л, Гаврилов С В , Лялинская О В , Соловьев Р А Использование результатов характеризации реальных библиотек логических вентилей в статистическом временном анализе // II Всероссийская научно-техническая конференция «Проблемы разработки перспективных микроэлектронных систем 2(1(16» сб научн тр / под общ ред А Л Стемпковского" - М ИППМ РАН, 2006 -С 29-36

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

Содержание.

Введение.

Глава 1. Анализ помехоустойчивости цифровых КМОП схем. Обзор состояния проблемы.

1.1. Консервативный анализ помехоустойчивости.

1.2. Современные методы анализа помехоустойчивости.

1.3. Выводы.

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

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

2.2. Алгоритм покластерного анализа помехи задержки на проводящем пути

2.3. Алгоритм покластерного анализа помехи задержки на проводящем пути с учетом межкластерных взаимодействий.

2.4. Экспериментальные результаты.

2.5. Выводы.

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

3.1. Статический временной анализ.

3.2. Современный статический временной анализ.

3.3. Расчет задержки и времени переключения для предварительно отхарактеризованного вентиля.

3.3.1. Нелинейная модель задержки.

3.3.2. Полиномиальная модель задержки.

3.4. Учет задержки вносимой межсоединениями в статическом временном анализе.

3.4.1. Задержка и время переключения сигнала для RC-деревьев.

3.4.2. Алгоритм, основанный на расчете эффективной емкости (Ceff) RC-дерева.

3.4.3. Экспериментальные результаты расчета RC-деревьев в статическом анализе.

3.5. Алгоритмы перечисления путей.

3.6. Формирование логических ограничений.

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

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

3.9. Реализация и экспериментальные результаты.

3.10. Выводы.

Глава 4. Анализ помех влияющих на задержку с помощью графа парных ограничений.

4.1. Модель помехи задержки.

4.2. Логические ограничения.

4.3. Временные ограничения.

4.4. Расчет влияния помехи на время задержки распространения сигнала в цифровых СБИС «на наихудший случай».

4.5. Формирование графа парных ограничений.

4.6. Поиск независимого множества максимального веса на графе парных ограничений.

4.7. Реализация и экспериментальные результаты.

4.8. Выводы.

Глава 5. Анализ помех влияющих на задержку с помощью метода ветвей и границ.

5.1. Расчет влияния помехи на время задержки распространения сигнала в цифровых СБИС «на наихудший случай».

5.2. Реализация и экспериментальные результаты.

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

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

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

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

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

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

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

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

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

• Оценка максимального возможного сокращения пессимизма в анализе помехи задержки на небольших комбинационных ИС.

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

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

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

• Разработка и исследование метода анализа помехи задержки в СБИС с помощью алгоритма ветвей и границ.

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

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

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

1) Разработан оригинальный метод для определения возможного сокращения пессимизма в оценке помехи задержки, основанный на попарном переборе входных воздействий и анализе реакции схемы на каждый из них. Этот метод позволяет оценить предел эффективности алгоритмов анализа помехи задержки.

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

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

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

Защищаемые в работе положения:

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

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

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

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

Апробация работы. Результаты диссертации докладывались и обсуждались на 12-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика -2005», 7-й Всероссийской научно-технической конференции молодых ученых и студентов «Современные проблемы радиоэлектроники», Всероссийской научно-технической конференции «Проблемы разработки перспективных микроэлектронных систем - 2005», международной конференции по компьютерному проектированию интегральных схем "ICCAD" (США, 2004), Всероссийской научно-технической конференции «Проблемы разработки перспективных микроэлектронных систем - 2006».

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

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

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

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

2. Проведена оценка максимально возможного сокращения пессимизма в анализе помехи задержки на небольших комбинационных ИС. Показано, что анализ помехи задержки, сразу для всего проводящего пути, может значительно сократить численное значение помехи задержки, по сравнению с консервативным и покластерньш методами (более чем на 60% и 30% соответственно);

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

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

5. Разработан метод анализа помехи задержки в СБИС на основе алгоритма ветвей и границ. Метод позволяет работать с логическими ограничениями любой размерности. С его помощью можно добиться сокращения численной оценки помехи задержки до 60-ти и более процентов по сравнению с консервативным методом анализа. Метод эффективно работает при размерности задачи до 150 агрессоров;

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

7. По теме диссертации опубликовано 8 печатных работ, в том числе 2 работы опубликованы в журнале, рекомендованном ВАК. Сделано 4 доклада на Всероссийских и международных конференциях;

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

Заключение

1. R.Levy, D.Blaauw, G.Braca, et.al. "ClariNet: A noise analysis tool for deep sub-micron design", DAC-2000, pp.233-238.

2. P.Chen, K.Keutzer. "Towards True Crosstalk Noise Analysis", ICCAD-99, pp. 132-137.

3. Noise-Aware Timing Analysis (Cadence), White Paper.

4. D.A.Kirkpatrick, A.L.Sangiovanni-Vincentelli. "Digital Sensitivity: Predicting Signal Interaction using Functional Analysis", ICCAD-96, pp.536-541.

5. W.Kunz, P.R.Menon. "Multi-Level Logic Optimization by Implication Analysis", ICCAD-94, pp.6-13.

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

7. K.L.Shepard "Design methodologies for noise in digital integrated circuits", Proc., DAC, 1998, pp. 94-99.

8. A.Rubio, N.Itazaki, X.Xu and K.Kinoshita, "An Approach to the Analysis and Detection of Crosstalk Faults in Digital VLSI Circuits", IEEE Trans, on CAD, Vol.13, No.3,1997.

9. A.Glebov, S.Gavrilov, D.Blaauw, S.Sirichotiyakul, C.Oh, V.Zolotov. "False-Noise Analysis using Logic Implications", ICCAD-2001, pp.515-520.

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

11. A.Glebov, S.Gavrilov, D.Blaauw, V.Zolotov. "False-noise analysis using logic implications", ACM Trans, on Design Automation of Electronic Systems (TODAES),2002, v.7, '3, pp.474-498.

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

13. K.L. Shepaid et al. "Global Harmony: Coupled noise analysis for full-chi] interconnect networks," Proc. IEEE Int'l Conf. Computer-Aided Design, IEEI Press, 1997, pp. 139-146

14. K.L. Shepard and V. Narayanan. Noise in deep submicron digital Desigr Proceedings of the IEEE/ACM International Conference on Computer-Aided Des pages 524-531, San Jose, С A, November 1996.

15. A.Glebov, S.Gavrilov, D.Blaauw, V.Zolotov, R.Panda, C.Oh. «False nc analysis using resolution method».- 1SQED 2002, p. 437-442.

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

17. T.Amon, G.Borriello. «An approach to symbolic timing verification».- Proc АСМЛЕЕЕ Design Automation Conference (DAC), 1992, p.410-412.

18. B.Gladstone. «Accurate timing analysis holds the key to performance in today': system designs».- EDA 1993.

19. D.Overhauser. «Fast timing simulation of MOS VLSI circuits».- Ph.D. thesis, University of Illinois at Urbana-Champaign, 1989.

20. A.Dharchoudhury, S.M.Kang, K.H.Kim, S.H.Lee. «Fast and accurate timing simulation with regionwise quadratic models of MOS I-V characteristics».- Proc. IEEE/ACM ICCAD-1994, p.190-194.

21. R.B.Hitchcock. «Timing verification and the Timing analysis Program».- Proc., ACM/IEEE Design Automation Conference (DAC), 1982, p.594-604.

22. R.Reddi, C.Chen. «Hierarchical Timing Verification System».- Computer Aided Design, Vol. 18, 9, November, p.467-477.

23. S.Yen, D.Du, S.Ghanta. «Efficient Algorithms for Extracting the К Most Critical paths in Timing Analysis».- Proc., АСМЛЕЕЕ Design Automation Conference (DAC), 1989, p.649-654.

24. T.Sasaki, A.Yamada, T.Aoyama, K.Hasegava, S.Kato, S.Satoa. «Hierarch Design Verification for Large Digital Systems».- Proc., ACM/IEEE Des Automation Conference (DAC), 1981, p. 105-112.

25. J.A. Robinson. «А Machine-Oriented Logic Based on the Resolution Principl J. of the ACM, 12(1): p. 23-41,1965.26. http://www.s\nopsvs.com/products/libertvccs/libertvccs.html

26. Synopsys Online Documentation. Library Compiler: Modeling Timing ai Power. Delay Models. Page 19-29

27. Synopsys Online Documentation. Library Compiler: Modeling Timing an Power. Delay Models. Page 31-36

28. Gentle, J. E. "Gaussian Elimination." §3.1 in Numerical Linear Algebra fo< Applications in Statistics. Berlin: Springer-Verlag, pp. 87-91,1998.

29. Morse, P. M. and Feshbach, H. "Derivatives of Analytic Functions, Taylor and Laurent Series." §4.3 in Methods of Theoretical Physics. Part I. New York: McGraw-Hill, pp. 374-398,1953.

30. Wen-mei Hwu, John W. Sias, Erik M. Nystrom and others. "Breaking the Memory Wall for Scalable Microprocessor Platforms", University of Illinois at Urbana-Champaign, 2004.

31. C.J.Alpert, F.Liu, C.V.Kashyap, A.Devgan. "Closed-form delay and slew metrics made easy", IEEE Trans, on CAD, 2004, v.23, p. 1661

32. W.C. Elmore. The Transient Analysis of Damped Linear Networks with Particular Regard to Wideband Amplifiers. J. Applied Physics, vol. 19(1), 1948.

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

34. C.J.Alpert, A.Devgan, C.V.Kashyap. "RC delay metrics for performance optimization", IEEE Trans, on CAD, 2001, v.20, p.571

35. P.R.O'Brien, T.L.Savarino. "Modeling the driving-point characteristic of resistive interconnect for accurate delay estimation", ICCAD-89, p.512.

36. A.Rubio, N.Itazaki, X.Xu and K.Kinoshita. «An Approach to the Analysis and Detection of Crosstalk Faults in Digital VLSI Circuits».- IEEE Trans. On CAD, Vol.13 No.3, 1997.

37. F.M. Brown. «Boolean reasoning».- Kluwer Academic Publishers, 1990.

38. E.Loukakis, C.Tsouros. «An Algorithm for the Maximum Internally Stable Set in a Weighted Graph», Intern. J. Computer Math., 1983, v.13, p.l 17-129.

39. N.A. Sherwani. «Algorithms for VLSI Physical Design Automation».- Klauwer Academic Publisher, 3rd edition, June 1999.

40. Du, D.H.C. Yen, S.H.C. Ghanta, S. «On the General False Path Problem in Timing Analysis».- Department of Computer Science, University of Minnesota, Minneapolis, MN, June 1989.

41. Andrew B. Kahng, Sudhakar Muddu, «Efficient Gate Delay Modeling for Large Interconnect Loads».- IEEE Multi-Chip Module Conference (MCMC '96), 1996, p. 202.

42. S. Malik, M. Martonosi, Y.T.S. Li, «Static Timing Analysis of Embedded Software».- Proceedings of the 34th annual conference on Design automation, 1997, pp. 147-152

43. Ravishankar Arunachalam, Karthik Rajagopall and Lawrence T. Pileggi, «ТАСО: Timing Analysis With Coupling».- Design Automation Conference, 2000, pp. 266-269.

44. Paul D. Gross, Ravishankar Arunachalam, Karthik Rajagopal and Lawrence T. Pileggi, «Determination of Worst-Case Aggressor Alignment for Delay Calculation».-ICCAD 98, 1998, pp. 212-219.

45. Florentin Dartu and Lawrence T. Pileggi, "Calculating Worst-Case Gate Delays Due to Dominant Capacitance Coupling," Proceedings of the 34th ACM/IEEE Design Automation Conference, June 1997.

46. G. Yee, R. Chandra, V. Ganesan and C. Sechen, "Wire Delay in the Presence of Crosstalk," Proceedings of TAU 97, the IEEE meeting on Timing Issues in Digital Systems, December 1997.

47. M.M. Halldorsson, «Approximations of Weighted Independent Setand Hereditary Subset Problems».- Journal of Graph Algorithms and Applications, 2000.

48. P.M. Pardalos, N. Desai, «An algorithm for finding a maximum weighted independent set in an arbitrary graph».- International Journal of Computer Mathematics, 1991.

49. E. L. Lawler, D. E. Wood, «Branch-And-Bound Methods: A Survey».-Operations Research, Vol. 14, No. 4 (Jul. Aug., 1966), pp. 699-719.

50. L. G. Mitten, «Branch-And-Bound Methods: General Formulation and Properties».- Operations Research, Vol. 18, No. 1 (Jan. Feb., 1970), pp. 24-34

51. M. Harrison, M. McLennan, «Effective Tcl/Tk programming: writing better programs with Tel and Tk».- Addison Wesley Longman Publishing Co., Inc. Redwood City, CA, 1998.

52. G.D. Lahti, S.J. Brown, «Tel: The Good, The Bad, and The Ugly».- SNUG, Boston, 2000.

53. У Т В Е Р Ж Д А Ю" Ген. Директор ОАО «Ангстрем-М»1. Машевич П.Р.1. О Я 2007 г.

54. АКТ ВНЕДРЕНИЯ Результатов диссертационной работы Соловьева Р.А. на соискание ученой степени кандидата технических наук. Тема диссертации: «Методы анализа помех, влияющих на быстродействиецифровых КМОП схем»

55. Настоящим актом удостоверяется, что на предприятии ОАО «Ангстрем-М» были внедрены научные и практические результаты диссертационной работы Соловьева Р.А.

56. На основе предложенных в диссертационной работе методов автором разработаны программы "Advanced Timing" и "Delay Noise" для статического временного анализа с учетом помехи задержки, влияющей на распространение сигнала.

57. Эффективность предложенных в диссертационной работе алгоритмов и методов подтверждена практическим опытом проектирования реальных микросхем.

58. Главный специалист А.Г1. Подобаев

59. УТВЕРЖДАЮ" Генеральный Директор1. Акт внедрениярезультатов диссертационной работы Соловьева Р.А. на соискание ученой степени кандидата технических наук по теме: " Методы анализа помех, влияющих на быстродействие цифровых1. КМОП схем"

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

61. Заведующий кафедрой «Проектирование и конструирование ИМС» к.т.н., доцент1Щщ г д и. Сухопаров