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

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

Кононов Николай Александрович

Структурная оптимизация и обфускация комбинационных цифровых схем в базисе ПЛИС/СБМК

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва2011 " З НОЯ 2011

4858398

4858398

Работа выполнена в Национальном исследовательском университете «МИЭТ» на кафедре проектирования и конструирования интегральных микросхем.

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

доктор технических наук Беспалов В.А.

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

доктор технических наук Гаврилов C.B. кандидат технических наук Машевич П.Р.

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

ФГУП ФНПЦ «Научно исследовательский институт измерительных систем им. Ю.Е. Седакова»

Защита диссертации состоится 29 ноября 2011 года в 14 часов 30 минут на заседании диссертационного совета Д212.134.01 при Национальном Исследовательском Университете «МИЭТ» по адресу: 124498, Москва, г.Зеленоград, проезд 4806, д.5 С диссертацией можно ознакомиться в библиотеке Национального исследовательского университета «МИЭТ». Автореферат разослан « 13 » 2011г.

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

д.т.н., профессор

/Т.Ю. Крупкина/

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

Актуальность работы

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

Для обеспечения паритетных возможностей российскими разработчиками аппаратуры в качестве элементной базы используются полузаказные СБИС с программируемой логикой — ПЛИС/СБМК (FPGA/structured ASIC). Несмотря на то, что ПЛИС уступают заказным схемам по быстродействию в 3-5 раз, а по расходу кремния в 7-10 раз, они очень популярны, поскольку позволяют в несколько раз сократить сроки разработки и повысить качество проектирования.

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

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

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

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

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

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

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

- разработка и программная реализация методов и алгоритмов оптимизации универсального логического модуля (УЛМ) ПЛИС и СБМК;

- разработка и программная реализация методов и алгоритмов оптимального отображения больших комбинационных схем в логический базис ПЛИС и СБМК;

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

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

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

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

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

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

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

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

Реализация

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

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

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

проектирования СБИС на предприятии НИИИС (г.Нижний Новгород), а также в учебный процесс в НИУ «МИЭТ».

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

Результаты данной работы были доложены:

• на 17 всероссийской межвузовской научно-технической конференции «Микроэлектроника и информатика — 2010» (Зеленоград, 28-30 апреля 2010 г).

• на XXXVII международной конференции «Новые информационные технологии в науке, социологии, экономике и бизнесе» (1Т Б&Е'Ю, 110 октября 2010 г. Украина, Гурзуф).

• на международной научно-технической конференции «Проектирование систем на кристалле: тенденции развития и проблемы» (МИЭТ, октябрь 2010).

• на семнадцатой ежегодной международной научно-технической конференции студентов и аспирантов "Радиоэлектроника, электроника и энергетика" (МЭИ, февраль 2011).

• на 38-й международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе» (Ялта, 20-30 мая2011).

Публикации

Результаты автора по теме диссертации опубликованы в 8 работах, в том числе в двух статьях в журналах, входящих в список ВАК. Список работ приведен в конце автореферата.

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

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

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

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

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

Около 25 лет назад компания Xilinx начала выпускать свой первый продукт, ХС2064, получивший название FPGA (Field Programmable Gâte Array) - ПЛИС для того, чтобы отличать его от другой программируемой логики и обозначить способ его использования для построения СБИС.

К 1990 г. на этом рынке существовало около 20 компаний. Лидерами были компании Xilinx и Altéra, конкуренцию им составили компании Lattice, Actel, Atmel и QuickLogic. В настоящее время, Xilinx и Altéra также доминируют на рынке. QuickLogic работает в области программируемых СБИС, однако дистанцируется от арены FPGA. Компании Lattice, Actel, Atmel имеют свои ниши на этом рынке. Появились некоторые новые компании, работающие в этой области: Silicon Blue, Achronix, Tabula. Всего около сорока компаний присутствуют в настоящее время на этом рынке.

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

блоки. Наконец, продажа ПЛИС/СБМК - также крайне сложная задача.

Программное обеспечение для проектирования и реализации ПЛИС/СБМК является крайне сложным, содержащим много миллионов строк кода. Например, размещение и трассировка являются сложной задачей, а при наличии оптимизации быстродействия или потребляемой мощности эта задача становится еще сложнее.

В настоящее время мировыми лидерами в проектировании и производстве ПЛИС и СБМК являются следующие компании: Altera, Xilinx, eASIC, ChipExpress.

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

Для реализации этой задачи был разработан и программно реализован алгоритм отображения произвольной комбинационной схемы в базис УЛМ. Краткое описание данного алгоритма и его псевдокод приводится ниже.

Сначала производится отображение схемы на библиотеку, состоящую всего из трех вентилей: NAND2, NOR2, INV (т.е. из КМОП вентилей, имеющих 1 или 2 входа). Это отображение выполняется с помощью программы OPTI, описанной в главе 3 настоящей диссертации. После этого производится отображение схемы в набор поисковых таблиц (LUT) с заданным числом входов N. При этом, двигаясь по схеме в обратном порядке (от первичных выходов к первичным входам), каждая LUT формируется из дерева, образованного N-1 двухвходовыми вентилями, соединенными между собой (и, возможно, включающего некоторое количество инверторов). Конечно, чем больше N, тем больше вариантов такого дерева.

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

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

п - первоначальное (т.е. до начала отображения в LUT) количество двухвходовых вентилей в схеме), ni - первоначальное количество вентилей с fanout=l, N — количество входов LUT.

