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

Введение.

Глава 1. Анализ методов логического синтеза КМОП схем с применением BDDтехнологии.

1.1 Диаграммы двоичных решений и их основные свойства.

1.1.1 Основные понятия.

1.1.2 Обоснование выбора BDD-технологии.

1.1.3 Правила сокращения BDD для получения минимизированного канонического представления.

1.1.4 Выбор порядка переменных разложения.

1.1.5 Используемые обозначения.

1.2 Анализ современного состояния BDD-технологии в применении к логическому синтезу.

1.2.1 Основные принципы синтеза схем логических функций в В00-представлении

1.2.2 Соответствие BDD схемам в базисах логических элементов.

1.2.3 Соответствие BDD схемам на транзисторном уровне.

1.2.4 Разложение Шеннона и метод каскадов.

1.2.5 Использование BDD как исходного представления для синтеза схем на уровне логических элементов.

1.2.6 Основные методы декомпозиции логических функций, реализованные по BDD-представлению логических функций.

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

1.2.8 Анализ методов синтеза транзисторных КМОП схем с применением BDD-технологии

1.2.9 Основные задачи развития методов синтеза транзисторных КМОП схем с применением BDD-технологии.

1.3 Выводы по главе.

Глава 2. Разработка метода и алгоритмов декомпозиции логических функций, ориентированных на оптимизацию синтезируемых схем по быстродействию .33 2.1 Разработка метода декомпозиции логических функций, ориентированного на оптимизацию BDD-представления систем логических функций по глубине.

2.1.1 Постановка задачи.

2.1.2 Схема декомпозиции логической функции в соответствии с полным разрезом BDD.

2.1.3 Схема декомпозиции логической функции в соответствии с неполным разрезом BDD.

2.1.4 Построение декомпозиционных функций.

2.1.5 Обоснование предложенного преобразования.

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

2.2.1 Основные шаги алгоритма декомпозиции.

2.2.2 Внутреннее представление BDD.:.

2.2.3 Реализация основных операций на BDD.

2.2.4 Подпрограмма выбора разреза.

2.2.5 Алгоритм оптимизированного выбора кодирования.

2.2.6 Построение BDD для внешней функции декомпозиции.

2.2.7 Построение BDD для внутренних функций декомпозиции.

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

2.3.1 Применение базового алгоритма декомпозиции к BDD специального вида.

2.3.2 Разработка алгоритма преобразования BDD в пирамидальную структуру для схем арифметического переноса.

2.4 Выводы по главе.

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

3.1 Постановка задачи.

3.2 Абстрактная контактная схема как модель КМОП схемы.

3.2.1 Представление логических функций контактными схемами.

3.2.2 Соответствие контактных схем КМОП схемам на транзисторном уровне.

3.2.3 Определение обобщенной контактной схемы.

3.2.4 Соответствие между BDD и контактными схемами.

3.3 Исследование и формулировка принципов прямого отображения BDD в контактную схему.

3.3.1 Определение понятия слабых и сильных ребер BDD.

3.3.2 Формулировка и доказательство критериев допустимости замены контакта на проводник.

3.3.3 Формулировка и доказательство критериев допустимости замены контакта на изолятор.

3.4 Разработка алгоритма отображения BDD в контактную схему.

3.4.1 Выбор стиля синтеза и основного критерия оптимизации.

3.4.2 Краткая характеристика разработанного алгоритма'синтеза КМОП схем.

3.4.3 Внутреннее представление BDD и реализация основных операций.

3.4.4 Реализация основных операций на BDD.

3.4.5 Алгоритм построения контактной схемы, заданной размеченной BDD.

3.4.6 Алгоритм построения КМОП схемы по контактной схеме, заданной размеченной BDD.

3.5 Выводы по главе.

Глава 4. Применение разработанных алгоритмов и полученные результаты.

4.1 Проектирование структуры быстрых сумматоров с использованием алгоритмов декомпозиции.

4.1.1 Структура последовательного сумматора.

4.1.2 Преобразование BDD-модели.

