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

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

Глебов Алексей Львович

4л

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

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

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

Москва - 2003

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

Научный консультант: доктор технических наук, профессор Русаков С.Г.

Официальные оппоненты: доктор технических наук, профессор Горнсв Е.С.

доктор технических наук, профессор Корячко В.П. доктор технических наук, профессор Шагурин И.И.

Зашита состоится 18 декабря 2003г. в 10 час. 00 мин. на заседании диссертационного совета Д 002.078.01 в Институте проблем проектирования в микроэлектронике Российской академии наук (ИППМ РАН) по адресу: 124681, г.Москва, ул. Советская, д.З.

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

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

Ведущая организация

Институт точной механики и вычислительной техники имени С.А. Лебедева (ИТМиВТ им. С.А. Лебедева)

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

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

a^og- А

2о212

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

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

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

- постоянное снижение размеров элементов (транзисторов, межсоединений), а также рост числа элементов на кристалле;

- необходимость проектирования схем с низкой потребляемой мощностью;

- возрастающее разнообразие стилей проектирования, которые используются или могут быть использованы при разработке СБИС.

Для удовлетворения указанных потребностей необходимо создать новое поколение методов анализа и оптимизации цифровых КМОП схем, включая анализ мощности и помехоустойчивости, обладающих значительно более высокими производительностью и качеством результатов по сравнению с существовавшими ранее. Для создания таких методов необходима новая математическая модель цифровых КМОП схем. Базой этой модели ррр ^'"""^^ Y"'"" diagrams,

или диаграммы двоичных решений), ра^^^^^Що^дользофавшиеся для

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

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

Основные задачи работы:

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

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

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

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

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

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

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

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

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

• Предложена оригинальная теоретико-графовая модель цифровых КМОП схем, основанная на впервые введенных ВОЭ (диаграммах двоичных решений) специального вида (БР-ВОЭ). Разработана теория БР-ЕШО, включающая набор базовых методов и алгоритмов работы с этими объектами. Данная Модель позволяет эффективно производить вычислительные операции для КМОП вентилей в рамках различных алгоритмов.

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

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

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

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

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

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

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

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

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

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

• Новый метод структурной оптимизации (ресинтеза) цифровых КМОП схем, основанный на использовании БР-ВОЭ модели. В данном методе на каждом шаге оптимизационной процедуры используется как детальное описание схемы на транзисторном уровне, так и описание ее логической функции. Метод позволяет значительно улучшить параметры схемы, предварительно синтезированной и оптимизированной лучшими из известных программ логического синтеза.

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

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

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

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались и обсуждались на 4-м международном семинаре по автоматизации проектирования "Russian Workshop" (Москва, 1994), 4-м международном семинаре по проектированию низкомощных и быстродействующих интегральных схем "PATMOS" (Испания, 1994), Международном симпозиуме по проектированию низкомощных интегральных схем "ISLPD" (США, 1995), 2-й международной конференции "Микроэлектроника и

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

Публикации. По теме диссертации опубликованы 24 печатные работы, в том числе одна монография.

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

Содержание работы

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

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

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

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

числа элементов и рассеиваемой мощности на одном кристалле - с другой стороны.

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

следующим образом. Требуется минимизировать мощность, потребляемую схемой:

min min Р szS W

где S - множество возможных структурных реализаций схемы, W=(W|.....Wn) -

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

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

• Как описать пространство возможных структурных реализаций схемы и двигаться по этому пространству ?

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

v

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

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

• используемые упрощенные модели задержек и мощности, как правило, нереалистичны, т.е. имеют недостаточную точность (это особенно недопустимо для моделей задержки);

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

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

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

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

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

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

Успехи в развитии технологии СБИС привели к значительному уменьшению размеров элементов и, как" следствие, к сильному росту емкостей связи межсоединений. Становится обычным, что 60-80% от полной емкости межсоединения составляют емкости связи с другими межсоединениями. Эта тенденция приводит к увеличению помех, индуцированных в цепи из-за нежелательных переключений соседних цепей, что приводит к необходимости разработки алгоритмов и программ анализа помехоустойчивости. Алгоритмы и программы анализа помехоустойчивости обычно предполагают, что все узлы-агрессоры в кластере переключаются одновременно и в одном направлении. На практике, однако, временные и логические ограничения, имеющиеся в схеме, могут накладывать запрет на одновременное переключение всех агрессоров в одном направлении. В этой ситуации величина помехи, получаемая при консервативном подходе, будет крайне велика, тогда как в действительности одновременное переключение агрессоров невозможно ввиду присущих схеме временных и логических корреляций.

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

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

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

• использование единой модели ПП-цепи вместо моделей отдельных транзисторов при ключевом моделировании;

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

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

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

В диссертации предложено представление для ПП-цспи (как для ее булевской функции, так и для се электрической схемы), основанное на использовании диаграмм двоичных решений (BDD = binary decision diagram) специального вида. Это представление названо SP-BDD (series-parallel BDD). Данное представление позволяет эффективно производить вычисления для ПП-цспей в рамках различных алгоритмов. Определим ПП-цепь как один из следующих объектов:

- ключ;

- последовательное соединение двух ПП-цспей;

- параллельное соединение двух ПП-цепей.

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

А. исток

В.

выход

и

Д-, х

I

Y

С.

и

_Ц X

Рис.1. Рекурсивное определение ПП-цспи (А - ключ, В - последовательное соединение двух ПП-цепей, С - параллельное соединение двух ПП-цепей).

Частичный порядок, ассоциированный с ПП-цепью - это бинарное отношение "<" на множестве ключей ПП-цепи, определяемое следующим образом. Пусть а,Ь -ключи ПП-цепн. Тогда а<Ь ("а предшествует Ь") если существует несамопересскающийся путь от истока к выходу ПП-цепи, содержащий а и Ь, причем а предшествует b на этом пути. Нетрудно показать,что:

- отношение "<•'действительно является отношением частичного порядка;

- ПП-цепь полностью задана если и только если заданы список се ключей и ассоциированный с ней частичный порядок.

Линейный порядок, ассоциированный с ПП-цепью - это бинарное отношение "«" на множестве ключей ПП-цспи, которое удовлетворяет следующим условиям:

• Если а«Ь то а<Ь (т.е. линейный порядок содержит частичный порядок).

• Если ПП-цепь содержит ПП-цепи X и Усоединеиныс параллельно, то

либо а«Ь для каждого а из X и каждого b из Y, либо Ь«а для каждого а из X и каждого b из Y. SP-BDD ассоциированная с ПП-цепью - это ROBDD (rctiuccd ordered BDD, т.е. минимизированный граф функции) для булевской функции ассоциированной с ПП-цепью, если выбранный порядок переменных - это линейный порядок, ассоциированный с ПП-цепью.

Пусть F - ПП-цепь с ассоциированной булевской функцией f. Тогда SP-BDD ассоциированная с F имеет минимальный размер среди всех ROBDD для f. Более точно, SP-BDD ассоциированная с F имеет в точности одну нетерминальную вершину для каждого аргумента функции f, и кроме того она имеет две терминальные вершины со значениями 0 и 1.

Для заданной ПП-цепи, ее SP-BDD в общем случае не является единственной, поскольку не является единственным ассоциированный с ней линейный порядок: мы можем получить один линейный порядок из другого просто перестановкой двух ПП-подцепей, соединенных параллельно. Рис.2 даст пример ПП-цспи и двух ассоциированных с ней SP-BDD, соответствующих двум различным линейным порядкам.

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

экстракция из электрической схемы ПП-цспи.

гГу

О

выход

исток

Рис.2. ПП-цепь и два варианта БР-ВОО, соответствующих двум различным ассоциированным линейным порядкам.

Как было отмечено выше, SP-BDD, представляющая ПП-цепь, не является единственной, поскольку не является единственным линейный порядок, ассоциированный с ПП-цспью. Но если мы рассмотрим стандартный статический КМОП-вентиль с комплементарными верхней (pull-up) и нижней (pull-down) ПП-цепями, то линейный порядок, ассоциированный одновременно с обеими этими ПП-цепями, является единственным.

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

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

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

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