Тогда вероятность того, что произвольно взятый двухвходовый вентиль имеет fanout=l, равна pi=ni/n. Можно показать, что среднее количество двухвходовых вентилей, которое будет продублировано при формировании каждой LUT, равно

nd=(l-p1)(N-2)+p1(l-p1)(N-3)+p12(l-p1)(N-4)+...+p1N-3(l-p1)

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

прочитать исходное описание схемы;

отобразить схему на библиотеку из 1- и 2-х входовых вентилей;

/* используя программу OPTI */ отобразить схему в набор LUT с заданным числом входов N;

/* двигаясь от первичных выходов к первичным входам */

вычислить окончательное количество LUT;

/* по приведенной в тексте формуле */

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

Схем t. 2 3 4 5 6 7

с432 36.9 25,1 21,7 21,3 23,0 26,3

с499 53,9 36,8 31,6 31,2 33,4 38,4

с1355 101,1 69,0 59,6 58,8 62,9 72,3

С1908 150,8 103,0 88,9 87,6 94,0 107,5'

с2б70 200,1 136,6 117,9 116,4 124,4 142,7

с3540 296,9 202,6 175,0 172,5 185,0 211,9

с5315 429,0 292,8 253,0 249,5 267,3 306,4

СЙ288 397,7 271,5 234,4 231,4 247,5 284,1

с7552 569,9 389,1 336,0 331,5 355,1 407,2

Таблица 1 — Результаты численных экспериментов с использованием набора эталонных комбинационных схем 18СА8-85

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

Логический блок (Logic Element —.LE) — это наименьшая архитектурная единица, реализующая логические функции ПЛИС. Данный логический блок (рисунок 1) содержит 4-входовый функциональный генератор, программируемый регистр, а также схемы переноса и каскадирования.

Рисунок 1 - Схема логического блока с четырьмя входами

Функциональный генератор (LookUp Table — LUT) является функциональным преобразователем, который позволяет быстро вычислять любую Булеву функцию четырех переменных. D-триггер

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

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

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

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

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

Результаты численных экспериментов следующие. На вход программы ресинтеза поступает схема, синтезированная и оптимизированная с помощью Synopsys Design Compiler. В результате использования разработанных в работе программ удается достичь уменьшения мощности или площади схемы (в

зависимости от того, что минимизируется) на 22-25% без ухудшения ее быстродействия.

В' Таблице 2 приведены результаты оптимального отображения для ряда тестовых комбинационных схем в библиотеку поисковых таблиц (LUT) с 4-мя, 2-мя и одним входами (обозначается эта библиотека как LUT421). В данной работе рассматриваются элементы LUT, реализующие произвольные последовательно-параллельные функции (SP-функции).

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

Результаты оптимизации LUTs_LUT421 best

Название Площадь до Наилучшая Задержка до На плучшая Эффективность Наилучшая

тестовой оптимизации площадь оптимизации задержка отображения эффективность

схемы (KLUTs) после после в LUT до отображения

оптньшзашш оптимизации оптимизации в LUT после

(jtLUTs) оптимизации

LUT Best : : LUT liest LUT Best : LUT Best : LUT Best,:::. LUT Не«

421 421 xstab 421 •N'stabí 421 .VsMb; 421 км»®; 421 'AiäliVij-

С17 б 'Kfïi б iffibin: 3 3 45, 0,5 îWiï3;' 0,5

С432 184 15« 2 32 34 0.54 0,62

С1355 482 4 304 iffiijjíí 25 19 iJMX'û 0,52 Isr 0,63 ■imû-k

C190S 530 3 , 263 42 29 3 ■ 0,14 3 ' 0,72 '3r:h чщ

cía 205 2 155 2 ■ 21 .1 ,;?#t 19 asS::-;/. 0,5 0,61

clal 181 * 163 J 30 filter;. 15 0,57 M 0,62

cut 0 75 6 55 26 riiíiyrg. 23 ПЙ;:.:1;!? 0.5 SÍ-ÍIV 0.6 fe/Sf-P