4.1.3 Отображение построенной BDD-модели на КМОП схему.

4.1.4 Результаты моделирования для схем арифметических функций.

4.1.5 Структура схемы функции переноса сумматора в зависимости от выбора разреза.

4.2 Примеры применения алгоритма синтеза КМОП схем по BDD.

4.2.1 Результаты для набора тестовых функций от 3 переменных.

4.2.2 Результаты для тестов MCNC.

4.3 Выводы по главе.

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

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

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

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

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

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

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

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

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

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

В области синтеза на транзисторном уровне отечественными и зарубежными учеными создан широкий спектр методов, алгоритмов, готовых решений и эвристик, как универсальных, так и ориентированных на конкретные технологии. Можно отметить методы И.И. Шагурина для синтеза схем на биполярных транзисторах, методы А.Н. Кармазинского для синтеза схем на МОП транзисторах, реализацию метода каскадов для КМОП схем А.А. Сапоженко. Зарубежные исследователи также постоянно возвращаются к этой проблеме, в том числе в последнее время были разработаны алгоритмы синтеза КМОП схем на основе BDD-технологии. Из многих исследований в этой области, большинство из которых связано с минимизацией ДНФ и оптимизацией формул в базисе {&,v,a}, особый интерес представляет алгоритм Р. Ньютона и М. Фукуи, позволяющий строить очень компактные схемы с использованием перебора, а также недавняя работа, выполненная Ж. Риера и др. (Каталонский университет), по синтезу схем для монотонных функций с оптимизацией потребляемой мощности. Появились также алгоритмы синтеза схем на проходных транзисторах, основанные на интерпретации BDD. В общем случае задача минимизации транзисторных схем NP-полна и трудно поддается автоматизации, особенно учитывая меняющиеся условия и критерии минимизации.

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

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

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

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

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

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

1) Исследование и разработка методов декомпозиции логических функций с использованием BDD-представления.

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

3) Исследование принципов отображения BDD в контактную схему и в КМОП схему на транзисторном уровне.

4) Разработка алгоритма синтеза КМОП схем на транзисторном уровне BDD способом интерпретации BDD.

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

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

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

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

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

На защиту выносятся следующие результаты: 1) Алгоритм декомпозиции логических функций по BDD;

2) Алгоритм преобразования BDD для синтеза быстродействующих арифметических схем;

3) Способ представления транзисторных КМОП схем на базе BDD;

4) Алгоритм отображения BDD в транзисторную КМОП схему.

Реализация результатов

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

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

Разработки внедрены на следующих предприятиях: НИИМА «Прогресс»; АООТ «НИИМЭ и завод Микрон»; ИППМ РАН.

Кроме того, результаты работы были использованы в рамках международных проектов ESPRIT-BRA «LINK» (№6855, 1992-1994 гг., ведущая организация Национальный политехнический институт, Гренобль, Франция), и «MALOP» (Mapping for Low Power, INCO-KIT960058, 1996-1999 гг., ведущая организация Католический университет г. Лоувайн-ла-Нев, Бельгия).

Практическая значимость результатов работы

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

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

Основные результаты работы были доложены на московской городской конференции "Системы автоматизированного проектирования (САПР-85)" (Москва, 1985); на конференции молодых специалистов ЦООНТИ "ЭКОС" (Москва, 1986); на международных научных семинарах Russian Workshop'94 (Москва, 1994); PATMOS'97 (Лоувайн-ла-Нев, Бельгия, 1997); MALOPD'99 (Москва, 1999); на международной конференции SASIMT2000 (Киото, 2000).

Публикации

По теме диссертации автором опубликовано 11 печатных работ, из которых 4 работы были представлены на международных семинарах.

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

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

4.3 Выводы по главе

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

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

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

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

Заключение

В заключении перечислены основные результаты диссертации.

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

2) Разработан новый универсальный алгоритм декомпозиции логических функций по BDD, направленный на минимизацию глубины. Глубина представления при этом уменьшается с п до n/2+log2r+l, где г - число вершин в выбранном разрезе.

