Содержание к диссертации
Введение
Глава 1. Анализ и оптимизация цифровых КМОП схем 11
1.1. Методы расчета мощности в цифровых КМОП схемах 13
1.2. Параметрическая оптимизация 15
1.3. Структурная оптимизация 18
1.4. Анализ помехоустойчивости цифровых схем 21
1.5. Выводы ..24
Глава 2. Последовательно-параллельные диаграммы двоичных решений (SP-BDD) 26
2.1. Определения и основные свойства 27
2.2. Основные операции на SP-BDD 34
2.3. SP-BDD и КМОП-схсмы 40
2.4. Выводы 55
Глава 3. Методы ключевого моделирования, расчета мощности и задержек цифровых КМОП схем 57
3.1. Оценка мощности, потребляемой КМОП схемой 60
3.2. Последовательность процедур моделирования 65
3.3. Ключевое моделирование с использованием SP-BDD 69
3.4. Алгоритм расчета задержек с использованием SP-BDD 72
3.5. Расчет энергии сквозных токов 76
3.6. Быстрая вероятностная модель мощности 77
3.7. Экспериментальные результаты 81
3.8. Выводы 82
Глава 4. Параметрическая оптимизация цифровых КМОП схем 83
4.1. Оптимизация схем, спроектированных на базе параметризованных ячеек 85
4.2. Использование метода моделируемого отжига при параметрической оптимизации 90
4.3. Выводы 96
Глава 5. Структурная оптимизация цифровых КМОП схем 91
5.1. Обзор метода ресинтеза 99
5.2. Глобальный ресинтез 103
5.3. Локальный ресинтез 103
5.4. Пространство состояний в локальном ресиптезс 109
5.5. Выводы 113
Глава 6. Анализ и оптимизация цифровых КМОП схем па проходных транзисторах 115
6.1. КМОП схемы на проходных транзисторах и модель задержек для них 115
6.2. Модель мощности для цифровых КМОП схем на проходных транзисторах. 124
6.3. Параметрическая оптимизация цифровых КМОП схем на проходных транзисторах 130
6.4. Структурная оптимизация цифровых КМОП схем на проходных транзисторах 147
6.5. Выводы 161
Глава 7. Анализ помехоустойчивости цифровых КМОП схем 163
7.1. Методы определения логических корреляций между сигналами цифровой схемы 164
7.2. Методы анализа помех в цифровой схеме па основе корреляций между сигналами 196
7.3. Анализ помехоустойчивости цифровой схемы на основе результатов временного анализа 199
7.4. Выводы 224
Глава 8. Характеристика программного обеспечения и экспериментальные результаты 226
8.1. Характеристика программного обеспечения, реализующего структурную и параметрическую оптимизацию цифровых КМОП схем 226
8.2. Экспериментальные результаты по параметрической оптимизации цифровых КМОП схем 228
8.3. Экспериментальные результаты по структурпой оптимизации цифровых КМОП схем 232
8.4. Выводы 236
Заключение 237
Литература 240
- Анализ помехоустойчивости цифровых схем
- Основные операции на SP-BDD
- Ключевое моделирование с использованием SP-BDD
- Использование метода моделируемого отжига при параметрической оптимизации
Введение к работе
Уровень развития математического обеспечения во многом определяет функциональные возможности САПР СБИС и, в первую очередь, сдерживает темпы их развития. Это особенно отчетливо проявляется при применении современных САПР в разработках субмикроиных СБИС. Возможности практического проектирования в этом случае отстают от технологических возможностей изготовления, т.е. наблюдается так называемый кризис проектирования. Состояние вычислительных методов анализа и оптимизации КМОП СБИС является доминирующей составляющей в процессе такого отставания. Ввиду возрастания роли межсоединений в субмикронных СБИС, особую важность здесь представляют методы анализа помехоустойчивости цифровых схем.
История развития большей части указанных методов насчитывает не один десяток лет. Следует отметить, что как в нашей стране, так и за рубежом получен значительный ряд результатов в области логического синтеза и оптимизации цифровых схем. Самостоятельное направление составили исследования по синтезу схем на транзисторном уровне, связанные с известными работами Глориозова Е.Л. [110], ШагурииаИ.И. [111], Кармазинского А.Н. [П2],Немудрова В.Г. [113]. Несмотря на значительный прогресс в этой области, существует потребность в новых и более эффективных методах и алгоритмах анализа и оптимизации. К факторам, порождающим такую потребность можно отнести:
- постоянное снижение размеров элементов (транзисторов, межсоединений), а также рост числа элементов на кристалле;
- необходимость проектирования схем с низкой потребляемой мощностью;
- возрастающее разнообразие стилей проектирования, которые используются или могут быть использованы при разработке СБИС.
Для удовлетворения указанных потребностей необходимо создать новое поколение методов анализа и оптимизации цифровых КМОП схем, включая анализ мощности и помехоустойчивости, обладающих значительно более высокими производительностью и качеством результатов по сравнению с существовавшими ранее. Для создания таких методов необходима новая математическая модель цифровых КМОП схем. Базой этой модели могут стать BDD (binary decision diagrams, или диаграммы двоичных решений)» ранее успешно использовавшиеся для представления булевских функций в логическом синтезе. На решение указанных задач нацелена настоящая диссертация.
Цель работы: разработка теоретических основ специализированного BDD-представления для построения новой модели и нового поколения высокопроизводительных и эффективных методов анализа и оптимизации цифровых КМОП схем, обеспечивающих радикальное ускорение и повышение качества их проектирования.
Основные задачи работы:
• Разработка и исследование новой математической модели цифровых КМОП схем, сохраняющей детальность описания схемы на транзисторном уровне, однако позволяющей гораздо быстрее и эффективнее выполнять вычислительные операции. Разработка базовых методов и алгоритмов работы с моделью.
• Разработка и исследование оперативных методов расчета мощности и быстродействия цифровых КМОП схем иа основе указанной модели, обладающих достаточной точностью и пригодных для использования внутри оптимизационного цикла.
• Разработка и исследование эффективных методов параметрической оптимизации цифровых КМОП схем по критериям мощности, быстродействия и площади, описанных как на уровне транзисторов, так и на уровне параметризованных ячеек.
• Разработка и исследование эффективных методов структурной оптимизации цифровых КМОП схем по указанным критериям при наличии различных ограничений, с использованием вышеуказанных математической модели КМОП схем и быстрых методов расчета мощности и быстродействия.
• Обобщение вышеуказанных методов анализа и оптимизации цифровых КМОП схем иа различные стили проектирования, в частности, на схемы на проходных транзисторах.
• Разработка и исследование логико-временных методов анализа устойчивости цифровых КМОП схем по отношению к помехам, возникающим за счет емкостных связей межсоединений.
• Экспериментальная проверка предложенных методов. Методы исследования, При решении поставленных задач использованы методы теории множеств, теории графов, оптимизации, ключевого моделирования и временного анализа КМОП схем.
Научная новизна:
• Предложена оригинальная теоретико-графовая модель цифровых КМОП схем, основанная на впервые введенных BDD (диаграммах двоичных решений) специального вида (SP-BDD). Разработана теория SP-BDD, включающая набор базовых методов и алгоритмов работы с этими объектами. Данная модель позволяет эффективно производить вычислительные операции для КМОП вентилей в рамках различных алгоритмов,
• Предложены методы ключевого моделирования цифровых КМОП схем, а также оперативного расчета мощности и задержек, основанные на использовании SP-BDD модели, обладающие точностью транзисторного уровня описания схемы и пригодные для использования внутри оптимизационных циклов.
• Предложен новый метод параметрической оптимизации цифровых КМОП схем на транзисторном уровне, основанный на использовании нестандартной процедуры моделируемого отжига с осциллирующим температурным планом. Данный метод может быть применен также к другим оптимизационным задачам, например, в оптимизации цифровых схем, спроектированных на основе библиотеки параметризованных ячеек.
• Разработан новый метод структурной оптимизации (ресинтеза) цифровых КМОП схем, основанный на использовании SP-BDD модели. На каждом шаге выполнения ресинтеза, схема описана детально на транзисторном уровне. Показано, что пространство сотояний схемы при ресинтезс по своим размерам типично для этапа логического синтеза. Теоретически обоснованы и экспериментально подтверждены качество результатов и быстродействие метода ресинтеза.
• Предложены методы оперативного расчета мощности и задержек, параметрической и структурной оптимизации для различных типов цифровых КМОП схем на проходных транзисторах,
• Разработаны новые методы логического и логико-временного анализа помехоустойчивости цифровых схем. Методы включают в себя оригинальные быстрые алгоритмы вычисления логических корреляций между сигналами в цифровой схеме (логических импликаций). Предложены обобщения метода логических импликаций на случай учета задержек распространения сигналов, а также на случай использования импликаций в сочетании с результатами статического временного анализа. Экспериментально доказана высокая эффективность разработанных методов.
Защищаемые в работе положения;
• ІІовая теоретико-графовая модель цифровых КМОП схем, основанная на впервые введенных DDD (диаграммах двоичных решений) специального вида (SP-BDD). Модель содержит детальную информацию о КМОП схеме на транзисторном уровне, одновременно описывая также логическую функцию схемы. Модель обеспечивает эффективность выполнения вычислительных операций в рамках различных алгоритмов.
• Новые методы ключевого моделирования цифровых КМОП схем, оперативного расчета мощности и задержек. Методы основаны па использовании SP-DDD модели, имеют точность транзисторного уровня описания схемы и пригодны для использования внутри оптимизационных циклов.
• Оригинальный метод параметрической оптимизации цифровых КМОП схем на транзисторном уровне, основанный па впервые введенной нестандартной процедуре моделируемого отжига с осциллирующим температурным планом. Метод может быть применен также к другим оптимизационным задачам.
• Новый метод структурной оптимизации (ресинтеза) цифровых КМОП схем, основанный на использовании SP-BDD модели. В данном методе на каждом шаге оптимизационной процедуры используется как детальное описание схемы на транзисторном уровне, так и описание се логической функции. Метод позволяет значительно улучшить параметры схемы, предварительно синтезированной и оптимизированной лучшими из известных программ логического синтеза.
• Оригинальные методы оперативного расчета мощности и задержек, параметрической и структурной оптимизации для различных типов цифровых КМОП схем на проходных транзисторах. Методы позволяют использовать указанные перспективные стили проектирования при разработке цифровых КМОП СБИС.
• Новые методы логического и логико-временного анализа помехоустойчивости цифровых схем. Методы включают в себя впервые предложенные быстрые алгоритмы вычисления логических корреляций между сигналами в цифровой схеме (логических импликаций). Обобщение метода, использующего логические импликации, па случай учета задержек распространения сигналов (внутри импликаций), а также па случай использования импликаций в сочетании с результатами статического временного анализа.
Практическая ценность. Результаты ВЬІГЮЛЕІЄННЬІХ исследований позволяют значительно повысить эффективность и качество проектирования цифровых КМОП СБИС, особенно СБИС с низкой потребляемой мощностью. Во первых, за счет применения эффективных методов ключевого моделирования, оперативного расчета мощности и задержек, параметрической и структурной оптимизации достигается возможность более качественного проектирования на этапе разработки электрической схемы.
Во вторых, за счет использования методов расчета мощности и задержек, параметрической и структурной оптимизации для цифровых КМОП схем на проходных транзисторах достигается возможность использования большего разнообразия перспективных стилей проектирования при разработке СБИС.
И, наконец, применение разработанных методов анализа помех в цифровых схемах даст возможность повысить помехоустойчивость проектируемых СБИС.
Таким образом, практическая ценность предлагаемых методов состоит в том, что они, по сравнению с известными, предоставляют возможности более качественного и эффективного проектирования цифровых СБИС.
Реализация научно-технических результатов работы. Результаты диссертации нашли практическое применение при проектировании ряда микросхем, блоков и элементов цифровых СБИС на предприятиях ОАО "НИИМЭ и Микрон 1, ОАО "Ангстрем", а также на Федеральном государственном унитарном предприятии НИИ электронной техники.
Апробация работы. Результаты диссертации докладывались и обсуждались на 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 страницах, включая рисунки, графики и таблицы.
В первой главе в целях обоснования и уточнения направлений исследования рассмотрено состояние проблем и дан обзор методов и алгоритмов анализа и оптимизации цифровых КМОП схем. В целях создания общей математической основы разрабатываемых методов анализа и оптимизации во второй главе диссертации сформулирована новая тсорстико-графовая модель цифровых КМОП схем, а также базовые методы и алгоритмы для работы с этой моделью. В третьей главе диссертации разработаны методы ключевого моделирования, оперативного расчета мощности и задержек для цифровых КМОП схем. В четвёртой главе диссертации проработаны методы параметрической оптимизации цифровых КМОП схем. Пятая глава диссертации посвящена структурной оптимизации цифровых КМОП схем. В шестой главе диссертации рассмотрены анализ и оптимизация цифровых КМОП схем па проходных транзисторах. В седьмой главе диссертации рассмотрены методы анализа помехоустойчивости цифровых схем, использование которых становится все более актуальным при проектировании СБИС. Восьмая глава посвящена характеристикам разработанного программного обеспечения, а также экспериментальным результатам. В заключении перечислены основные результаты работы.
Анализ помехоустойчивости цифровых схем
Успехи в развитии технологии СБИС привели к значительному уменьшению размеров элементов и, как следствие, к сильному росту емкостей связи межсоединений. Становится обычным, что 60-80% от полной емкости межсоединения составляют емкости связи с другими межсоединениями. Эта тенденция приводит к увеличению помех, индуцированных в цепи из-за нежелательных переключений соседних цепей, что приводит к необходимости разработки алгоритмов и программ анализа помехоустойчивости [44-48]. При анализе помех в цифровых схемах узел схемы, в котором рассматривается помеха, обычно называют узлом-жертвой, тогда как соседние узлы, индуцирующие помеху, называют узлами-агрессорами. Узел-жертву вместе со связанными с ним узлами-агрессорами будем называть кластером. Говорят, что имеет место фунщиональиая помеха, если узел-жертва находится в стационарном состоянии, тогда как узлы-агрессоры переключаются, индуцируя в узле-жертве импульс помехи, который может привести к логически неправильной работе схемы. Говорят, что имеет место помеха задержки, если узел-жертва переключается одновременно с узлами-агрессорами, что увеличивает или уменьшает задержку переключения узла-жертвы и может привести к нарушению требований к быстродействию схемы.
Алгоритмы и программы анализа помехоустойчивости обычно предполагают, что все узлы-агрессоры в кластере переключаются одновременно и в одном направлении [44,46,47]. При этом предположении помехи, индуцированные каждым из агрессоров, складываются, что приводит к максимально возможному составному импульсу помехи и чрезмерно консервативному анализу (т.е. слишком пессимистической оценке величины помехи). На практике, однако, временные и логические ограничения, имеющиеся в схеме, могут накладывать запрет на одновременное переключение всех агрессоров в одном направлении. Следовательно, помеха, являющаяся результатом анализа, не учитывающего временных и логических корреляций, может быть сильно переоценена, что приводит к так называемой ложной фатальной помехе. Это особенно пажно в случаях, когда кластер содержит большое количество агрессоров (10 и более), что часто имеет место на практике. В этой ситуации величина помехи, получаемая при консервативном подходе, будет крайне велика, тогда как реализация сценария одновременного переключения агрессоров очень маловероятна ввиду присущих схеме временных и логических корреляций.
Промышленные программы анализа помехоустойчивости используют временные корреляции между сигналами, существу to щие в схеме, для уменьшения пессимизма оценки максимальной помехи посредством идентификации ситуаций, когда два узла-агрессора не могут переключаться одновременно. Простейшими примерами таких ситуаций являются случаи, когда два узла-агрессора переключаются в различных тактовых периодах или когда один агрессор переключается в ранней части, а другой - в поздней части одного и того же тактового периода. Для определения того, когда узел может переключаться, так называемые окна переключения распространяются по схеме с использованием статического временного анализа [44-46]. После того, как окна переключения найдены для каждого агрессора, определяется возможность наложения окон для набора агрессоров. Важно подчеркігуть, что данный подход по своей природе локален, что означает идентификацию окон переключения по отдельности для каждого узла-агрессора, поэтому такой вид анализа весьма эффективен. Однако отсюда следуют также и слабые стороны данного подхода, заключающиеся в том, что не идентифицируются ситуации, в которых, например, каждый из двух узлов-агрессоров по отдельности может переключаться в некоторый момент времени, однако совместное их переключение в этот момент времени невозможно из-за логических корреляций между сигналами в схеме. Простой пример такой ситуации показан на Рис, 1.3. Подход, использующий окна переключения (временные окна), не обнаруживает также ситуации, когда узлы не могут переключаться одновременно в одном направлении, например являясь соединенными через инвертор. Следовательно, этот подход не обнаруживает все ложные фатальные помехи, хотя он и показал себя на практике относительно эффективным [44].
Основные операции на SP-BDD
В первую очередь мы рассмотрим операцию изменения порядка переменных в SP-BDD, после которого она все еще остается SP-BDD. Некоторые из таких переупорядочений соответствуют изменениям в линейном порядке без изменения электрической схемы. Другие переупорядочения меняют электрическую схему ПП-цепи. Однако в обоих случаях булевская функция, ассоциированная с ПП-цепыо, остается неизменной. Чтобы рассмотреть пространство возможных переупорядочений, мы должны дать некоторые новые определения. Определение 6. Интервал SP-BDD - это множество вершин SP-BDD с индексами, идущими подряд. Для заданной ПП-цепи и ассоциированной с ней SP-BDD, некоторые интервалы SP-BDD соответствуют ПП-цспям, другие - не соответствуют. Здесь и далее, говоря о последовательном или параллельном соединении интервалов SP-BDD, мы будем иметь в виду результат шага В или С процедуры формирования SP-BDD, описанной в предыдущем разделе. Определение 7. ПП-фрагмепт - это интервал SP-BDD, который является либо одиночной вершиной SP-BDD, либо последовательным соединением двух или более ПП-фрагментов, к которому ничего более не присоединено последовательно, либо параллельным соединением двух или более ПП-фрагментов, к которому ничего более не присоединено параллельно. В примере, показанном на Рис.2.4, список всех ПП-фрагмситов таков: элементарные фрагменты (т.е. состоящие из одиночных вершин), (а,Ь,с) и вся SP-BDD (без терминальных вершин). (а,Ь) и (d,e) не являются ПП-фрагментами. Рис.2.4. Простой пример ПП-цспи (а) и соответствующей SP-BDD (о). Определение 8. ПП-цепочка - это последовательность двух или более ПП-фрагментов, соединенных последовательно или параллельно и вместе в свою очередь образующих ПП-фрагмент. Очевидно, что ПП-фрагмент и ПП-цсгточка являются объектами, которые могут быть связаны как с SP-BDD, так и с ПП-цепью. Произвольная SP-BDD (ПП-цепь), содержащая более чем одну вершину (ключ), представляет собой иерархию ПП-пепочек. Например, SP-BDD на Рис.2.4 содержит две ПП-цепочки: ((a,b,c),(d),(e)) - 1-й (верхний) уровень иерархии, ((a),(b),(c)) - 2-й уровень иерархии.
Очевидно, что количество ПП-цепочек в SP-BDD равняется количеству ПП-фрагмептов длиной более единицы (длина = количество вершин). Для каждой ПП-цспочки рассмотрим все возможные перестановки составляющих ее ПП-фрагмептов. Легко показать, что перестановки, совершаемые в любых двух различных ПП-цепочках, коммутируют. Следовательно, пространство возможных переупорядочений SP-BDD является декартовым произведением под пространств перестановок для каждой ПП-цспочки. Перестановки ПП-фрагмснтов, соединенных параллельно, изменяют линейный порядок ключей в ПП-цепи, не меняя ее электрической схемы. Перестановки ПП-фрагмснтов, соединенных последовательно, изменяют электрическую схему ПП-цепи без изменения ее булевской функции. Произвольное переупорядочение SP-BDD может быть выполнено как композиция элементарных переупорядочений (ПП-перестаповок), каждая из которых меняет местами два соседних ПП-фрагмента.
Для реализации переупорядочений SP-BDD мы вводим в структуру данных, описывающую каждую вершину v SP-BDD, рассматриваемую как первую вершину второго из переставляемых ПП-фрагментов, следующие поля: v.changc_tag - тип соединения ПП-фрагмснтов (1 - последовательное, 2 - параллельное), v.change_start - указатель на первую вершину первого ПП-фрагмепта, v.change_end - указатель на вершину, следующую за последней вершиной второго ПП-фрагмснта. Эти перестановочные поля вычисляются при формировании SP-BDD и затем поддерживаются при выполнении всех основных операций, выполняемых на SP-BDD. 2.2.2, Слияние Предположим, что мы имеем ПП-фупкцшо f, и один из ее аргументов х является в свою очередь ПП-функцией h некоторого другого множества переменных. (Мы предполагаем здесь, что множества аргументов сужения 1х=Ь и функции h не пересекаются для любого значения булевской константы Ь.) Предположим, что заданы SP-BDD Gf, G для функций f и h, и мы хотим построить SP-BDD G для их композиции f[x=h . Эта операция соответствует слиянию двух ПП-цепей F и II, где Н управляет ключом х из F, в единую ПП-цсиь. G будет построена следующим образом. Пусть v - вершина Gf , соответствующая переменной х. G будет содержать все вершины из Gf кроме v, а также нее нетерминальные вершины Gh, со следующими изменениями нх атрибутов: - каждая вершина из Gf, которая имела v своим 0-нотомком (1-потомком), будет иметь своим 0-потомком (1-потомком) бывший корень Gf,; - каждая вершина из Gh имевшая t0 своим 0-потомком, будет иметь своим 0-потомком low(v); - каждая вершина из Gh имевшая tj своим 1-потомком, будет иметь своим 1-иотомком high(v); - все нетерминальные вершины G имеют индексы в соответствии с линейным порядком, образованным из линейных порядков на Gf и Gj, следующим образом: сначала идут вершины из Gf, которые предшествовали v, затем идут вершины из Gj,, в конце идут вершины из Gf, которые шли после V. Если v не являлась корнем Gf, то бывший корень Gf будет корнем G, в противном случае бывший корень Gf, будет корнем G. 2.2.3. Декомпозиция Декомпозиция - это операция, обратная слиянию. Предположим, что нам нужно представить ПП-фупкцию с заданной SP-BDD G в виде композиции 11х=(, двух ПП-функций f и h, представленными как SP-BDD Gf и G . Это соответствует декомпозиции заданной ПП-цспи на две ПП-цспи F и Н, причем II управляет ключом из F. Для того, чтобы произвести декомпозицию, мы должны выбрать некоторый интервал I из G, содержащий последовательное или параллельное соединение ПП-фрагментов из одной и той же ПП-цепочки. После этого SP-BDD Gf и Gfo формируются следующим образом. Пусть Wj , w2 - первая и последняя вершина интервала I. G будет содержать две терминальные вершины t0 и tj , а также все вершины из I со следующими изменениями в их атрибутах
Ключевое моделирование с использованием SP-BDD
Во второй главе было описано новое и эффективное представление для статических КМОП схем - SP-BDD (см. также [38]). Там же приведены алгоритмы экстракции SP-BDD и основных процедур для работы с ними. В настоящем разделе мы покажем, как алгоритм ключевого моделирования из предыдущего раздела (ориентированный на вычисление мощности) может быть преобразован в более эффективную форму с использованием представления КМОП схем в виде SP-BDD.
Каждому стандартному КМОП вентилю в нашем представлении схемы соответствует SP-BDD (вентильная BDD). Вершина вентильной BDD описывается следующей структурой данных (следует обратить внимание па наличие некоторых дополнительных полей, необходимых для работы алгоритма ключевого моделирования).
Как уже указывалось выше, главным содержанием ключевого моделирования является разбиение всех узлов вентиля (после каждого переключения схемы) па узлы подграфа А (графа схемы), узлы подграфа С и узлы CS-грунп. После этого новые потеїгциальї всех узлов могут быть легко вычислены по их старым потенциалам.
Каждая вершина вентильной BDD соответствует паре транзисторов (один в верхней и один в нижней цепи) с объединенными контактами затворов, образующими вход вентиля. Кроме того, каждая вершина за исключением корневой соответствует внутреннему узлу верхней пепи (если вершина является 1-потомком другой вершины) или нижней цепи (если это 0 потомок). Выходной узел вентиля пс имеет соответствующей вершины в вентильной BDD.
Мы опишем здесь алгоритм, который разбивает вершины вентильной BDD (и, следовательно, соответствующие узлы схемы), а также и выходной узел, на pU-грунпы (верхние группы) и pD-групны (нижние группы). Эта процедура находится в следующем соответствии с разбиением графа схемы на подграфы и CS-группы:
Л. Все внутренние узлы верхней цепи с pU_group=l относятся к подграфу А. Все внутренние узлы верхней цени с pU__group=out_pU_group относятся к подграфу С. Все остальные внутренние узлы верхней цепи, имеющие одинаковое значение параметра pU_group, относятся к одной и той же CS-групие. B. То же справедливо для внутренних узлов нижней цепи, если произвести следующие замены: pU_group - pD_group, out_pU_group - out_pD_group, подграфы Л - С.
C. Выходной узел относится к подграфу Л, если out_pU_group=l, в противном случае он относится к подграфу С.
Алгоритм использует только один линейный обход вентильной BDD и работает намного быстрее, чем алгоритм, описанный в предыдущем разделе (предполагая, что предварительно произведена экстракция SP-BDD представления КМОП схемы). Алгоритм описывается следующим псевдокодом. (Все параметры pU_group, pD_group прошшциализированы нулем.)
Расчет задержек КМОП вентилей является важнейшей составной частью алгоритма ключевого моделирования, ориентированного на расчет мощности. В данном разделе мы рассмотрим такой алгоритм, использующий SP-BDD представление КМОП схемы. Для оценки задержек КМОП вентиля мы используем Элморовскую модель задержки [53].
Пусть имеется транзисторная ПП-иепь (верхняя цепь статического КМОП вентиля). Один из се терминалов имеет потенциал Vdd (исток), другой терминал перед началом переключения имеет нулевой потенциал (выход). Первоначально ПП-цепь находится в непроводящем состоянии. Допустим, что некоторый транзистор х переключается в проводящее состояние, и это приводит к переключению ПП-цепи в проводящее состояние.
Будем использовать следующие обозначения. Пусть транзистор к присоединен к узлам М и N (контактами истока и стока). Пусть в ПП-испи существует нссамопсрссекающийся путь от узла истока к узлу выхода, проходящий через х, причем М предшествует N. В этом случае будем говорить, что х верхне-нрисоедипеп к М и нижне-присосдинен к N.
Для оценки задержки переключения узла выхода будем использовать задержку Элмора для наихудшего случая, даваемую формулой: где Rx = mflfjfj ,(Vr;) - максимальное предшествующее сопротивление, rt сопротивление проводящего і-го транзистора, {Р} - множество путей от узла истока к транзистору х, гх - сопротивление проводящего транзистора х, N(x) -узел, к которому транзистор х пижпе-присоединеи, - RC-сумма для узла N(x), {Q} - множество путей от узла N(x) к узлу выхода, Сх - емкость дерева для транзистора х, т.е. максимальная емкость, перезаряжаемая при переключении транзистора х в проводящее состояние (то же для CJ). (Здесь и далее путь в ПП-цепи - это подпуть полного пути. Полный путь - это несамопересекающийся путь от узла истока к узлу выхода.) 11а первый взгляд можно предположить, что емкость дерева Сх зависит от проводящего пути Р. Паш алгоритм, однако, основан на следующем утверждении.
Использование метода моделируемого отжига при параметрической оптимизации
При параметрической оптимизации КМОП схем, в том числе при оптимизации мощности, мы имеем дело со следующей проблемой. Найти минимум целевой функции F(x) посредством выбора оптимального вектора размеров х = (Х, ..,, хп), где Wj = axj + b - ширина j-го транзистора, минимальный размер b и шаг а могут зависеть от тина транзистора (п или р), все X: - неотрицательные целые числа. Целевую функцию определим следующим образом: где: D(x) - разность между действительной и максимальной допустимой задержкой, если она положительна, и 0 если отрицательна, Р(х) - мощность, площадь или их комбинация, С - очень большое число ("бесконечность"). Возможно также наличие некоторых других ограничений. Мы опробовали несколько различных алгоритмов для решения данной оптимизационной задачи и нашли метод моделируемого отжига наиболее надежным. Каждый шаг отжига состоит в случайном выборе одного транзистора из множества и изменении его размера Xj в большую или меньшую сторону. Если нарушаются какие либо ограничения, то данное изменение отклоняется, в противном случае оно либо принимается либо отклоняется с вероятностью, зависящей от изменения целевой функции и значения температуры на текущем шаге. В первоначальной (обычной) версии метода вероятность на шаге І отжига равна 1 при F; Fj. (Fj - значение целевой функции па і-м шаге), а в противном случае - пропорциональна cxpHFj-Fj.O/Tj), ТгоТи, Т0 0, 0 сс 1
Указанный традиционный температурный план с монотонным охлаждением базируется па аналогии со статистической механикой и минимизирует математическое ожидание значения целевой функции для текущего состояния системы после очередного шага (WYA-COCTOHHUC, "Where-You-Are"). Mo в действительности мы всегда используем лучшее из состояний, пройденных системой в процессе отжига (BSF-состоянис, "Best-So-Far"). Таким образом, следует согласиться с [74] в том, что обычные обоснования плана монотонного охлаждения не вполне корректны.
В соответствии с подходом, предложенном в [74] (моделирование цепей Маркова), были найдены оптимальные BSF-плаиы отжига (т. с. планы, минимизирующие математическое ожидание BSF-цсш.г, где под BSF-нсной понимается значение целевой функции для BSF-еостояния) для некоторых простых задач оптимизации, и установлено следующее: реально вычислить оптимальный BSF-план возможно лишь для очень простых схем (состоящих из нескольких транзисторов); все оптимальные BSF-планы отличны друг от друга и от монотонного. Поскольку мы заранее не знаем структуру минимумов целевой функции для каждой конкретной схемы, то необходим план, приводящий к процедуре отжига, эффективной и надежной для любой схемы (включая наихудший случай). В настоящей главе построен пример системы, подобной системе из сформулированной выше задачи параметрической оптимизации, для которой оптимальным В SF-планом является осциллирующий план. После этого приведены некоторые аргументы в пользу осциллирующего плана для задачи параметрической оптимизации. Пусть состояние системы описывается вектором х=(х!,...,хп), где Xj пробегает все целые значения. Целевая функция задается формулой: Рассмотрим процедуру моделируемого отжига для данной системы с начальным состоянием х =(0,...,0) и длиной lm шагов. Очевидно, что математическое ожидание цены для оптимального плана с числом единичных шагов меньшим, чем lm, равно нулю (при этом оптимальный BSF-плап - просто любой план, а оптимальным WYA-mianoM является, например, план с нулевой температурой). Если длина (т.е. число шагов) отжига равна lm, то математическое ожидание цены для оптимального плана (как BSF, так и WYA) меньше 0 из-за состояния со значением целевой функции -1. Единственная траектория от начального состояния до данного есть где P(xJ/xJ" ) есть вероятность состояния xJ после j шагов при условии, что система находилась в состоянии х-1 1 послеj-1 шагов. Тогда для TJ справедливо следующее: Таким образом, для рассматриваемой системы имеем оптимальный план отжига (как BSF, так и WYA), показанный на рис. 4.1.
Данный пример иллюстрирует ситуацию, при которой множество состояний системы состоит из областей примерно одинакового размера и с примерно одинаковой высотой границ (высота = значение целевой функции), причем внутри каждой области имеется локальный минимум целевой функции. При этом лучший план должен максимизировать число посещенных областей (за предписанное число шагов). Это и будет осциллирующий план, подобный описанному выше, где интервалы с нулевой температурой необходимы для приближения к локальному минимуму, а с бесконечно большой - для наиболее вероятного преодоления барьера на границе и достижения соседней области локального минимума.