cut 1 79 57 26 ■И!-.: :¡S 23 1'"'.'ir- 0,5 6 S" 0.61 S

cnt_oues 67 6 - 55 29 2 -Гн.:.:. IS 2 - 0,55 б 0,64

cnt_zeros 63 3' 55 28 1 23 ffir'H; 0,56 ÍKSife 0,65

newcfct 153 6¡;.:-».!: 123 6 16 5 . 11 5 0,56 i.A'i© 0,64

•Best ,N'»tab:

1 -table_cost_l_3_6_l 4 -table_cost_02_3_10_02

2 - table_cost_l_3_10_l i — table~cost_002_3_I0_002

3 - table_cost_02_3_4_02 6 - table3°stJX>2_3_50_002

Таблица 2 - Результаты оптимального отображения схемы на библиотеку поисковых таблиц LUT421

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

В Таблице 3 приведены результаты оптимизации при использовании библиотеки LUT4321. Как и следовало ожидать, для этой, более разнообразной библиотеки результаты улучшились.

Результаты одтпмизаппн LUTs_LüT4321 best

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

LUT 4321 Best №.tab LUT 4321 Best ' .Vjtab ' LUT 4321 Best \stab LUT 4321 Best , .Vstab LUT 4321 Best LUT 4321 Best КиаЪ'

cl" б 1 ■ 3 1. • 3 1 2 1 0,5 . 0,75 1

CJ32 150 6 117 6 16 1 14 1 0,6 0.73 1

С1355 432 3 232 •3 25 г 14 1 0,52 ; 0.72 3 '

C190S 49 9 f 248 6 . 34 6 - 18 6 0,56 . 0,79 4

da 200 128 б 21 V 10 1 0,51 Î- 0.69 б

clal 139 : 133 J . 16 1 • 16 1 0,67 з * 0,71 .

cut 0 63 б - 48 26 •t 17 2 0.53 6 0.71 6

Cllt 1 73 2 1 46 2 26 1 17 1 0.52 2 0.71 2,

cut ones 51 > 46 2 18 3 15 - 0.64 0,72 б'

cnt zeros 50 2 46 2 П 6 13 6 0,65 0.72 2 ' '.

newckt 115 V . ■ 101 1 10 1 S 1 0.66 4 , 0,76 4 .

"Вез! Л'ЛаЬ:

1 - 1аЫе_со$М_3_б__1 4 -1аЫе_ссге1_02_3_10_02

2 - 1аЫе_акГ 1~3_10_1 5 - 1аЫе_смГ_002_3 _10_002

3 - 1аЫе_со.?Г02_3_4~02 б • |»Ые_соЯ_002_3_50_002

Таблица 3. Результаты оптимального отображения схемы на библиотеку поисковых таблиц ШТ4321

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

Перечислим основные причины, приводящие к необходимости обфускации:

• 1Р-блоки используются без необходимой уплаты денег владельцу;

• Разработчики, легально использующие 1Р-блоки, нелегально продают их третьим лицам;

• Изготовители ИС торгуют нелегальными копиями 1Р-блоков;

• Компании занимаются обратным конструированием 1Р-блоков.

Далее перечислим простейшие методы обфускации цифровых схем:

• Удаление комментариев и изменение имен в описании нетлиста;

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

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

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

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

Рисунок 2 — Конечный автомат (ББМ), встраиваемый в схему обфускации

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

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

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

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

На рисунке 3 показан пример введения в схему фиктивного демпфирующего цикла.

Рисунок 3 — Пример введения в схему фиктивного демпфирующего цикла

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

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

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

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

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

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

Публикации

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

1. В.А.Беспалов, А.Л.Глебов, Н.А.Кононов, Д.Ю.Немчин. Методика выбора универсальных логических модулей для ПЛИС и СБМК // Известия ВУЗов. Электроника. - 2011. - №1. - С.46.

2. А.Л.Глебов, Н.А.Кононов, Д.Ю.Немчин. Метод обфускации цифровых схем, спроектированных на основе ПЛИС и СБМК // Открытое образование. В трудах 38-й международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе»

Ялта, 2011,- С.131.

3. Н.А.Кононов. Оптимизационный подход к выбору универсальных логических модулей для ПЛИС и СБМК // Микроэлектроника и информатика — 2010. Семнадцатая всероссийской межвузовской научно-технической конференции. Тезисы докладов — М.:МИЭТ, 2010. - С.79.

4. В.А.Беспалов, H.A. Кононов, А.В.Ларионов. Оптимизация логических модулей для СБМК и ПЛИС // Труды 37-й международной конференции «Новые информационные технологии в науке, социологии, экономике и бизнесе». - Ялта, 2010.-С.164.