3) Разработан итеративный алгоритм декомпозиции для BDD специального вида, имеющих ограниченную ширину, позволяющий синтезировать представление функции, имеющее пирамидальную структуру. Глубина при этом уменьшается с п до log2n+l.

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

5) Разработана методика проектирования структуры быстрых сумматоров в КМОП схемотехниках, позволяющая получать структуры схем, близкие к предельным по соотношению параметров.

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

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

8) Разработан новый метод отображения BDD в оптимизированную КМОП схему без избыточных транзисторов, основанный на проведенных исследованиях. Алгоритм включает распознавание таких транзисторов непосредственно по BDD, при этом

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

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

10) Результаты использованы в реальных проектах БИС на ряде предприятий. Результаты внедрены на следующих предприятиях: НИИМА «Прогресс»; АООТ «НИИМЭ и завод Микрон»; ИППМ РАН. Кроме того, результаты работы были использованы в рамках международных проектов ESPRIT-BRA «LINK» (№6855, 1992-1994 гг., ведущая организация Национальный политехнический институт, Гренобль, Франция), и «MALOP» (Mapping for Low Power, INCO-KIT960058, 1996-1999 гг., ведущая организация Католический университет г. Лоувайн-ла-Нев, Бельгия).

1. Вартанян С.М. Новое доказательство минимальности контактной схемы, реализующей линейную функцию // Методы дискретного анализа в изучении реализаций логических функций. Вып.41. Новосибирск. - 1984.

2. Исаева Т.Ю. Корнилов А.И., Алгоритм декомпозиции логических функций, ориентированный на синтез быстродействующих цифровых устройств. // Информационные технологии. Вып. 4. - С. 26 -30 - 2001.

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

4. Корнилов А.И. и др. Устройство переноса // Свидетельство об изобретении СССР № 1608648, G 06 F 7/50. 1988.

5. Корнилов А.И. Проектирование быстродействующих арифметических устройств в универсальном логическом базисе // Техника средств связи. Сер. Микроэлектронная аппаратура,-Вып. 1-2 (12-13). М.: С. 41-47. - 1990.

6. Корнилов А.И. Универсальная ячейка базового кристалла и метод синтеза схем // Техника средств связи. Сер. Микроэлектронная аппаратура Вып. 1-2 (6-7). - С. 64-67. - 1985.

7. Корнилов А.И. Устройство переноса // Свидетельство об изобретении СССР № 1402145, G 06 F 7/50. 1986.

8. Корнилов А.И., Коренева Т.Ю. Синтез КМОП схем с ограниченной глубиной // Тезисы докладов конференции молодых специалистов. Часть II ЦООНТИ "ЭКОС". - 1986.

9. Логическое проектирование БИС/В.А. Мищенко, А.И. Аспидов, В.В. Витер и др.; Под ред. В.А. Мищенко. М.: Радио и связь. - 1984.

10. Лупанов О.Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. Вып. .10. -М.: Физматгиз, 1963. С.63-97.

11. Лупанов О.Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. М.: Физматгиз, 1960. - С.61-80.

12. Лупанов О.Б. Об одном подходе к синтезу управляющих систем принципе локального кодирования // Проблемы кибернетики. Вып. 14. - М.: Физматгиз, 1965. -С.31-110.

13. Немудров В.Г., Корнилов А.И., Исаева Т.Ю. Синтез схем на основе КМОП базовых кристаллов // Автоматизация проектирования в радиоэлектронике и вычислительной технике: Материалы семинара М. - 1987.

14. Немудров В.Г., Корнилов А.И., Коренева Т.Ю. Синтез электрических схем цифровых устройств на КМОП БК // Техника средств связи. Сер. Микроэлектронная аппаратура- 1985, вып. 1-2 (6-7).

15. Нигматуллин Р.Г. Сложность булевых функций. М., «Наука». - 1988.