БР-ВОО. ассоциированная с КМОП-вентилем, - это БР-ВОО, ассоциированная с его верхней ПП-цепыо и построенная с использованием линейного порядка, ассоциированного с КМОП-вентилем.

Поскольку этот линейный порядок является единственным, ассоциированная 5Р-1Ш0 является каноническим (единственным) представлением КМОП-вентиля. Очевидно, что она описывает как булевскую функцию, так и электрическую схему КМОП-вентиля. Показано, что это представление крайне удобно для многих целей и приложений. Пример КМОП-вентиля и его ассоциированной 5Р-ВОЭ показан на Рис.3.

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

Вложенная БР-ВОО - это БР-ВОЭ с сигналом или его инверсией, приписанными к каждой вершине, где сигнал - это булевская переменная из некоторого набора булевских переменных.

Каждая вложенная БР-ВОО соответствует некоторому КМОП-вентнлю, входящему в состав некоторой схемы.

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

вложенная ЭР-ВОО не является ни ЯОВОЭ, ни даже ОВОО для се функции, тем не менее это очень удобное представление для КМОП-вентиля, поскольку она содержит всю информацию как о булевской функции, так и об электрической схеме этого вентиля.

Полезными процедурами, разработанными для вложенной ЭР-ВОО, являются ПП-сужение и минимизация.

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

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

Рис.3. КМОП-всптиль (а) и его ассоциированная 5Р-ВОО (Ь).

переключаются между некоторыми промежуточными потенциалами вследствие: а) "плохих" логических уровней, Ь) разделения заряда. Например, в 3-входовом вентиле ЫАЫО при входном сигнале, показанном на Рис.4, в предположении напряжения питания 5В и одинаковых п- и р-транзисторов с пороговым напряжением 1В, узел 1 переключается между ОВ и 4В (из-за "плохого" логического уровня), а узел 2 переключается между ОВ и 2В (из-за разделения заряда между узлами I и 2). Следовательно, оценка мощности без учета точных значений узловых потенциалов может приводить к значительной ошибке.

. У ь и с

-1

УК'

Рис.4.3-входовый вентиль ЫЛИО и типичный входной сигнал.

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

статической КМОП схеме при единичном переключении получена формула: > ]

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

Q ' fomV

m

где интегрирование производится по времени переключения, Jm - ток через ш-й транзистор, суммирование производится по транзисторам закоротки (см. ниже). Итак, Q -полный заряд, перетекший через транзисторы закоротки в течение одного переключения схемы.

Рассмотрим процессы в отдельно взятой DCCC (dc-connected component, или подсхема, связанная но постоянному току), происходящие в течение одного переключения схемы. Некоторые транзисторы переключаются в проводящее состояние (включаются), некоторые другие - переключаются в непроводящее состояние (выключаются). В стационарном состоянии после завершения переключения существует часть DCCC (множество А узлов), dc-связаниая с VDD-узлом через проводящие транзисторы. Остальная часть DCCC (множество В узлов) dc-изолирована от VDD-узла. Мы можем также рассмотреть граф схемы с вершинами, соответствующими узлам схемы, и ребрами, соответствующими каналам транзисторов. В соответствии со .стационарным состоянием после единичного переключения схемы, можно разбить граф.схемы на два подграфа: подграф А (порождаемый множеством А узлов) и подграф В (порождаемый множеством В узлов).

Пример DCCC и соответствующего графа схемы показан на Рис.5. Показано состояние после конкретного переключения схемы, проводящие и непроводящие транзисторы помечены соответственно знаками плюс и минус. Подграф А содержит узлы {VDD,1} а подграф В содержит узлы {GND,2,3,4,5}.

В схеме также имеются транзисторы, соединяющие подграфы А и В. Назовем их транзисторами закоротки (это понятие относится, естественно, к конкретному переключению схемы). В примере на Рис.5 четыре транзистора, показанные на графе схемы жирными линиями, являются транзисторами закоротки.

Энергия перезарядки емкостей (CR-энергия) для единичного переключения схемы • это полная потеря энергии, вычисленная в предположении, что все транзисторы закоротки переключаются мгновенно в начале переключения схемы.

Энергия сквозных токов (SC-энергия) для единичного переключения схемы -это полная энергия (действительная) за вычетом CR-энергин.

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

Рис.5, Пример ОССС и соответствующего графа схемы.

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

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

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

- имеется петля обратной связи внутри одной ЭССС (итерации в пределах одной ЭССС);

- имеется петля обратной связи, включающая несколько ОССС (итерации в пределах нескольких ОССС).

При моделировании единичного переключения для одной ЭССС соответствующий граф схемы обходится в следующей последовательности:

- все двух-терминальные нижние пути из подграфа С;

- все двух-терминальные верхние пути из подграфа А;

- остальная часть подграфа С;

- остальная часть подграфа А;

- подграф О (остальная часть подграфа В).

При моделировании большой КМОП схемы алгоритм вначале производит разбиение схемы на ОССС и упорядочение ОССС в соответствии с направлением распространения сигнала (если это возможно). Моделирование всей схемы -событийное, с использованием глобальной очереди событий. Если событие (под событием мы понимаем здесь переключение узла) имеет место на одном из входов ЭССС, то:

- для этой ОССС производится ключевое моделирование с вычислением СЯ-энсргин, как это было описано выше;

- если на выходе ОССС генерируется новое событие, то время этого события вычисляется по времени события на входе с использованием Элморовской задержки;

- аналогичным образом вычисляется длительность фронта для нового события;

- вычисляется также БС-энсргия для переключения ГССС.

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

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

проводящее состояние, и это приводит к переключению ПП-цепн в проводящее состояние.

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

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

<1={Ях + гх)Сх+АЫ{х)

где = " максимальнос предшествующее сопротивление, r¡ -

сопротивление проводящего 1-го транзистора, {Р} - множество путей от узла истока к транзистору х, гх - сопротивление проводящего транзистора х, Щх) - узел, к которому транзистор х нижне-присоединсн,

Ан(Х) = "",*<ш<1')9

- ЯС-сумма для узла Щх), • множество путей от узла Щх) к узлу выхода, Сх -емкость дерева для транзистора х, т.е. максимальная емкость, перезаряжаемая при переключении транзистора х в проводящее состояние (то же для С'¡). (Здесь и далее путь в ПП-цепи - это подпуть полного пути. Полный путь - это нссамопересскающийся путь от узла истока к узлу выхода.)

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

A. Инициализация и подготовка обратного прохода БР-ВОО.

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

C. Вычисление емкостей деревьев.

О. Вычисление ЯС-сумм и задержек (обратный проход БР-ВЭЭ).

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

векторов длиной 2000. Результаты свидетельствуют об очень хороших точности и быстродействии данного алгоритма. Разница в среднем токе питания между данным алгоритмом и известной программой Ро\уегМШ не превышает несколько процентов, однако данный алгоритм много быстрее (в среднем в 15-20 раз), что делает его пригодным как для быстрого расчета мощности, потребляемой большими КМОП схемами, так и для использования внутри оптимизационного цикла.

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

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

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

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

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

Найти минимум целевой функции F(x) посредством выбора оптимального вектора размеров х = (Х|,..., х„), где Wj = axj + b - ширина j-ro транзистора, минимальный размер b и шаг а могут зависеть от типа транзистора (п или р), все Xj - неотрицательные целые числа. Целевую функцию определим следующим образом:

F(x) = С D(x) + Р(х)

где:

D(x) - разность между действительной и максимальной допустимой задержкой, если

она положительна, и О если отрицательна,

Р(х) - мощность, площадь или их комбинация,

С - очень большое число ("бесконечность").

Возможно также наличие некоторых других ограничений.

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

Каждый шаг отжига состоит в случайном выборе одного транзистора из множества и изменении его размера Xj в большую или меньшую сторону. Если нарушаются какие либо ограничения, то данное изменение отклоняется, в противном случае оно либо принимается либо отклоняется с вероятностью, зависящей от изменения целевой функции и значения температуры на текущем шаге. В традиционной версии метода вероятность на шаге i отжига равна 1 при F^Fj.j (F; -значение целевой функции на ¡-м шаге), а в противном случае - пропорциональна expHFi-Fi.,)/^), ТраТи, Т0>0,0<а<1