5. А.А.Миндеева, Н.А.Кононов, A.B. Ларионов. Алгоритмы безвекторной оценки мощности // Труды 37-й международной конференции «Новые информационные технологии в науке, социологии, экономике и бизнесе».- Ялта, 2010.-С.176.

6. Н.А.Кононов. Оптимизация логических модулей для СБМК и ПЛИС. Оптимизация логических модулей для СБМК и ПЛИС // Проектирование систем на кристалле: тенденции развития и проблемы. Международная научно-техническая конференция: Тезисы докладов. - М.:МИЭТ, 2010. — С. 17.

7. Н.А.Кононов. Разработка маршрута проектирования мультислойных фотошаблонов для изготовления специализированных СБИС микро- и нанометрового уровня технологий // Проектирование систем на кристалле: тенденции развития и проблемы. Международная научно-техническая конференция: Тезисы докладов. - М.:МИЭТ, 2010.— С.44.

8. Н.А.Кононов. Оптимизация и обфускация комбинационных схем для СБМК и ПЛИС // Радиоэлектроника, электротехника и энергетика. Семнадцатая ежегодная международная научно-техническая конференция студентов и аспирантов: Тезисы докладов. - М.:МЭИ, 2011. - С.394.

Формат 60x84 1/16. Уч.-изд. л. 4 4. Тираж 100 экз. Заказ № />/ 2

Отпечатано в типографии ИПК МИЭТ.

124498, Москва, Зеленоград, проезд 4806, д.5, МИЭТ.

Введение

Оглавление

Глава 1. СБИС с программируемой архитектурой.

1.1. СБИС с программируемой архитектурой компаний Altera и Xilinx.

1.2. СБИС с программируемой архитектурой компании eASIC.

1.3. Подход компании ChipExpress к проектированию СБИС.

1.4. Алгоритм CutMap - совместная минимизация глубины и площади в процессе отображения LUT в ПЛИС.

1.5. Алгоритм DAOmap - оптимальный по глубине алгоритм оптимизации и отображения для ПЛИС.

1.6. Восстановление схемы с ограничением по глубине методом

Cut Substitution для технологического отображения LUT в ПЛИС.

1.7. IMap, Эвристические методы минимизации площади в технологии отображения LUT для ПЛИС.

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

Глава 2. Разработка методов и алгоритмов структурной оптимизации логических модулей для СБМК и ПЛИС.

2.1. Оптимизационный подход к выбору функциональных блоков для

СБМК и ПЛИС.

2.2. Назначение и основные характеристики логического блока.

2.3. Схемы переноса и каскадирования.

2.4. Электрическая схема логического блока.

2.5. Описание портов логического блока.

2.6. Результаты моделирования.

2.7. Общая формула подсчета количества транзисторов в УЛМ.

2.8. Выбор варианта УЛМ для СБМК (ПЛИС).

Глава 3. Методы и алгоритмы оптимального синтеза комбинационных схем.

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

3.2. Представление КМОП схем в виде ЗР-ВББ.

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

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

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

3.6. Описание программы.

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

3.8. Библиотека комплиментарных схем ШТ4321 и Ы1Т421.

3.9. Таблицы с результатами оптимизации тестовых схем К!СА8в программном пакете орй на основе комплиментарных библиотек ШТ421 и ШТ4321.

Глава 4. Разработка и исследование методов обфускации цифровых схем, спроектированных на основе ПЛИС и СБМК.

4.1. Основная идея предлагаемого метода.

4.2. Временной анализ и демпфирующие циклы.

4.3. Реализация алгоритма обфускации и использование ПЛИ.

4.4. Особенности применения метода обфускации к схемам на ПЛИС и СБМК.

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

4.6. Защита проектных решений на уровне нетлиста.

4.7. Технические преимущества предлагаемого метода.

4.8. Примеры обфускации.

4.9. Выбор оптимального набора узлов.

4.10. Алгоритм итерационного распределения.

4.11. Маршрут проекта, основанный на обфускации проектных решений.

ПЛИС и СБМК являются в настоящее время наиболее популярными решениями для проектирования и производства СБИС разнообразного назначения, для различных сроков и объемов прототипирования и производства.

В настоящей работе используется аббревиатура "ПЛИС" (программируемая логическая интегральная схема) в том же смысле, который имеет англоязычная аббревиатура "FPGA". Аналогично, аббревиатура "СБМК" (структурированный базовый матричный кристалл) используется здесь идентично англоязычной аббревиатуре "structured ASIC".

При разработке электронных систем вопросы оптимизации быстродействия, мощности, площади и информационной защиты функций и данных, заложенных в используемой элементной базе, по-прежнему остаются актуальными. Применительно к схемам на стандартных ячейках и компьютерным программам эти вопросы исследовались в ИППМ РАН [76,77,80] и ИСП РАН [72]. В данной работе эти вопросы рассматриваются для схем, спроектированных в базисе ПЛИС и СБМК.