16. Окольнишникова Е.А. Нижние оценки сложности реализации характеристических функций двоичных кодов бинарными программами // Методы дискретного анализа в синтезе реализаций булевых функций. Сб. научных трудов, вып.51, Новосибирск. -1991.-С. 61-83.

17. Окольнишникова Е.А. О сравнении сложностей бинарных k-программ // Дискретный анализ и исследование операций 1995. - Т.2, №4. - С. 54-73.

18. Поваров Г.Н. Метод синтеза вычислительных и управляющих контактных схем // Автоматика и телемеханика. 1957. - Т. 18, №2. - С. 145-162.

19. Редькин Н.П. О минимальной реализации двоичного сумматора // Проблемы кибернетики. Вып. 38. М.: Наука. - 1981. - С. 181-216.

20. Редькин Н.П. О реализации монотонных булевых функций контактными схемами // Проблемы кибернетики. Вып. 35. М.: Наука. - 1979. - С. 87-110.

21. Сапоженко А. А.; Ложкин С.А. Методы логического проектирования и оценки сложности схем на дополняющих МОП транзисторах. Микроэлектроника, АН СССР, т. 12, вып. 1 1983.-С. 42-47.

22. Сапоженко А.А.; Ложкин С.А. Метод каскадов для КМОП схем. Техника средств связи, Сер. Микроэлектронная аппаратура, вып. 1-2 (6-7). 1985. - С. 84-90.

23. Храпченко В.М. О сложности реализации симметрических функций формулами // Матем. заметки. 1972.-Т. 11, №1. - С.109-120.

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

25. Яблонский С. В. Функциональные построения в k-значной логике // Труды МИ АН СССР. Т.51. -М.: Изд-во АН СССР, 1958.

26. Akers, S. В. Binary Decision Diagrams // IEEE Trans. Comput., Vol. C-27, No. 6, p. 509516. 1978.

27. Ashar, P.; Cheong, M. Efficient Breadth-First Manipulation of Binary Decision Diagrams // Proc. oflCCAD. 1994.

28. Bahar, R.I. et al. Algebraic Decision Diagrams and Their Applications II Bahar, R.I.; Frohm, E.A.; Gaona, C.M.; Hachtel, G.D.; Macii, E.; Pardo, A.; Somenzi, F. Proc. of Int. Conf. On Computer-Aided Design. - 1993.

29. Berman, C.L. Ordered Binary Decision Diagrams and Circuit Structure // Proc. of ICCDVS9, pp. 392-395. 1989.

30. Bern, J.; Meinel, C.; Slobodova, A. Global Rebuilding of OBDD's Tunneling Memory Requirement Maxima // Proc. of the 32nd DAC, pp. 408-413. - 1995.

31. Bollig, В.; Lobbing, M.; Wegener, I. Simulated Annealing to Improve Variable Orderings for OBDDs // Proc. of IFIP Workshop on Logic and Architectural Synthesis, Grenoble. -1994.

32. Bollig, В.; Savicky, P.; Wegener, I. On the Improvement of Variable Orderings for OBDDs // Proc. of Int. Workshop on Computer-Aided Design & Test, Dagstuhl. 1995.

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

34. Bryant, R. E. Bit-Level Analysis of an SRT Divider Circuit // Proc. of the 33rd DAC. -1996.

35. Bryant, R. E. Graph-Based Algorithms // IEEE Trans. Comput., Vol. C-35, No. 8, pp. 677-691.- 1986.

36. Bryant, R. E. Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams // ACM Computing Surveys, Vol. 24, No 3. 1992.

37. Burgun, L. et al. Multilevel Logic Optimization of Very High Complexity Circuits // Burgun, L.; Dictus, N.; Greiner, A.; Prado Lopes, E.; Sarwary, C. ACM. - 1994.

38. Butler, R. M. et al. Heuristics to Compute Variable Orderings for Efficient Manipulation of Ordered Binary Decision Diagrams // Butler, R. M.; Ross, D. E.; Kapur, R.; Mercer, M. R. -Proc. of the 28th DAC. 1991.