Указанный традиционный температурный план с монотонным охлаждением базируется на аналогии со статистической механикой и минимизирует математическое ожидание значения целевой функции для текущего состояния системы после очередного шага (WYA-состояние, "Where-You-Are"). Но в действительности мы всегда используем лучшее из состояний, пройденных системой в процессе отжига (BSF-состояние, "Best-So-Far"). Таким образом, обычные обоснования плана монотонного охлаждения не вполне корректны.

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

функции для ВвР-состояния) для некоторых простых задач оптимизации, и установлено следующее:

• реально вычислить оптимальный ВБИ-план возможно лишь для очень простых схем (состоящих из нескольких транзисторов);

• все оптимальные ВБИ-планы отличны друг от друга и от монотонного.

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

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

Пусть состояние системы описывается вектором х=(х[,...,хп), где х^ пробегает все

целые значения. Целевая функция задается формулой: п 2

Р(х) - - к^ш) , если (к}-1/2)т<Х}<(куН/2)т, х * (1т, 0,..., 0)

1 -1, если х = (1ш, 0,..., 0)

Рассмотрим процедуру моделируемого отжига для данной системы с начальным состоянием х° =(0,...,0) и длиной 1т шагов. Очевидно, что математическое ожидание цены для оптимального плана с числом единичных шагов меньшим, чем 1т, равно нулю (при этом оптимальный ВБР-план - просто любой план, а оптимальным WYA-планом является, например, план с нулевой температурой).

Если длина (т.е. число шагов) отжига равна 1т, то математическое ожидание цены для оптимального плана (как ВБР, так и \УУА) меньше 0 из-за состояния со значением целевой функции -1. Единственная траектория от начального состояния до данного есть

х^ = 0.0,-.0), ]=0,...,1т Оптимальный план может быть найден из следующего условия:

Т1 = а^тах Р(х^"')

где Р(х'/х'-') есть вероятность состояния х' после j шагов при условии, что система находилась в состоянии х-1'1 после >1 шагов. Тогда для Т* справедливо следующее:

Tj=0, если F(xj)£F(xj~')

-да, если F(xJ)>F(xJ_1) Таким образом, для рассматриваемой системы имеем оптимальный план отжига (как BSF, так и WYA), показанный на рис. 6.

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

т/2 т Зт/2 2т (|-|/2)т 1т 1

Рис.6. Оптимальный план отжига для модельной системы.

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

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

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

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

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

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

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

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

реструктуризацию и выбор оптимальных размеров. Поэтому ресинтез последовательно разбивает схему на небольшие логические сегменты (подсхемы), которые будем называть окнами. Обычно каждое окно содержит до 50 транзисторов, что составляет приблизительно 10-20 вентилей. Ресинтез генерирует большое количество транзисторных структур, функционально эквивалентных исходному окну, используя метод моделируемого отжига (см. четвертую главу). Генерируемые варианты ■ окна различаются как способом их составления из индивидуальных вентилей, так и структурой вентилей. Каждое окно также образмеривается с помощью быстрого приближенного алгоритма выбора оптимальных размеров, для того, чтобы уложиться в размеры исходного окна. Будем называть этот процесс перебора вариантов окна локальным ресиитезом. Локальный ресинтез сравнивает каждый вариа!гт окна с исходным окном. Наилучший вариант окна вставляется в схему вместо исходного, с минимальными размерами транзисторов. Затем для всей схемы производится выбор оптимальных размеров транзисторов до исходной площади, и схема проверяется на улучшение параметров (быстродействия). (Пунктирные кривые иа Рис.7 показывают образмериванис схемы с новым окном). Наилучший вариант окна (с точки зрения быстродействия схемы) сохраняется после каждой итерации, тогда как остальные варианты окна отбрасываются. Ресинтез производится в два этапа. На первом этапе вся схема покрывается окнами, и каждое окно минимизируется по площади при минимальных размерах всех транзисторов. Этот этап приводит к созданию схемы с минимизированной площадью, представленной крайней правой точкой кривой на Рнс.7. На втором этапе окнами покрывается только критический путь, и каждое окно оптимизируется для улучшения быстродействия. После того, как критический путь покрыт таким образом, схема образмеривается для увеличения ее площади на заданный процент. Далее вышеописанная процедура повторяется.

Глобальным ресиитезом будем называть алгоритм рссинтеза схемы в целом. Схема этого алгоритма показана на Рис.8. Как указывалось выше, глобальный ресинтез основан на покрытии всей схемы последовательностью окон (связных подсхем) и выполнении локального рссинтеза на каждом из окон.

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

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

Рис.8. Блок-схема глобального рссиитсза.

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

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

• Л. Преобразование ДсМоргана меняет вентиль на комплементарный, с добавлением или удалением инверторов на его входах и выходах.

• В. Переупорядочение меняет местами две ПП-цепи, соединенные последовательно, в верхней или нижней цепи вентиля.

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

• D. Шаг слияния объединяет два последовательных встиля с инвертором между ними в один сложный вентиль. Если промежуточного инвертора нет, то для одного из двух вентилей может быть выполнено предварительное преобразование ДсМоргана. В результате слияния может появиться вентиль с избыточной структурой. Поэтому после слияния производится минимизация вентильной BDD.

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

, "^ч_1

(а)

(Ь)

(с)

Рис.9. Примеры преобразований БР-ВОО и соответствующих вентилей: (а) слияние и

декомпозиция (прямая стрелка - декомпозиция, обратная - слияние); (Ь) преобразование ДеМоргана; (с) переупорядочение (отмстим, что переупорядочение в данном случае не может быть сведено к переназначению входов вентиля).

вентиля, удаление и вставка буфера). Пример результата локального рссинтеза показан на Рис. 10.

чцч

Рис.10. Исходная схсма (с 17), содержащая 24 транзистора, и результат локального ресинтеза, содержащий 22 транзистора.

Описанный выше алгоритм рееннтеза был реализован в виде экспсрименталь-тальной программы, с которой был проведен ряд численных экспериментов. На Рис. 11 показана кривая площадь-задержка, являющаяся результатом ресинтеза комбинационной схемы, содержащей около 120 вентилей 500 транзисторов). На Рис.11 показана точка, соответствующая исходной схеме, синтезированной промышленной программой логического синтеза (с оптимизацией быстродействия). Синтез проводился с использованием богатой библиотеки стандартных ячеек, содержащей 150 ячеек (4-5 вариантов с различной нагрузочной способностью для каждого типа логического вентиля). Кривая 1 на рис. - это кривая площадь-задержка для исходной схемы, полученная с помощью параметрической оптимизации с индивидуальным выбором оптимального размера каждого транзистора.

Кривая 2 показывает результаты ресинтеза исходной схемы. Ресшгтсз заметно улучшает параметры даже оптимизированной схемы с индивидуально выбранными размерами транзисторов (улучшение быстродействия на 15% при тон же площади и уменьшение площади на 30% при том же быстродействии). По сравнению с исходной схемой ресинтез дал улучшение быстродействия на 20% при той же площади и уменьшение площади на 37% при том же быстродействии. Следует также отметить, что количество транзисторов в схеме в результате ресинтеза уменьшилось на 20% (для минимальной площади) и на 5% (для площади, соответствующей исходной схеме).

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

В диссертации представлена оригинальная модель для важного класса КМОП схем на проходных транзисторах - CPL схем (Complementary Pass-transistor Logic). Модель основана на использовании BDD специального вида (SBDD-модель). На базе указанной модели разработаны эффективные апгор"тмн р?<-ц<тя задержек и потребляемой мощности для у

С.Петербург ОЭ МО «г

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

Удобно представить схему на проходных транзисторах с использованием BDD, т.к. функционирование двух-транзисторного мультиплексора аналогично функциии BDD вершины в лишрамме двоичных решений. Из-за симметричности CPL схем одна BDD вершина может представлять два мультиплексора на проходных транзисторах одновременно. Для представления CPL схем (их структуры и логики) мы используем сеть разделяемых (многовыходных) BDD у которых вершины и ребра имеют атрибуты (более коротко: SBDD, или shared BDD). Мы используем только один вид атрибутов: инверсию.

Простая вершина вычисляет некоторый сигнал и передает его родительской вершине неизмененным. Инвертированная вершина передает родительской вершине инвертированный сигнал. Таким образом, инвертированная вершина соответствует мультиплексору на проходных транзисторах и выходным инверторам CPL вентиля (обычно, с транзисторами обратной связи, см. Рис.12.). Переменные в квадратах вычисляются через другие вершины или берутся с первичных входов.

Предлагаемый алгоритм расчета задержек для СРЬ схем основан на БВОО-ирсдставлснии и содержит следующие шаги:

• Вычисление емкостей узлов и инициализация.

• Вычисление емкостей деревьев.

• Вычисление максимального предшествующего вершине сопротивления.

Ь_М Ц_ь Ь J Ц_Ь

"i Р" 1 Г

'с d с "3"

Рис.12. Инвертированная вершина SBDD.

• Вычисление RC-сумм и DCCC задержек.

• Вычисление времени прибытия сигналов (arrival times), требуемого времени прибытия сигналов (required times) и дефицита времени сигналов (slacks).

Предлагаемый алгоритм расчета мощности основан на преобразовании SBOD в эквивалентную SP-BDD. Разработанные в диссертации алгоритмы параметрической и структурной оптимизации для CPL схем также основаны на использовании SBDD модели. Все указанные алгоритмы легко адаптируются к другим типам схем на проходных транзисторах: PTL схемам (pass transistor logic) и TGL схемам (transmission gate logic).

В седьмой главе диссертации рассмотрены методы анализа помехоустойчивости цифровых схем, использование которых становится все более актуальным при проектировании СБИС. После того, как определены потенциальная жертва и группа агрессоров (узлы схемы), последовательно используются несколько фильтров (алгоритмов) для того, чтобы сделать оценку помехи более точной. Ряд таких фильтров основан на учете логики цифровой схемы. В одном из типов этих методов производится поиск наихудшего 2-вскторного теста, с использованием характеристической функции схемы и решением ОЗБО (оптимизационной задачи с булевским ограничением, в англоязычном оригинале - ВСОР, boolean constraint optimization problem). Известны также другие методы, основанные на понятии цифровой чувствительности и CODC (compatible observability don't care set). Все указанные подходы имеют высокую сложность и требуют большого времени счета при применении к большим схемам.

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

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

Простая логическая импликация (ПЛИ) между двумя узлами схемы а, Ь - это отношение типа (а=0)->(Ь=1) или, используя более короткое обозначение, а->Ь. Рассмотрим в качестве примера небольшую схему (Рис.13). Из логического 0 в узле п7 следует логическая I в узлах пЗ, п4, п8, п9, а также логический 0 в узле п! 1. В целом данная схема имеет 26 нетривиальных ПЛИ. (Тривиальная ПЛИ - это а->а.)

Все ПЛИ к данному узлу схемы хранятся в виде четырех списков импликаций: Например, на Рис.13 один из списков импликаций в узле п7 - это

Ньп7={пЗ,п4,п8,п9}.

Алгоритм генерации ПЛИ основан на распространении ПЛИ через простые вентили. Для этого используются следующие основные операции: объединение списков, пересечение списков, контра-позитивный закон. Рассмотрим, например, 2-входовый вентиль AND с входами a, b и выходом х. Если мы имеем списки импликаций в а, Ь, то список импликаций Lv* вычисляется как объединение списков Lya и Lyb, а список Ну* вычисляется как пересечение списков Ну® и НуЬ (здесь V -либо Н либо L). Аналогичные правила используются для вентиля OR и инвертора. Как только новая импликация получена на выходе вентиля, добавляется также обратная импликация, полученная с помощью контра-позитивного закона:

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

Рис.13. Пример логических импликаций в простой схеме (с17).

если (a=va)->(b=vb) то (b=vb)->(a=va).

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

При Прямом распространении ПЛИ (т.е. при распространении вперед) мы обрабатываем ROBDD в топологическом порядке, от первичных входов к первичным выходам. При обработке одной ROBDD мы обрабатываем каждую нетерминальную вершину в топологическом порядке, от терминальных вершин к корневой вершине.

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

Рассмотрим 2-входовый вентиль AND со входами а,Ь и выходом х. Когда мы производим прямое распространение ПЛИ с использованием пересечения списков, в действительности мы используем следующую 3-ЛИ (логическую импликацию между 3 узлами): а&Ь->х. Например, мы можем скомбинировать эту 3-ЛИ с парой ПЛИ р->а,'р->Ь, и получить новую ПЛИ р->х.

Однако мы можем записать данную 3-ЛИ также и в другой форме: а&х->Ь. Мы также можем скомбинировать эту 3-ЛИ с парой ПЛИ q->a, q->x, и получеть новую ПЛИ q->b. Мы называем эту операцию боковым распространением ПЛИ через 2-входовый вентиль. Для иллюстрации того факта, что боковое распространение нельзя свести к прямому распространению, рассмотрим следующий простой пример (Рис.14).

Рис.14. Иллюстрация бокового распространения ПЛИ

В данном примере мы можем скомбинировать 3-ЛИ а&х->Ь с двумя ПЛИ у->а, у->х, и получить новую ПЛИ у->Ь. Нетрудно увидеть, что эта ПЛИ не может быть

получена с помощью только прямого распространения ПЛИ.

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

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

Таким образом, алгоритм генерации ПЛИ может быть описан с помощью следующего пссвдо-кода:

инициализировать списки тривиальными ПЛИ; повторять {

для (каждого вентиля в прямом порядке)

произвести прямое распространение ПЛИ с применением контра-иознтивиого закона; } до установления; повторять {

для (каждого вентиля в обратном порядке) для (каждого входа вентиля)

произвести боковое распространение ПЛИ с применением транзитивного и коитра-иоштивиого законов;

повторять {

для (каждого вентиля в прямом порядке)

произвести прямое распространение ПЛИ с применением коитра-позитнвного закона; } до установлении; } до установления;

Результаты тестирования алгоритма генерации ПЛИ приведены в Таблице 1.

Таблица 1. Результаты тестирования алгор1ггма генерации ПЛИ.

схема с432 с 1355 с1а1 сп1_0 ст_1 СМ_ ОПСБ сп(_ гего$ 1с51ск!

Яузлов 248 559 333 83 87 97 99 474

ШЛИ (П) 7826 27218 5136 1196 1222 1976 1812 82572

ШЛИ (П+О) 20210 32802 5672 1466 1516 2248 2098 86444

% 158 21 10 23 24 14 16 5

шли/ пару 0.33 0.10 0.05 0.21 0.20 0.24 0.21 0.38

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

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

• один узел-жертва V

• набор узлов-агрессоров А;, ¡=1,...,п

• тип помехи

• вес помехи w(V>A¡) для каждого А;

- * порогСуммыВ - максимальная разрешенная сумма весов для возможной комбинации агрессоров.

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

• Н^ЬРаН, жертва: 1, агрессоры: |->0

• ЬоиЯие, жертва: 0, агрессоры: 0-> 1

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

A. Вычисление ПЛИ (см. выше).

B. Формирование графа ограничений (ГО).

C. Решение задачи НММВ (Независимое Множество Максимального Веса) для ГО и сравнение веса НММВ с порогСуммыВ.

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

Для формирования ГО с использованием ПЛИ мы должны рассмотреть два типа взаимодействий:

• жертва-агрессор (для каждого А;);

• агрессор-агрессор (для каждой пары агрессоров).

Когда задан тип помехи, мы знаем для V и для каждого А; начальное и конечное состояние: (Vе,V11); (А", А"), ¡=1,...,п. ГО будет содержать вершины, соответствующие некоторым из агрессоров. Следующие ПЛИ должны быть рассмотрены для взаимодействия жертва-агрессор:

Vе-> А°, V" -> А;п.

Если по крайней мере одна из этих ПЛИ найдена, то вершина для А; не включается в ГО.

После этого формируется ГО с вершинами для каждого А|, для которого не найдено ни одной ПЛИ указанного выше типа. Вес вершины для А; равен \у(У,А]). Ограничения (ребра ГО) находятся следующим путем (на основе взаимодействия агрессор-агрессор). Для каждой пары вершин (А-,,Ар мы ищем следующие ПЛИ:

А° -> А;0, А-" -> А". Если хотя бы одна из этих ПЛИ найдена, то ребро (А;,Ар добавляется в ГО.

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

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

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

Заключение

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

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

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

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

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

4) Разработан метод структурной оптимизации (ресннтеза) цифровых КМОП схем. Метод основан на использовани 5Р-[ШО модели КМОП схемы. В ходе ресннтеза в схеме последовательно выделяются подсхемы относительно небольшого размера (окна), которые подвергаются локальному ресинтезу на транзисторном уровне. Предложенный метод позволяет значительно улучшить качество проектируемой схемы. Например, для исходной схемы, синтезированной одной из лучших программ логического синтеза (Бупорэуз) достигается уменьшение площади или потребляемой мощности на 10-50% без ухудшения ее быстродействия. При этом время счета для метода ресннтеза в несколько раз меньше времени счета программы логического синтеза.

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

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

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

8) Разработан метод анализа помехоустойчивости цифровой схемы на основе

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

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

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

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

1. Glebov A.L., Lialinsky A.A., Rusakov S.G. Optimization of CMOS Circuits Based on Parameterized Cells // Proc. of 4-th Intern. Design Automation Workshop. Moscow, 1994.-P. 17.

2. Glebov A.L. BDD Based Algorithms for Series-Parallel Network Representation and Manipulation // Proc. of 4-th Intem. Design Automation Workshop. Moscow, 1994. -P. 32.

3. Glebov A.L., Lialinsky A. A., Rusakov S.G. Optimization of CMOS Circuits Based on Parameterized Cells//Proc. of 4-th Intern. Workshop PATMOS-94. Barcelona, 1994. -P. 178.

4. Glebov A.L., Blaauw D., Jones L.G. Transistor Reordering for Low Power CMOS Gates Using SP-BDD Representation // Int. Symp. on Low Power Design. Dana Point, CA. - 1995.-P. 161.

5. Глебов Л.Л. SP-BDD модель цифровых КМОП схем и ее приложения в оптимизации и моделировании // 2-я международная конференция "Микроэлектроника и информатика". - М., 1995. - С. 44.

6. Gavrilov S., Glebov A., Rusakov S., Blaauw D., Jones L., Vijayan G. Power loss calculation for digital static CMOS circuits // Proc. of European Design and Test Conference (ED&TC). Paris, 1997. - P. 411.

7. Glebov A., Gavrilov S., Blaauw D., et.al. Library-Less Synthesis for Static CMOS Combinational Circuits // Proc. of IEEE/ACM Intern. Conf. on Computer Aided Design (ICCAD). San Jose, CA. - 1997. - P. 658.

8. Глебов А.Л., Стсмпковский А.Л. Оптимизация низкомощных цифровых КМОП схем // Автоматизация проектирования. - 1997. - Вып. 3. - С. 11.

9. Глебов А.Л. SP-BDD модель цифровых КМОП схем и ее приложения в оптимизации и моделировании // Информационные технологии. • 1997. - Вып. 10.

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

11. Глебов А.Л., Ларкичев С.Ю. Алгоритм расчета задержки в цифровых комбинационных схемах с учетом истинных путей распространения сигнала // 3-я Международная конференция "Микроэлектроника и информатика". - М., 1997. - С. 40.

12. Глебов А.Л., Лопатников С.Ю. Новый алгоритм моделируемого отжига для оптимизации КМОП схем // Информационные технологии. - 1998. - Вып. 1.

13. Glebov A., Nadezhin D. Fast delay and power estimation for digital CMOS circuits // Proc. of 1-st Intern. Workshop "Multi-Architecture Low Power Design". Moscow, 1999. - P. 3.

14. Gavrilov S., Glebov A. BDD-based circuit level structural optimization for digital CMOS // Proc. of 1-st Intern. Workshop "Multi-Architecture Low Power Design". Moscow, 1999. - P. 45.

15. Глебов А.Л., Соловьев A.H. Оптимизация цифровых синхронных КМОП СБИС // Информационные технологии. - 2000. - Вып. 2. - С. 34.

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

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

18. Glebov А-, Gavrilov S., Blaauw D., et.al. False-Noise Analysis Using Logic Implications // Proc. of IEEE/ACM Intern. Conf. on Computer Aided Design (ICCAD). San Jose, CA.-2001.-P. 515.

19. Glebov A., Gavrilov S., Zolotov V., et.al. False-Noise Analysis Using Resolution Method // Proc. of. Int. Symp. on Quality Electron Design. San Jose, CA. - 2002. - P. 437.

20. Glcbov A., Gavrilov S., Blaauw D., Zolotov V. Falsc-noisc analysis using logic implications // ACM Trans, on Design Automation of Electronic Systems (TODAES).

- 2002. - V. 7.-N3.-P.474.

21. Гаврилов C.B., Глебов A.JI., Стемпковскнй А.Л. Анализ помехоустойчивости цифровых схем на основе логических импликации // Известия ВУЗов, Электроника.

- М„ 2002. - Вып. 5. - С. 60.

22. Гаврилов C.B., Глебов А.Л., Стемпковскнй А.Л. Быстрый алгоритм расчета мощности в цифровых КМОП схемах И Электроника: наука, технология, бизнес.

- М., 2002, - Вып. 4, - С. 40.

23. Гаврилов C.B., Глебов А.Л., Стемпковскнй А.Л. Структурная оптимизация цифровых КМОП схем // Информационные технологии и вычислительные системы.

- М., 2002. - Вып. 4. - С. 34.

24. Глебов А.Л., Гурарий М.М., Егоров Ю.Б. и др. Актуальные проблемы моделирования в системах автоматизации схемотехнического проектирования // - М.: Наука, 2003. - 437 с.

2аоМ

~2o2í¿f »20212

Введение.

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

1.1. Методы расчета мощности в цифровых КМОП схемах.

1.2. Параметрическая оптимизация.

1.3. Структурная оптимизация.

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

1.5. Выводы.

Глава 2. Последовательно-параллельные диаграммы двоичных решений

SP-BDD).

2.1. Определения и основные свойства.

2.2. Основные операции на SP-BDD.

2.3. SP-BDD и КМОП-схемы.

2.4. Выводы.

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

3.1. Оценка мощности, потребляемой КМОП схемой.

3.2. Последовательность процедур моделирования.

3.3. Ключевое моделирование с использованием SP-BDD.

3.4. Алгоритм расчета задержек с использованием SP-BDD.

3.5. Расчет энергии сквозных токов.

3.6. Быстрая вероятностная модель мощности.

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

3.8. Выводы.

Глава 4. Параметрическая оптимизация цифровых КМОП схем.

4.1. Оптимизация схем, спроектированных на базе параметризованных ячеек.

4.2. Использование метода моделируемого отжига при параметрической оптимизации.

4.3. Выводы.

Глава 5. Структурная оптимизация цифровых КМОП схем.

5.1. Обзор метода ресинтеза.

5.2. Глобальный ресинтез.

5.3. Локальный ресинтез.

5.4. Пространство состояний в локальном ресинтезе.

5.5. Выводы.

Глава 6. Анализ и оптимизация цифровых КМОП схем на проходных транзисторах.

6.1. КМОП схемы на проходных транзисторах и модель задержек для них.

6.2. Модель мощности для цифровых КМОП схем на проходных транзисторах.

6.3. Параметрическая оптимизация цифровых КМОП схем па проходных транзисторах.

6.4. Структурная оптимизация цифровых КМОП схем на проходных транзисторах.

6.5. Выводы.

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

7.1. Методы определения логических корреляций между сигналами цифровой схемы.

7.2. Методы анализа помех в цифровой схеме на основе корреляций между сигналами.

7.3. Анализ помехоустойчивости цифровой схемы на основе результатов временного анализа.

7.4. Выводы.

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

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

8.2. Экспериментальные результаты по параметрической оптимизации цифровых КМОП схем.

8.3. Экспериментальные результаты но структурной оптимизации цифровых КМОП схем.

8.4. Выводы.

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

История развития большей части указанных методов насчитывает не один десяток лет. Следует отметить, что как в нашей стране, так и за рубежом получеп значительный ряд результатов в области логического синтеза и оптимизации цифровых схем. Самостоятельное направление составили исследования по синтезу схем на транзисторном уровне, связанные с известными работами Глориозова E.JI. [110], Шагурипа И.И. [111], Кармазинского A.II. [112], Немудрова В.Г. [113]. Несмотря па значительный прогресс в этой области, существует потребность в новых и более эффективных методах и алгоритмах анализа и оптимизации. К факторам, порождающим такую потребность можно отнести:

- постоянное снижение размеров элементов (транзисторов, межсоединений), а также рост числа элементов на кристалле;

- необходимость проектирования схем с низкой потребляемой мощностью;

- возрастающее разнообразие стилей проектирования, которые используются или могут быть использованы при разработке СБИС.

Для удовлетворения указанных потребностей необходимо создать новое поколение методов анализа и оптимизации цифровых КМОП схем, включая анализ мощности и помехоустойчивости, обладающих значительно более высокими производительностью и качеством результатов по сравнению с существовавшими ранее. Для создания таких методов необходима новая математическая модель цифровых КМОП схем. Базой этой модели могут стать BDD (binary decision diagrams, или диаграммы двоичных решений), ранее успешно использовавшиеся для представления булевских функций в логическом синтезе. На решение указанных задач нацелена настоящая диссертация.

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

Основные задачи работы:

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

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

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

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

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

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

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

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

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

• Предложена оригинальная теоретико-графовая модель цифровых КМОП схем, основанная на впервые введенных BDD (диаграммах двоичных решений) специального вида (SP-BDD). Разработана теория SP-BDD, включающая набор базовых методов и алгоритмов работы с этими объектами. Данная модель позволяет эффективно производить вычислительные операции для КМОП вентилей в рамках различных алгоритмов.

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

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

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

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

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

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

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

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

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

• Новый метод структурной оптимизации (ресинтеза) цифровых КМОП схем, основанный па использовании SP-BDD модели. В данном методе на каждом таге оптимизационной процедуры используется как детальное описание схемы на транзисторном уровне, так и описание ее логической функции. Метод позволяет значительно улучшить параметры схемы, предварительно синтезированной и оптимизированной лучшими из известных программ логического синтеза.

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

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

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались и обсуждались на 4-м международном семинаре по автоматизации проектирования "Russian Workshop" (Москва, 1994), 4-м международном семинаре по проектированию низкомощных и быстродействующих интегральных схем "PATMOS" (Испания, 1994), Между народном симпозиуме ио проектированию пизкомощных интегральных схем "ISLPD" (США, 1995), 2-й между народной конференции "Микроэлектроника и информатика" (Москва, 1995), Европейской конференции по проектированию и тестированию интегральных схем "ED&.TC" (Франция, 1997), Международной конференции по компьютерному проектированию интегральных схем "ICCAD" (США, 1997), 3-й международной конференции "Микроэлектроника и информатика" (Москва, 1997), 1-м международном семинаре по проектированию мульти-архитектурных низкомощпых интегральных схем "MALOPD" (Москва, 1999), Международном семинаре по помехоустойчивости интегральных схем "Signal Integrity Workshop" (США, 2000), 3-й международной конференции "Электроника и информатика - XXI век" (Москва, 2000), Международной конференции по компьютерному проектированию интегральных схем "ICCAD" (США, 2001), Международном симпозиуме по качественному проектированию интегральных схем "1SQED" (США, 2002).

Публикации. По теме диссертации опубликованы 24 печатные работы, в том числе одна монография.

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

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

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

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

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

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

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

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

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

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

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

6) Разработаны методы параметрической и структурной оптимизации для цифровых КМОП схем на проходных транзисторах. Указанные методы пригодны для схем различных типов: схем CPL (комплементарная логика на проходных транзисторах), TGL (логика на проходных ключах), PTL (простая логика на проходных транзисторах). Результаты проведенных численных экспериментов свидетельствуют о высоких производительности и эффективности предлагаемых методов.

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

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

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

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

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

2. Tsui C.Y., Pedram M., Despain A.M. Technology Decomposition and Mapping Targeting Low Power Dissipation// Proc. of 30th Design Automation Conference, Dallas, June 14-18, 1993, p.68.

3. Tiwari V., Ashar P., Malik S. Technology Mapping for Low Power // Proc. of 30th Design Automation Conference, Dallas, June 14-18, 1993, p.74.

4. Marculescu R., Marculescu D., Pedram M. Switching Activity Analysis Considering Spa-tiotemporal Correlations // Intern. Conf. on Computer Aided Design, 1994, p.294.

5. Marculescu R., Marculescu D., Pedram M. Efficient Power Estimation for Highly Correlated Input Streams // Proc. of 32nd Design Automation Conference, San Francisco, June 1216, 1995, p.628.

6. Mechta H., Borah M., Owens R.M., Irwin M.J. Accurate Estimation of Combinational Circuit Activity // Proc. of 32nd Design Automation Confercncc, San Francisco, June 12-16, 1995, p.618.

7. Saxena V., Najm F.N., Hajj I.N. Monte-Carlo Approach for Power Estimation in Sequential Circuits // Proc. of European Design & Test Conference, Paris, March 17-20, 1997, p.416.

8. Kim Y.H., Hwang S.H., Newton A.R. Electrical-Logic Simulation and Its Applications // IEEE Trans, on CAD, 1989, v.8, p.8.

9. Saleh R.A., Newton A.R. Mixed-Mode Simulation. 1990.

10. Rabe D., Timmermann В., Ncbel W. CMOS Library Characterization for Power Consumption // PATMOS-94, p.94.

11. Najm F.N. Feedback, Correlation, and Delay Concerns in the Power Estimation of VLSI Circuits // Proc. of 32nd Design Automation Conference, San Francisco, June 12-16, 1995, p.612.

12. Najm F.N., Zhang M.Y. Extreme Delay Sensitivity and the Worst-Case Switching Activity in VLSI Circuits // Proc. of 32nd Design Automation Conference, San Francisco, June 12-16, 1995, p.623.

13. Hayes J.P. A Unified Switching Theory with Applications to VLSI Design // Proc. IEEE, 1982, v.70, p. 1140.

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

15. Huizer C.M. Power Dissipation Analysis of CMOS VLSI Circuits by Means of Switch-Level Simulation // Proc. of 16-th European Solid-State Circuit Conf., 1990, p.61.

16. Gavrilov S., Glebov A., Rusakov S., ct.al. Fast Power Loss Calculation for Digital Static CMOS Circuits // Proc. of European Design & Test Conference, Paris, March 17-20, 1997, p.411.

17. Cheng D.I., Cheng K.T., Wang D.C., Marck-Sadowska M. A New Hybrid Methodology for Power Estimation // Proc. of 33rd Design Automation Conference, Las Vegas, June 9-13, 1996, p.439.

18. Fishburn J.P., Dunlop Л.Е. TILOS: A Posynomial Programming Approach to Transistor Sizing // Intern. Conf. on Computer Aided Design, 1995, p.326.

19. Sapatnckar S.S., Rao V.B., Vaidya P.M., Kang S.M. An Exact Solution to the Transistor Sizing Problem for CMOS Circuits Using Convex Optimization // IEEE Trans, on CAD, 1993, v.12, p.1621.

20. Hoppe В., Neuendorf G., Schmitt-Landsiedel D. Optimization of High-Speed CMOS Logic Circuits with Analytical Models for Signal Delay, Chip Area and Dynamic Power Dissipation // IEEE Trans, on CAD, 1990, v.9, p.236.

21. Borah M., Owens R.M., Irwin M.J. Transistor Sizing for Minimizing Power Consumption of CMOS Circuits under Delay Constraint // Int. Symp. on Low Power Design, 1995, p. 167.

22. Glebov A.L., Lialinsky A.A., Rusakov S.G. Optimization of CMOS Circuits Based on Parameterized Cells // PATMOS-94, p. 178.

23. Hsieh Y.C., Hwang C.Y., Lin Y.L., Hsu Y.C. LiB: A CMOS Cell Compiler// IEEE Trans, on CAD, 1991, v.l0,p.994.

24. Baltus D.G., Allen J. SOLO: A Generator of Efficient Layout from Optimized MOS Ciruit Schematics // Proc. of 25th Design Automation Confercncc, Anaheim, June 12-15, 1988, p.445.

25. Boyer D.G. Symbolic Layout Compaction Review // Proc. of 25th Design Automation Conference, Anaheim, June 12-15, 1988, p.383.

26. Berkelaar M., Jess J. Gate Sizing in MOS Digital Circuits with Linear Programming // EDAC-90, p.217.

27. Berkelaar M., Buurman P., Jess J. Computing the Entire Active Area/Power Consumption versus Delay Trade-off Curve for Gate Sizing with a Piecewise Linear Simulator // Intern. Conf. on Computer Aided Design, 1994, p.474.

28. Chen D.S., Sarrafzadeh M. An Exact Algorithm for Low Power Library-Spccific Gate Resizing // Proc. of 33rd Design Automation Conference, Las Vegas, June 9-13, 1996, p.783.

29. Bahar R.I., Hachtel G.D., Macii E., Somcnzi F. A Symbolic Method to Reduce Power Consumption of Circuits Containing False Paths // Intern. Conf. on Computer Aided Design, 1994, p.368.

30. Bahar R.I., Cho H., Hachtel G.D., ct.al. Timing Analysis of Combinational Circuits Using ADD's // Proc. of European Design & Test Conference, Paris, March 1994.

31. Coudert O. Gate Sizing: A General Purpose Optimization Approach // Proc. of European Design & Test Conference, Paris, March 11-14, 1996, p.214.

32. Devadas S., Malik S. A Survey of Optimization Techniques Targeting Low Power VLSI Circuits // Proc. of 32nd Design Automation Conference, San Francisco, June 12-16, 1995, p.242.

33. Iman S., Pedram M. Logic Extraction and Factorization for Low Power// Proe. of 32nd Design Automation Confcrcncc, San Francisco, June 12-16, 1995, p.248.

34. Fishburn J.P. A Depth-Decreasing Heuristic for Combinational Logic, or How to Convert a Ripple-Carry Adder into Carry-Lookahead Adder or Anything In-Between // Proe. of 27th Design Automation Conference, 1990, p.361.

35. Carlson B.S., Lee S.J. Delay Optimization of Digital CMOS VLSI Circuits by Transistor Reordering// IEEE Trans, on CAD, 1995, v. 14, p. 1183.

36. Caufape S., Figueras J. Power Optimization of Delay Constrained CMOS Bus Drivers // Proc. of European. Design & Test Conference, Paris, March 11-14, 1996, p.205.

37. Turgis S., Azemad N., Auvergne D. Design and Selection of Buffers for Minimum Power-Delay Product // Proc. of European Design & Test Conference, Paris, March 11-14, 1996, p.224.

38. Glebov A.L., Blaauw D., Jones L.G. Transistor Reordering for Low Power CMOS Gates Using SP-BDD Representation // Int. Symp. on Low Power Design, 1995, p. 161.

39. Musoll E., Cortadella J. Optimizing CMOS Circuits for Low Power Using Transistor Reordering// Proc. of European Design & Test Conference, Paris, March 11-14, 1996, p.219.

40. Rohfleisch В., Kolbl Л., Wurth B. Reducing Power Dissipation after Technology Mapping by Structural Transformations // Proc. of 33rd Design Automation Conference, Las Vegas, June 9-13, 1996, p.789.

41. Glebov A., Gavrilov S., Blaauw D., ct.al. Library-Less Synthesis for Static CMOS Circuits // Intern. Conf. on Computer Aided Design, 1997.

42. Glebov A.L. BDD Based Algorithms for Series-Parallel Network Representation and Manipulation//Russian Workshop, Moscow, 1994, p.32.

43. Bryant R.E. Graph-Based Algorithms for Boolean Function Manipulation // IEEE Trans, on Computers, 1986, v.35, p.677.

44. Levi R., Blaauw D., Braca G., et.al. ClariNet: A Noise Analysis Tool for Deep Submi-cron Design // Proc. of 37th Design Automation Conference, Los Angeles, June 5-9, 2000, p.233.

45. Chen P., Keutzer K. Towards True Crosstalk Noise Analysis // Intern. Conf. on Computer Aided Design, 1999, p. 132.

46. Shepard K.L., Narayanan V., Elementary P.C., Zhen G. Global Harmony: Coupled Noise Analysis for Full-Chip RC Interconnect Networks // Intern. Conf. on Computer Aided Design, 1997, p. 139.

47. Shepard K.L. Design Methodologies for Noise in Digital Integrated Circuits // Proc. of 35th Design Automation Conference, San Francisco, June 15-19, 1998, p.94.

48. Shepard K.L., Narayanan V., Rose R. Harmony: Static Noise Analysis of Deep Submi-cron Digital Integrated Circuits// IEEE Trans, on CAD, 1999, v.18, p.1132.

49. Kirkpatrick D.A., Sangiovanni-Vincentelli A.L. Digital Sensitivity: Predicting Signal Interaction Using Functional Analysis // Intern. Conf. on Computer Aided Design, 1996, p.536.

50. Rubio A., Itazaki N., Xu X., Kinoshita K. An Approach to the Analysis and Detection of Crosstalk Faults in Digital VLSI Circuits // IEEE Trans, on CAD, 1997, v. 16.

51. Glebov A., Gavrilov S., Blaauw D., ct.al. False-Noise Analysis Using Logic Implications // Intern. Conf. on Computer Aided Design, 2001.

52. Glebov A., Gavrilov S., Zolotov V., et.al. False-Noise Analysis Using Resolution Method // Int. Symp. on Quality Electron Design, San Jose, 2002.

53. Caisso J.R, Cerny E., Rumin N.S. A Recursive Technique for Computing Delays in Series-Parallel MOS Transistor Circuits // IEEE Trans, on CAD, 1991, v. 10, n.5, p.589.

54. Tan C.H., Allen J. Minimization of Power in VLSI Circuits Using Transistor Sizing, Input Ordering, and Statistical Power Estimation // Proc. of Int. Workshop on Low Power Design, 1994, p.75.

55. Boehncr M. LOGEX An Automatic Logic Extractor from Transistor to Gate Level for CMOS Technology // Proc. of 25th Design Automation Conference, Anaheim, June 12-15, 1988, p.517.

56. Глебов А.Л. SP-BDD модель цифровых КМОП схем и ее приложения в оптимизации и моделировании // 2-я международная конференция "Микроэлектроника и информатика", Москва, 1995, с.44.

57. Глебов А.Л. SP-BDD модель цифровых КМОП схем и ее приложения в оптимизации и моделировании // Информационные технологии, 1997, №10.

58. Chandrakasan А.Р., Shcng S., Brodersen R.W. Low-Power CMOS Digital Design //IEEE Journ. of Solid-State Circuits, 1992, v.27, n.4, p.473.

59. Barzilai Z., Bccce D., Huisman L.M., et.al. SLS a Fast Switch-Lcvcl Simulator// IEEE Trans, on CAD, 1988, v.7, n.8, p.838.

60. Rao V.B., Trick T.N. Network Partitioning and Ordering for CMOS VLSI Circuits // IEEE Trans, on CAD, 1987, v.6, n.l, p. 128.

61. Li W.N., Lim A., Agrawal P., Sahni S. On the circuit implementation problem // Proc. of 29th Design Automation Conference, Anaheim, June 8-12, 1992, p.478.

62. Barth R., Monier L., Serlet B. PatchWork: Layout from schcmatic annotations // Proc. of 25th Design Automation Conference, Anaheim, June 12-15, 1988, p.250.

63. Bloom M. Parameterizablc cells strike middle ground between fixed and compiled cells // Computer Design, 1986, Nov.l, p. 24.

64. Obermcicr F.W., Katz R.H. An electrical optimizer that considers physical layout // Proc. of 25th Design Automation Conference, Anaheim, June 12-15, 1988, p.453.

65. Chen H.Y., Kang S.M. Л new circuit optimization technique for high performance CMOS circuits // IEEE Trans, on CAD, 1991, v. 10, p.670.

66. Lin S., Marek-Sadowska M., Kuh E.S. Delay and area optimization in standard-cell design // Proc. of 27th Design Automation Conference, 1990, pp.349.

67. Chan P.K. Algorithms for library-specific sizing of combinational logic // Proc. of 27th Design Automation Conference, 1990, p.353.

68. Kirkpatrick S., Gellat C.,Jr. and Vecchi M.P. Optimization by Simulated Annealing // Sciencc, 1983, v.220,p.671.

69. Strenski P.N., Kirkpatrick S. Analysis of Finite Length Annealing Schedules //Algorith-mica, 1991, v.6, p.346.

70. Hooke R., Jeeves Т.Л. Direct search solution of numerical and statistical problems // J. Assoc. Сотр. Mach., 1961, №.8, p.212.

71. Gill P.E., Murray W., Wright M.I I. Practical optimization. London: Academic Press, 1981.

72. Carlson B.S., Chen C.Y.R. Performance enhancement of CMOS VLSI circuits by transistor reordering // Proc. of 30th Design Automation Conference, Dallas, June 14-18, 1993, p.361.

73. Barth R., Serlct В., Sindhu P. Parameterized schematics // Proc. of 25th Design Automation Conference, Anaheim, June 12-15, 1988, p.243.

74. Boese K.D., Kahng A.B., Tsao C.W.A. Best-So-Far vs. Where-You-Are: New Perspectives on Simulated Annealing for CAD // Proc. of European Design Automation Conference, Hamburg, September 20-24, 1993, p.78.

75. Aluffi-Pentini F., Parisi V., Zurilli F. Global Optimization and Stochastic Differential Equations // Journ. of Optimization Theory and Applications, 1985, v.47, p. 1.

76. Sakurai Т., Newton A.R. MOSFET Model Parameter Extraction Based on Fast Simulated Diffusion // Memorandum № UCB/ERL M90/20, 16 March 1990, University of California, Berkeley.

77. Tivari V., Ashar P., Malik S. Technology Mapping for Low Power// Proc. of 30th Design Automation Conference, Dallas, June 14-18, 1993, p.74.

78. Dharchoudhury A., Kang S.M., Kim K.H., Lee S.H. Fast and Accurate Timing Simulation with Regionwisc Quadratic Models for MOS // Intern. Conf. on Computer Aided Design, 1994, p. 190.

79. Rudell R. Dynamic variable ordering for OBDD // Intern. Conf. on Computer Aided Design, 1993, p.42.

80. Meinel C., Somenzi F., Theobald T. Linear sifting of decision diagrams // Proc. of 34th Design Automation Conference, Anaheim, June 9-13, 1997, p.202.

81. Madre J.C., Billon J.P. Proving Circuit Correctness Using Formal Comparison Between Expected and Extracted Behaviour// Proc. of 25th Design Automation Conference, Anaheim, June 12-15, 1988, p.205.

82. Minato S., Ishiura N., Yajima S. Shared Binary Decision Diagram with Attributed Edges for Efficient Boolean Function Manipulation // Proc. of 27th Design Automation Conference, 1990, p.52.

83. Levy R., Blaauw D., Braca G., et.al. "ClariNet: A noise analysis tool for deep submicron design // Proc. of 37th Design Automation Conference, Los Angeles, June 5-9, 2000, p.233.

84. Brown F.M. Boolean reasoning. Boston: Kluwer Academic Publishers, 1990.

85. Ilachtel G., Jacoby R., Moceyunas P., Morrison C. Performance Enhancements in BOLD using Implications // Intern. Conf. on Computer Aided Design, 1988, p.94.

86. Kunz W., Menon P.R. Multi-Level Logic Optimization by Implication Analysis // Intern. Conf. on Computer Aided Design, 1994, p.6.

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

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

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

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

91. Garey M.R., Johnson D.S. Computers and Intractability, A Guide to the Theoiy of NP-Completeness. New York: Freeman, 1979.

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

93. Meinel C., Teobald T. Algorithms and Data Structures in VLSI Design. New York: Springer, 1998.

94. Blaauw D., Zolotov V., Sundareswaran S., et.al. Slope propagation in static timing analysis // Intern. Conf. on Computer Aided Design, 2000.

95. Brashear R.B., Menezes N., Oh C., ct.al. Predicting circuit performance using circuit-lcvel statistical timing analysis // EDAC-94.

96. Глебов АЛ. SP-BDD модель цифровых КМОП схем и ее приложения в оптимизации и моделировании // 2-я междунар. конф. "Микроэлектроника и информатика", Москва, 1995, с.44.

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

98. Glebov A., Nadezhin D. Fast delay and power estimation for digital CMOS circuits // 1st Intern. Workshop "Muli-Architecture Low Power Design", Moscow, 1999, p.3.

99. Гаврилов C.B., Глебов A.JI., Стемпковский А.Л. Быстрый алгоритм расчета мощности в цифровых КМОП схемах // Электроника НТБ, 2002, №4, с.42.

100. Глебов А.Л., Лопатников С.Ю. Новый алгоритм моделируемого отжига для оптимизации КМОП схем // Информационные технологии, 1998, №1.

101. Gavrilov S., Glebov A. BDD-bascd circuit level structural optimization for digital CMOS // 1-st Intern. Workshop "Muli-Architecture Low Power Design", Moscow, 1999, p.45.

102. Глебов А.Л., Стемпковский А.Л. Оптимизация низкомощных цифровых КМОП схем // Автоматизация проектирования, 1997, №3, c.l 1.

103. Глебов А.Л., Соловьев А.Н. Оптимизация цифровых синхронных КМОП СБИС // Информационные технологии, 2000, №2.

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

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

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

107. Стсмпковский А. Л. Отказоустойчивые архитектуры микроэлектронных вычислительных систем // Информационные технологии и вычислительные системы,2001, №2/3.

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

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

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

111. Нсмудров В.Г., Лебедев В.И., Гладков В.Н., Иванов Ю.П. Быстродействующие БИС па переключателях тока // Москва, Радио и связь, 1982.us

112. АКТ ВНЕДРЕНИЯ результатов диссертационной работы Глебова A.JI,. на соискание ученой степени доктора технических наук. Тема диссертации: "Методы анализа и оптимизации цифровых1. КМОП СБИС"

113. Разработанные автором программные средства, интегрированные в САПР сквозного проектирования.

114. При внедрении программных средств использовались, разработанные автором:

115. Методика проектирования анализа и оптимизации цифровых КМОП ИС.

116. Структура программно-аппаратных средств.

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

118. В.К.Крюков В.К.Зольников И.П.Потапов

119. Настоящий акт свидетельствует о том, что на предприятии ОАО "Ангстрем" были внедрены научные и практические результаты диссертационной работы Глебова АЛ.

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

121. Эффективность предложенных в диссертационной работе алгоритмов и моделей представления проектной информации подтверждена практическим опытом проектирования реальных микросхем.1. КМОП СБИС

122. Ученый секретарь НТС Главный специалист

123. В.М.Самохвалов А.П.Подобаевzsг1.•

124. УТВЕРЖДАЮ" Директор ИППМ РАНчл.-корр. РАН А.Л.Стемпковский2003 г.

125. АКТ ВНЕДРЕНИЯ результатов диссертационной работы Глебова А.Л. на соискание ученой степени доктора технических наук

126. Тема диссертации: "Методы анализа и оптимизации цифровых КМОП СБИС"

127. Указанный программный комплекс используется в ИППМ РАН и показал свою эффективность:- при проведении научных исследований;- при проведении учебного процесса на базовой кафедре института.

128. Зав. сектором ИППМ РАН, к.т.н.1. Ученый секретарь ИППМ РАН1. С.В.Гаврилов В.С.Борискин