Актуальность работы.

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

Для обеспечения паритетных возможностей российскими разработчиками аппаратуры в качестве элементной базы используются полузаказные СБИС с программируемой логикой — ПЛИС/СБМК (FPGA/structured ASIC). Несмотря на то, что ПЛИС уступают заказным схемам по быстродействию в 3-5 раз, а по расходу кремния в 7-10 раз, они очень популярны, поскольку позволяют в несколько раз сократить сроки и качество разработки.

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

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

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

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

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

- разработка и программная реализация методов и алгоритмов оптимизации универсального логического модуля (УЛМ) ПЛИС и СБМК;

- разработка и программная реализация методов и алгоритмов оптимального отображения больших комбинационных схем в логический базис ПЛИС и СБМК; разработка и программная реализация методов обфускации (маскировки проектных решений) комбинационных схем;

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

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

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

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

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

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

Реализация.

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

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

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

Методы и алгоритмы, предложенные в данной работе, а также компьютерные программы, разработанные на их основе, могут быть использованы для эффективного проектирования СБИС и систем на кристалле на основе ПЛИС и СБМК, в том числе производимых ведущими фирмами, с проектными нормами 90,45,28 нм. Результаты работы внедрены в процесс проектирования СБИС на предприятии НИИИС (г. Нижний Новгород), а также в учебный процесс в НИУ «МИЭТ».

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

Результаты данной работы были доложены:

• на 17 всероссийской межвузовской научно-технической конференции «Микроэлектроника и информатика — 2010» (Зеленоград, 28-30 апреля 20 Юг).

• на XXXVII международной конференции «Новые информационные технологии в науке, социологии, экономике и бизнесе» (1Т Б&Е'Ю, 1-10 октября 2010г. Украина, Гурзуф).

• на международной научно-технической конференции «Проектирование систем на кристалле: тенденции развития и проблемы» (МИЭТ, октябрь 2010).

• на семнадцатой ежегодной международной научно-технической конференции студентов и аспирантов "Радиоэлектроника, электроника и энергетика" (МЭИ, февраль 2011).

Публикации.

Результаты автора по теме диссертации опубликованы в 8 работах [98-105], в том числе в двух статьях и журналах, входящих в список ВАК.

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

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

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

1) Разработан алгоритм оптимального синтеза (ресинтеза) комбинационных схем. Данный алгоритм основан на использовании представления схем в виде BDD специального вида, а именно SP-BDD. Произведена адаптация данного алгоритма к задаче отображения схем в базис ПЛИС и СБМК.

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

3) Численные эксперименты по ресинтезу с отображением схемы в базис ПЛИС и СБМК также показывают, что в результате оптимизации эффективность отображения значительно улучшается. В экспериментах использовалась поисковая таблица (LUT) с оптимальным числом входов, равным 4.

Глава 4. Разработка и исследование методов обфускации цифровых схем, спроектированных на основе ПЛИС и СБМК

В последние годы наблюдается возрастающий интерес к проблеме обфускации (затруднение понимания, скрытие смысла) компьютерных программ [72],[73]. Цель такой обфускации - предотвращение несанкционированного доступа к указанным программам. Наряду с указанной проблемой, актуальной также является задача обфускации схемотехнических решений, используемых в цифровых СБИС [74],[75]. По сути дела эти задачи являются глубоко родственными.

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

Простая > логическая импликация" (ПЛИ) между двумя узлами цифровой схемы а, Ъ — это отношение типа (а=0)-> (¿=1) или, используя более короткое обозначение, а -> Ъ В работах [76],[77] показано, что цифровая комбинационная схема обычно содержит большое количество ПЛИ, а также описан быстрый алгоритм их вычисления. Ниже будет показано, что, используя найденные ПЛИ, можно вводить в схему некоторое количество фиктивных (в действительности неработающих) циклов. В дополнение к этому можно вводить также и реальные (работающие) циклы [78],[79]. При этом схема остается комбинационной, и реализуемая ею Булева функция не изменяется. Однако для обфускированной (запутанной) таким образом схемы автоматическое восстановление ее Булевой функции становится крайне сложной задачей, не решаемой обычными алгоритмами и программами восстановления Булевых функций. Final circuit

II module final (a, b, с, x, y); input a, b, c; output x, y; wire d, e; assign d = ~ (a | b |e); assign x = ~d; assign у = ~ (b & c); assign e = ~ (x | y); endmodule b)

Рис.4.3 - Входное (а) и выходное (b) описание схемы, показанной на Рис.4.1.