39. Chang, S. С.; Marek-Sadowska, M.; Hwang Т. T. Technology Mapping for TLU FPGA's Based on Decomposition of Binary Decision Diagrams // IEEE Trans, on Computer Aided Design of Integrated Circuits and Systems, Vol. 15 No 10. 1996.

40. Chen, C. -S.; Hwang, Т. -Т.; Lin, C. L. Low-Power FPGA Design A Re-Engineering Approach // Proc. of the 34th DAC. - 1997.

41. Chen, C.-S. et al. Combining Technology Mapping and Placement for Delay-Minimization in FPGA Design. // Chen, C.-S.; Tsay, Yu-W.: Hwang, T.-T.; Lin, C. L. IEEE Trans, on CAD of Integrated Circuits and Systems, Vol. 14, No 9. - 1995.

42. Clarke, E.M. et al. Spectral Transforms for Large Boolean Functions with Application for Technology Mapping // Clarke, E.M.; McMillan, K.L.; Zhao, X.; Fujita, M.; Yang, J. Proc. of the 30th DAC. - 1993.

43. Devadas, S.; Malik, S. A Survey of Optimization Techniques Targeting Low Power VLSI Circuits. // Proc. of the 32nd DAC, 1995.

44. Drechsler, R.; Drechsler, N.; Gunther, W. Fast Exact Minimization of BDDs // Proc. of the 35th DAC.- 1998.

45. Drechsler, R.; Horeth, S. Manipulation of *BMDs // Proc. ofthe 35th DAC. 1998.

46. Fortas, A.; et al. Mapping Techniques for QuickLogic FPGA // Fortas, A.; Bouzouzou, H.; Crastes, M.; Roane, R.; Saucier, G. Proc. of SASIMT1995, pp. 184-190. - 1995.

47. Friedman, S. J.; Supowit, K. J. Finding the Optimal Variable Ordering for Binary Decision Diagrams // Proc. ofthe 24th DAC. 1987.

48. Friedman, S. J.; Supowit, K. J. Finding the Optimal Variable Ordering for Binary Decision Diagrams // IEEE Trans. Comput., Vol. C-39, No 5, pp. 710-713. 1990.

49. Fujita, M.; Chen, К. C. Network Resynthesis for Delay Minimization. // Proc. of SASIMI-92, pp. 26-35.- 1992.

50. Fujita, M.; Fujisawa, H.; Kawato, N. Evaluation and Improvements of Boolean Comparison Method Based on Binary Decision Diagrams // Proc. of ICCAD. 1988.

51. Fukui, M; Newton, A. R. Optimum Module Generation for Semi-Custom Design. Proc. ofAPCCAS'92. 1992.

52. Galans, N. et al. Advanced Ordering Manipulation Techniques for Binary Decision Diagrams // Galans, N.; Zhang, Q.; Jacobi, R.; Yernaux, В.; Trullemans, A. -M. Proc. of the European Conf. on Design Automation EDAC'92. - 1992.

53. Gavrilov, S. et al. Library-Less Synthesis for Static CMOS Combinational Logic Circuits // Gavrilov, S.; Glebov, A.; Pulella, S.; Moore, S. C.; Dharchoudhury, A.; Panda, R.; Vijayan, G.; Blaauw, D. T. Proc. ofICCAD'97. - 1997.

54. Gavrilov, S.; Glebov, A. BDD-based Circuit Level Structural Optimization for Digital CMOS. // Proc. of MALOPD'99 Workshop Moscow, Russia, September 12-13. - 1999.

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

56. Hinsberger, U.; Kolla, R. Boolean Matching for Large Libraries // Proc. of the 35th DAC. 1998.

57. Hong, Y. et al. Safe BDD Minimization Using Don't Cares // Hong, Y.; Beerel, P. A.; Burch, J.R.; McMillan, K.L. Proc. of the 34th DAC. - 1997.

58. Horeth, S. Compilation of Optimized OBDD-Algorithms // EURO-DAC'96 with EURO-VHDL'96.-1996.

59. Horeth, S.; Drechsler, R. Dynamic Minimization of Word-Level Decision Diagrams // Proc. of DATE'98. 1998.

60. Iman, S.; Pedram, M. Pose: Power Optimization and Synthesis Environment // Proc. of DAC'96. 1996.

61. Isaeva T. Y. Switch-Level BDD Based Synthesis Algorithm // Proc. of MALOPD'99 Workshop Moscow, Russia, September 12-13. - 1999.

62. Ishiura, N. Synthesis of Multi-Level Logic Circuits from Binary Decision Diagrams // Proc. of SASIMI-92, pp. 74-83. 1992.

63. Ishiura, N.; Sawada, H.; Yajima, S. Minimization of Binary Decision Diagrams Based on Exchanges of Variables // Proc. of ICC AD. 1991.

64. Ishiura, N.; Yajima, S. A Class of Logic Functions Expressible by Polynomial-Size Binary Decision Diagrams // Proc. of SASIM1-90. 1990.

65. Jacobi, R.P.; Trullemans, A.-M. ROBDD-based Logic Decomposition Techniques // Proc. of IFIP Workshop on Logic and Architecture Synthesis, Institut National Polytechnique de Grenoble, France, December 19-20. 1994.

66. Jain, J. et al. Indexed BDDs: Algorithmic Advances in Techniques to Represent and Verify Boolean Functions // Jain, J.; Bitner, J.; Abadir, M.S.; Abraham, J.A.; Fussell, D.S. IEEE Trans. On Computers, Vol. 46, No. 11. 1997.

67. Jeong, S. -W. et al. Variable Ordering for Binary Decision Diagrams // Jeong, S. -W.; Plessier, В.; Hachtel, G. D.; Somenzi, F. Proc. of the European Conf. on Design Automation EDAC'92. 1992.

68. Kebschull, U.; Schubert, E.; Rosenstiel, W. Multilevel Logic Synthesis Based on Functional Decision Diagrams // Proc. of European Design Conf., pp. 43-47. 1992.

69. Kornilov A. I., Isaeva T. Y. BDD Based Decomposition for Depth Reduction // IV International Design Automation Workshop "Russian Workshop'94": Abstracts of Papers Submitted to Russian Workshop'94 Moscow, Russia, June 28-29. - 1994.

70. Kornilov A. I., Isaeva T. Y. Circuit Depth Optimisation by BDD Based Function Decomposition // Logic and Architecture Synthesis: State-of-the-art and novel approaches -Chapman&Hall, edited by G. Saucier and A. Mignotte. 1995.

71. Kornilov A. I., Isaeva T. Y. Circuit Depth Optimization by BDD Based Function Decomposition // Proc. of IFIP Workshop on Logic and Architecture Synthesis, Institut National Polytechnique de Grenoble France, December 19-20. - 1994.

72. Kornilov A. I., Isaeva T. Y., Syngaevsky V. A. Carry Circuit Depth Optimisation by BDD Based Decomposition // Proc. of PATMOS'97 Workshop Louvain-la Neuve, Belgium, September 8-10.- 1997.

73. Kukimoto, Y.; Fujita, M.; Brayton, R. K. A Redesign Technique for Combination Circuits Based on Gate Reconnections // Proc. of ICCAD. 1994.

74. Lai, Yung-Te; Pedram, M.; Pan, R. OBDD-Based Function Decomposition: Algorithms and Implementation // IEEE Trans, on Computer Aided Design of Integrated Circuits and Systems, Vol. 15 No 8.- 1996.

75. Lai, Yung-Te; Pedram, M.; Vrudhula, S. BDD Based Decomposition of Logic Functions with Application to FPGA Synthesis // Proc. of the 30th DAC. 1993.

76. Laurent, В.; Saucier, G. Performance/Power Tradeoffs in ASIC Multipliers. // Proc. of PATMOS'97 Workshop. 1997.