Для эффективного выполнения обфускации цифровой комбинационной схемы предлагаемым методом необходимо выполнение следующих условий: a) для формирования фиктивных циклов нужно выбирать пары узлов с ПЛИ между ними, отстоящие "далеко" друг от друга; b) предварительно необходимо произвести временной анализ схемы, используя ту или иную модель задержки логических вентилей; c) используя результаты временного анализа, нужно формировать фиктивные демпфирующие циклы, не удлиняющие критические пути, т.е. не ухудшающие быстродействие схемы.

Поясним реальность выполнения условий а) и с). В работах [76],[77] был разработан быстрый алгоритм вычисления большого количества ПЛИ и было показано, что ПЛИ очень распространены в комбинационных схемах. Псевдо-код алгоритма вычисления ПЛИ показан на Рис.4.4. инициализировать списки тривиальными ПЛИ; повторять { для (каждого вентиля в прямом порядке) произвести прямое распространение ПЛИ с применением контра-позитивного закона; } до установления; повторять { для (каждого вентиля в обратном порядке) для (каждого входа вентиля) произвести боковое распространение ПЛИ с применением транзитивного и контра-позитивного законов; повторять { для (каждого вентиля в прямом порядке) произвести прямое распространение ПЛИ с применением контра-позитивного закона; до установления; до установления;

Рис.4.4 - Псевдо-код алгоритма быстрого вычисления ПЛИ.

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

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

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

4.4. Особенности применения метода обфускации к схемам на ПЛИС и СБМК

В отличие от схем, спроектированных на основе библиотек стандартных ячеек (таких как NAND, NOR, AOI и т.п.), кристаллы ПЛИС и СБМК содержат большие массивы универсальных логических модулей (УЛМ). Каждый УЛМ для формирования комбинационных блоков содержит, как правило, две поисковые таблицы (LUT = Look-up Table). Каждая'LUT может настраиваться (в ПЛИС — электрически, в СБМК — с помощью слоев металлизации) на вычисление Булевой функции четырех или менее аргументов [98].

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

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

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

• Два или более демпфирующих цикла могут иметь общую часть.

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

Результаты численных экспериментов для ряда схем из набора ISCAS-85 даны в Таблице 4.1. Для каждой схемы приведены число первичных входов и первичных выходов, глубина схемы (т.е. длина критического пути в LUT), количество LUT в схеме. В последних трех столбцах приведен рост числа транзисторов в схеме при введении соответственно пяти, десяти и двадцати демпфирующих циклов (ДЦ). Из Таблицы 4.1 видно, что цена обфускации схемы реального размера вполне приемлема. схема #Р1 #РО глубина #вентплей ю mm 20 ДЩ%) с432 36 7 17 248 5.6 9.9 26.8 с499 41 32 11 454 2.3 5.4 12.3

С1355 41 32 24 559 1.9 3.8 11.3

С1908 33 25 40 1057 1.7 23 5.3 с2670 157 64 32 1400 1.0' 23> 3.8 с3540 50 22 47 1983 0.9 1.4 3.2 с5315 178 123 49 2973 0.5 0.8 2.0 с6288 32 32 124 2416 0.7 1.0 2.5

С7552 207 108 43 4043 0.4 0.7 1.6

1. http ://www. altera.com2. http://www.eASIC.com3. www.chipexpress.com/

2. Stratix IV Device Handbook, Altera Corp., Nov 2009.

3. Hardcopy Ш Device Handbook, Altera Corp., July 2009.

4. Virtex-5 FPGA, User Guide, Xilinx, Nov 2009.

5. J.Cong and Y.HWang, "Simultaneous Depth and Area Minimization in LUT-Based' FPGA Mapping," International Symposium on Field Programmable Gate Arrays, 1995.

6. Chen, К. C., J. Cong, Y. Ding, A. B. Kahng, and P. Trajmar, "DAG-Map: Graph-based FPGA Technology Mapping for Delay Optimization," IEEE Design and Test of Computers, pp. 7-20, Sep. 1992.

7. Cong, J. and Y. Ding, "An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs," IEEE Trans, on Computer-Aided Design, Vol. 13, pp. 1-12, Jan. 1994.

8. Cong, J. and Y. Ding, "On Area/Depth Tradeoff in LUT-Based FPGA Technology Mapping," IEEE Trans, on VLSI Systems, Vol.2, June 1994.

9. Cong, J. and Y.-Y. Hwang, "Simultaneous Depth and Area Minimization in LUT-Based FPGA Mapping," Proc. ACM 3rd Int'l Symp. on Field Programmable Gate Arrays, pp. 68-74, Feb. 1995.

10. Francis, R. J., J. Rose, and K. Chung, "Chortle: A Technology Mapping Program for Lookup Table-Based Field Programmable Gate Arrays," Proc. 27th АСМЛЕЕЕ Design Automation Conference, pp. 613-619, June 1990.

11. Francis, R. J., J. Rose, and Z. Vranesic, "Technology Mapping for Delay Optimization of Lookup Table-Based FPGAs," MCNC Logic Synthesis Workshop, 1991.

12. Karplus, K., "Xmap: A Technology Mapper for Table-lookup Field-Programmable Gate Arrays," Proc. 28th АСМЛЕЕЕ Design Automation Conference, pp. 240-243, June 1991.

13. R. Murgai, et al., "Performance Directed Synthesis for Table Look Up Programmable Gate Arrays," ICCAD, Nov., 1991.

14. H. Yang and D: F. Wong, "Edge-map: Optimal Performance Driven Technology Mapping for Iterative LUT based FPGA Designs," ICCAD, Nov. 1994.

15. P. Pan and; C.L. Liu, "Optimal Clock Period FPGA Technology Mapping for Sequential Circuits," DAC, June 1996.

16. A.H. FarrahL and M. Sarrafzadeh, "FPGA Technology Mapping for Power Minimization," Proc. of Intl. Workshop in- Field Programmable Logic and' Applications, 1994.

17. J. Anderson- and F. N. Najm, "Power-Aware Technology Mapping for' LUT-Based FPGAs," IEEE Intl. Conf. on Field-Programmable Technology, 2002.

18. Z-H. Wang et al., "Power Minimization in LUT-Based FPGA Technology Mapping," ASPDAC, 2001.

19. H. Li, W. Mak, and S. Katkoori, "Efficient LUT-Based FPGA Technology Mapping for Power Minimization," ASPDAC, 2003.

20. Ji Lamoureux and S.J.E. Wilton, "On the Interaction between Power- Aware CAD» Algorithms for FPGAs," IEEE/ACM-International« Conference on Computer Aided Design, 2003.

21. D. Chen, et al., "Low-Power Technology Mapping for FPGA Architectures with Dual Supply Voltages," FPGA, Feb. 2004.

22. C. Legl, B. Wurth, and K. Eckl, "A Boolean Approach to Performance-Directed Technology Mapping for LUT-Based FPGA Designs," DAC, June 1996.

23. J. Cong and Y. Ding, "Beyond the Combinatorial Limit in Depth Minimization for LUT-Based FPGA Designs," ICCAD, Nov. 1993.

24. Maxim Teslenko, Elena Dubrova, "Hermes: LUT FPGA Technology Mapping Algorithm for Area Minimization with Optimal Depth," IEEE International Conference on Computer Aided Design, 2004.

25. A. Lu, G. Stenz, and F. M. Johannes, "Technology mapping for minimizing gate and routing area," in Proc. Conf. Des., Autom. Test Eur. Paris, France: Le Palais des Congres de Paris, 1998, pp. 664-669.

26. MVSIS Group, MVSIS: Multi-Valued Logic Synthesis System, Berkeley: Univ. California Berkeley. Online]. Available: http://www-cad.eecs.berkeley.edu/mvsis/

27. A. Mishchenko, S. Chatteijee, and R. Brayton, "An integrated technology mapping environment," in Proc. Int. Workshop Logic and Synthesis, Lake Arrowhead, CA, 2005, pp. 383-390.

28. S. Chatteijee, A. Mishchenko, R. Brayton, X.Wang, and T. Kam, "Reducing structural bias in technology mapping," in Proc. Int. Workshop Logic and Synthesis, Lake Arrowhead, CA, 2005, pp. 375-382.

29. S.Iman, M.Pedram. "Logic Extraction and Factorization for Low Power," DAC-95, p.248.

30. C.Y.Tsui, M.Pedram, A.M.Despain: "Technology Decomposition and Mapping Targeting Low Power Dissipation," DAC-93, p.68.

31. J.P.Fishburn. "A Depth-Decreasing Heuristic for Combinational Logic; or How to Convert a Ripple-Carry Adder into a Carry-Lookahead-Adder or Anything In-Between," DAC-90, p.361.

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

33. V.Tivari, P.Ashar, S.Malik. "Technology Mapping for Low Power," DAC-93, p.74.

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

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

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

37. S.Gavrilov, A.Glebov, S.Rusakov, DJBlaauw, L.Jones, G.Vijayan. "Fast Power Loss Calculation for Digital Static CMOS Circuits," European Design & Test Conf., 1997, p.411.

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

39. K.D.Boese, A.B.Kahng, C.W.A.Tsao. "Best-So-Far vs. Where-You-Are: New Perspectives on Simulated Annealing for CAD," Euro-DAC'93, p.78.

40. T.Sakurai, A.R.Newton. "MOSFET Model Parameter Extraction Based on Fast Simulated Diffusion," Memorandum UCB/ERL M90/20, 16 March 1990, Univ. of California, Berkeley.

41. A. Dharchoudhury, S. M. Kang, К. H. Kim, and S. H. Lee, "Fast and Accurate Timing Simulation with Regionwise Quadratic Models for MOS," Int'l Conf on Computer Aided Design, Nov 1994, pp. 190-193.

42. S.Caufape, J.Figueras. "Power Optimization of Delay Constrained CMOS Bus Drivers", ED&TC-96, p.205.

43. S.Turgis, N.Azemad, D.Auvergne. "Design and Selection of Buffers for Minimum Power-Delay Product", ED&TC-96, p.224.

44. E.Musoll, J.Cortadella. "Optimizing CMOS Circuits for Low Power Using Transistor Reordering", ED&TC-96, p.219.

45. B.Rohfleish, A.Kolbl, B:Wurth. "Reducing Power Dissipation after Technology Mapping by Structural Transformations", DAC-96, p.789

46. Варновский Н.П., Захаров В.А., Кузюрин H.H., Шокуров А.В.,

47. О перспективах решения задачи обфускации компьютерных программ», Труды конференции «Математика и безопасность информационных технологий» (МаБИТ-03), Москва, 2003, с.344-351.

48. Lynn В., Prabhakaran М., Sahai A., "Positive results and techniques for obfuscation", Lecture Notes in Computer Science, v. 3027,2004, p.20-39.

49. Barak B. et al., "On the (Impossibility of obfuscating programs", Electronic Colloquium on Computational Complexity, 8(57), 2001, p.1-41.

50. Norman K.T., "Algorithms for white-box obfuscation using randomized subcircuit selection and replacement", Thesis, Air Force Institute of Technology, Ohio, 2008, 99 pp.

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

52. Riedel M.D., "Cyclic combinational circuits", PhD Dissertation, California Institute of Technology, 2004.

53. Тлебов A.JI:, Гурарий M.M: и, др. (под ред. Стемпковского A.JI.), "Актуальные проблемы моделирования1 в системах автоматизации схемотехнического проектирования", М., Наука, 2003, 430 с.

54. Д. Colin Johson, "Antipiracy scheme aims protect chip makers". http://www.eetimes.com

55. A.B. Kahng, et al, "Constraint-based Watermarking Techniques for Design IP Protection, IEEE TCAD, vol. 20, no. 10, pp: 1236-1252, Oct. 2001.

56. F. Koushanfar and G. Qu, "Hardware Metering", Proc. DAC, 2001.

57. D.C. Musker, "Protecting and Exploiting Intellectual Property in Electronics", Proc IBC Conferences, 1998.87. "ThicketTM Family of Source Code Obfuscators". http://www.semdesigns.com

58. T. Batra, "Methodology for protection and Licensing of HDL IP", http ://www.us. design-reuse. с om/news/?id=12745\&print=y es89. "Designware USB Solutions".http://www.synopsys.com/products/designware/usb solutions.html

59. E. Castillo, et al, "IPP@HDL: Efficient Intellectual Property Protection Scheme for IP Cores", IEEE TVLSI,vol. 15, no. 5, pp. 578-590, May 2007.

60. I. Cox, M: Miller, and J. Bloom, "Digital Watermarking: Principles and Practice", San Mateo,CA: Morgan Kaufmann, 2001'.

61. A.B. Kahng, et al, "Watermarking techniques for intellectual property protection", Proc. DAC, 1998

62. F. Koushanfar andM. Potkonjak, "CAD-based Security, Cryptography, and Digital Rights Management", Proc. DAC, 2007.

63. Y. Alkabani, F. Koushanfar and M. Potkonjak, "Remote Activation of ICs for Piracy Prevention and Digital Right Management", Proc. ICCAD, 2007. 95JJ.A. Roy, F. Koushanfar andl.L. Markov, "EPIC: Ending Piracy of Integrated Circuits", Proc. DATE, 2008.

64. W.A. Moore and P.A. Kayfes, "US Patent 7213142 System andmethod to initialize registers with an EEPROM stored boot sequence (2007)". http://www.patentstorm.us/patents/7213142/description.html'97. http://www.fm.vslib.cz/kes/asic/iscas/

65. H.A. Кононов, «Оптимизация логических модулей для СБМК и ПЛИС». Тезисы докладов международной научно-технической конференции «Проектирование систем на кристалле: тенденции развития и проблемы» (МИЭТ, октябрь 2010) стр.17

66. Н.А.Кононов, «Оптимизация и обфускация комбинационных схем для СБМК и ПЛИС». Тезисы докладов семнадцатой ежегодной международной научно-технической конференции студентов и аспирантов "Радиоэлектроника, электроника и энергетика" (МЭИ, февраль 2011).