77. Lavagno, L. et al. Timed Shannon Circuits: A Power-Efficient Design Style and Synthesis Tool // Lavagno, L.; McGeer, P. C.; Saldanha, A.; Sangiovanni-Vincentelli, A. L. Proc. of the 32nd DAC.- 1995.

78. Lee, C. Y. Representation of Switching Circuits by Binary-Decision Programs // Bell Syst. Tech. J., Vol. 38, pp. 985-999. 1959.

79. Lin, В.; Newton, A. R. Implicit Manipulation of Equivalence Classes Using Binary Decision Diagrams // Proc. of the European Conf. on Design Automation EDAC'92. 1992.

80. Malik, S. et al. Logic Verification Using Binary Decision Diagrams in a Logic Synthesis Environment // Malik, S.; Wang, A. R.; Brayton, R. K.; Sangiovanni-Vincentelli, A. Proc. of the ICCAD. - 1988.

81. Manne, S.; Grunwald, D.; Somenzi, F. Remembrance of Things Past: Locality and Memory in BDDs // Proc. of the 34th DAC, p. 196-201. 1997.

82. Meinel, C.; Somenzi, F.; Theobald, T. Linear Sifting of Decision Diagrams // Proc. of the 34th DAC. 1997.

83. Meinel, C.; Theobald, T. Ordered Binary Decision Diagrams and Their Significance in Computer-Aided Design of VLSI Circuits a Survey // Electronic Colloquium on Computational Complexity, report No. 39. - 1998.

84. Minato, S. Calculating of Unate Cube Set Algebra Using Zero Suppressed BDDs.

85. Minato, S. Fast Generation oflrredundant Sum-of-Products Forms from Binary Decision Diagrams // Proc. of SASIMI-92, pp. 64-73. 1992.

86. Minato, S. Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems // Proc. of the 30th DAC.- 1993.

87. Minato, S.; Ishiura, N.; Yajima, S. Shared Binary Decision Diagram with Attributed Edges for Efficient Boolean Functions Manipulation // Proc. of the 27th DAC. 1990.

88. Moller, D.; Molitor, P.; Drechsler, R. Symmetry Based Variable Ordering for ROBDDs // Proc. of IFIP Workshop on Logic and Architecture Synthesis, Institut National Polytechnique de Grenoble, France, December 19-20. 1994.

89. Moret, В. M. Decision Trees and Diagrams // Association on Computing Mash., Comput. Surv., Vol. 14, pp. 593-623. 1982.

90. Motorola H4C Series Design Reference Guide, p. 7-165.

91. Murgai, R et al. Logic Synthesis for Programmable Gate Arrays // Murgai, R.; Nishizaki, N.; Shenoy, N.; Brayton, R.K.; Sangiovanni-Vincentelli, A. Proc. of the 27th DAC. - 1990.

92. Murgai, R.; Brayton, R.K.; Sangiovanni-Vincentelli, A. Optimum Functional Decomposition Using Encoding. // Proc. of the 31st DAC. 1994.

93. Narayan, A. et al. Partitioned ROBDDs // Narayan, A.; Jain, J.; Fujita, M.; Sangiovanni-Vincentelli, A. -Proc. ofICCAD'96. 1996.

94. Panda, S.; Somenzi, F.; Plessier, B. F. Symmetry Detection and Dynamic Variable Ordering of Decision Diagrams // Proc. of ICCAD. 1994.

95. Poirot, F.; Roane, R.; Tarroux, G. Boolean Optimization Using Implicit Techniques // Proc. of IWLAS. 1994.

96. Rajgopal, S.; Tyagr, A. Dynamic Distance Based BDD Ordering // Proc. of SASIMI-92, pp. 54-63. 1992.

97. Riera, J. et al. From BDDs to CMOS Complex Gates // Riera, J.; Ribas, L.; Velasco, A. J.; Carrabina, J. Proc. of IWLAS. - 1996.

98. Riera, J. et al. Switch-Level Technology Mapping and Modeling // Riera, J.; Velasco, A. J.; Ribas, L.; Carrabina, J. Proc. of PATMOS'97 Workshop. - 1997.

99. Rudell, R. Dynamic Variable Ordering for Ordered Binary Decision Diagrams // Proc. of the Int. Conf. on Computer Aided Design, pp. 42-47. 1993.

100. Rudell, R. Tutorial: Design of a Logic Synthesis System // Proc. of the 33rd DAC. 1996.

101. Sauerhoff, M.; Wegener, I. On the Complexity of Minimizing the OBDD Size for Incompletely Specified Functions // IEEE Transactions of Computer Aided Design of Integrated Circuits and Systems. Vol. 15, No. 11, p. 1435-1437. - 1996.

102. Sawada, H.; et al. Logic Synthesis Method for Look-Up Table Applications Using Functional Decomposition and Support Minimization // Sawada, H.; Suyama, Т.; Yukishita, M.; Nagoya, A. Proc. of SASIMT95, pp. 161-168. - 1995.

103. Scholl, C. et al. Minimizing ROBDD Sizes of Incompletely Specified Boolean Functions by Exploiting Strong Symmetries // Scholl, C.; Melchior, S.; Hotz, G.; Molitor, P. Proc. Of EDAC'97

104. Scholl, C. Multi-Output Functional Decomposition with Exploitation of Don't Cares. DATE'98, 1998.

105. Singh, K. J.; Wang, A. R.; Brayton, R. K.; Sangiovanni-Vincentelli, A. Timing Optimization of Combinational Logic. // Proc. of ICCAD. 1988.

106. Somenzi, F. CUDD: CU Decision Diagram Package, ftp://vlsi.colorado.edu/pub/

107. Stanion, Т.; Sechen, C. A Method for Finding Good Ashenhurst Decomposition and Its Application to FPGA Synthesis // Proc. of the 32nd DAC, pp. 60-64. 1995.119

108. Stanion, Т.; Sechen, С. Boolean Division and Factorization Using Binary Decision Diagrams // Proc. of IEEE Asia-Pacific Conference on Circuits and Systems (APCCAS'92), pp. 190-195.- 1992.

109. Tachibana M. Heuristic Algorithms for FBDD node Minimization with Application to Pass-Transistor Logic and DCVS Synthesis // SASIMI-96, pp. 96-101. 1996.

110. Trullemans-Anckaert, A.-M. et al. A Multi-Target Design Approach for Power Critical VLSI Systems / A.-M. Trullemans-Anckaert, R. Ferreira, G. Saucier, T. Isaeva // Proc. of SASIMI-2000. -2000.

111. Tsai, M. H., Hwang, Т. Т.; Lin, Y. L. Technology Mapping for Field Programmable Gate Arrays Using Binary Decision Diagrams // Proc. of SASIMI-92, pp. 84-92. 1992.

112. Weinmann, U.; Rosenstiel, W. Network Flow Based Clustering and Partitioning for FPGAs // IFIP Workshop on Logic and Architectural Synthesis. 1994.

113. Yang, C.; Singhal, V.; Ciesielski, M. BDD Decomposition for Efficient Logic Synthesis // Proc. of ICCD'99, pp. 626-631. 1999.

114. Yang, S. et al. Space- and Time- Efficient BDD Construction via Working Set Control // Yang, S.; Chen, Y.-A.; Bryant, R.E.; O'Hallaron, D.R. Proc. of ASP-DAC'98, pp. 433-446. - 1998.

115. Ye, Y.; Roy, K. A Graph-Based Synthesis Algorithm for AND/XOR Networks // Proc. of the 34th DAC. 1997.

116. Zhong, P. et al. Using Reconfigurable Computing Techniques to Accelerate Problems in the CAD Domain: A Case Study with Boolean Satisfiability // Zhong, P.; Ashar, P; Malik, S.; Martonosi, M. Proc. of the 35th DAC. - 1998.

117. Zhou, H.; Wong, D.F. Exact Gate Decomposition for Low-Power Technology Mapping. // Proc. of the 34th DAC. 1997.120