Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,791

MODELING OF DIGITAL CMOS CIRCUITS USING TERNARY DECISIONS DIAGRAMS

Glebov A.L. 1 Mindeeva A.A. 1 Petrosyan V.S. 1 Gevorgyan A.M. 1
1 National Research University of Electronic Technology
В статье описывается логическое моделирование цифровых КМОП схем при помощи диаграмм троичных решений. Производится оценка затрачиваемой схемой мощности как пример использования такого моделирования. Как вводная информация объясняется сутью представления Булевых функций в виде диаграмм двоичных решений (BDD). Для описания неполно определенных Булевых функций вида f: Tn->T, T={0,U,1} представляются диаграммы троичных решений (TDD) и вводится понятие последовательно-паралельных диаграмм троичных решений (SP-TDD). На основе представления КПОМ схемы в виде SP-BDD описывается алгоритм построения SP-TDD модели цифровых КМОП схем. Логическое моделирование цифровых схем с использованием TDD дает возможность оптимизации цифровой схемы и оценки параметров цифровой схемы с учетом третьего, неопределенного состояния вентилей. В работе производится логическое моделирование цифровой схемы и оценка потребляемой схемой мощности. В случае TDD представления оценка потребляемой мощности имеет интервальное значение, так как в модели существуют узлы с неопределенным значением и, следовательно, с неопределенным переключением. В последующем эти интервальные значения можно уточнить путем наложения дополнительной информации.
The paper describes the logic simulation of digital CMOS circuits using ternary decisions diagrams(TDD). Also in this paper is done the interval estimation of power consumed by the scheme as an example of the use of such modeling. As an introduction there are explained representation of Boolean functions in the form of a binary decision diagram (BDD). To describe incompletely specified Boolean functions of the form f: Tn-> T, T = {0, U, 1} there are proposed the ternary decisions diagrams (TDD) and it’s special type - series-parallel ternary decisions diagrams (SP-TDD). On the basis of the SP-BDD representation of CMOS scheme explained the SP-TDD representation of CMOS scheme described the algorithm for constructing the SP-TDD model of CMOS circuits. Logical simulation of digital circuits using TDD enables optimization of digital circuits and estimation of the parameters of digital circuits with the gates in indeterminate state. In this paper is made logical modeling of digital CMOS circuit and estimation of the power consumed by the scheme. In the case of TDD the consumed power it is a interval value, as there are gates in the scheme with an undefined state, and therefore uncertain switching. Subsequently, these interval values can be improved by imposing additional information.
power estimation
SP-BDD
BDD
SP-TDD
TDD
logic simulation

Введение

Хорошо известно, что BDD (диаграммы двоичных решений) являются удобным и эффективным представлением Булевых функций f: Bn->B, B={0,1} [2],[7]. Это представление позволяет конструировать и программно реализовывать различные алгоритмы для работы с системами Булевых функций. В частности, это алгоритмы логического синтеза, верификации и генерации тестов для цифровых схем. Сюда же можно отнести и алгоритм логического моделирования.

Известна также SP-BDD (последовательно-параллельная диаграмма двоичных решений), которая представляет собой BDD специального вида и является адекватной моделью цифровых КМОП схем [1],[3]. SP-BDD содержит в себе полную информацию не только о Булевой функции, вычисляемой КМОП вентилем, но также и о его детальной электрической схеме на транзисторном уровне. Кроме логического моделирования, SP-BDD может быть использована для оперативной и достаточно точной оценки задержек и потребляемой мощности цифровых КМОП схем, а также для их ресинтеза (структурной оптимизации) [4] и во многих других приложениях. На практике часто приходится иметь дело с неполно определенными Булевыми функциями вида f: Tn->T, T={0,U,1}. Дополнительное состояние U может интерпретироваться различными способами. Чаще всего оно интерпретируется в рамках Клиниевой сильной трехзначной логики (Kleenean strong ternary logic) [6], в которой U – это состояние «не определено» (undefined = don't care). Т. е. это в действительности либо 0, либо 1, но мы не знаем что именно (или нам не нужно это знать). Значение U может принимать как каждый из аргументов, так и сама неполно определенная Булева функция. Далее для таких функций будем для краткости использовать термин «Клиниева функция».

По аналогии с BDD, удобным представлением для Клиниевой функции является TDD (диаграмма троичных решений) [5],[8]. В TDD каждая нетерминальная вершина имеет трех потомков, кроме того имеются три терминальные вершины, соответствующие значениям функции 0,U,1. По умолчанию, под TDD обычно понимают ROTDD, т. е. минимизированную упорядоченную TDD. По аналогии с BDD, для заданной Клиниевой функции TDD строится в три этапа:

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

Таким образом построенная TDD является каноническим (единственным) представлением Клиниевой функции (для заданного порядка аргументов). Для TDD разработан ряд алгоритмов и пакетов программ, аналогичных таким для BDD. Наиболее очевидным применением TDD является логическое моделирование соответствующих цифровых схем.

Построенная вышеуказанным способом TDD называется полной TDD. Если мы удалим из нее все U-ветви (и все, что определяется только ими), мы получим так называемую сокращенную (abbreviated) TDD [5], [8]. Сокращенная TDD также является каноническим представлением Клиниевой функции. По сокращенной TDD может быть однозначно восстановлена полная TDD. Однако сокращенная TDD занимает значительно меньше места в компьютерной памяти. Поэтому во многих алгоритмах выгоднее использовать сокращенную TDD, а полную TDD восстанавливать только тогда, когда это необходимо (например, при логическом моделировании). Пример полной и сокращенной TDD для функции f(a,b,c)=ab+c показан на рис. 1. (Следует отметить, что для некоторых функций U-терминал может сохраняться в сокращенной TDD.)

Рис. 1. Полная (a) и сокращенная (b) TDD для функции f(a,b,c)=ab+c

В общем случае ветви TDD, идущие вниз от нетерминальной вершины, должны быть помечены значками ”0”,”U”,”1”, указывающими, какому значению переменной в данной вершине соответствует данная ветвь. В TDD на рис.1(a) подразумевается, что ветви, идущие от каждой вершины, помечены по умолчанию слева направо соответственно символами ”0”,”U”,”1” (на рис. 1(b) — символами ”0”,”1”). Однако такая умолчательная разметка удобна далеко не всегда.

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

SP-TDD модель цифровых КМОП схем

Приведем сначала определение SP-BDD через рекурсивную процедуру ее построения [1] (рис. 2).

Рис. 2. Рекурсивное построение SP-BDD: A. SP-BDD для одного ключа

B. Формирование SP-BDD для последовательного соединения двух ПП-цепей

C. Формирование SP-BDD для параллельного соединения двух ПП-цепей

По аналогии с вышеприведенным определением, дадим рекурсивное определение SP-TDD как модели Клиниевой функции, задаваемой последовательно-параллельной цепью (ПП-цепью) из ключей (с возможностью третьего, неопределенного состояния как каждого ключа, так и всей цепи). Данное определение показано на рис. 3.

Рис. 3. Рекурсивное построение SP-TDD: A. SP-TDD для одного ключа

B. Формирование SP-TDD для последовательного соединения двух ПП-цепей

C. Формирование SP-TDD для параллельного соединения двух ПП-цепей

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

Если для некоторой ветви явно не показан потомок, то им является: 0-терминал для ветви идущей вниз-влево; U-терминал для ветви идущей строго вниз; 1-терминал для вершины идущей вниз-вправо.

Отметим два важных факта. Во-первых, как и в случае SP-BDD, SP-TDD может быть построена не только через построение троичного дерева (см. выше), но также и через последовательность присоединений параллельно и последовательно соединенных фрагментов.

Во вторых, из сравнения рис. 2, 3 видно, что сокращенная SP-TDD, полученная из полной удалением U-ветвей, есть не что иное, как соответствующая SP-BDD.

Логическое моделирование на основе TDD и оценка мощности

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

Рассмотрим возможные переключения логического вентиля G при переходе схемы от некоторого входного вектора к следующему. Пусть энергия, потребляемая вентилем при переключении, равна EG. Возможны три варианта для потребляемой энергии E при следующих переключениях выхода вентиля:

E принадлежит [0,0] при 0->0, 1->1

E принадлежит [EG,EG] при 0->1, 1->0

E принадлежит [0,EG] при 0->U, U->0, 1->U, U->1, U->U

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

a) Для моделируемой схемы, заменить каждый вентиль его TDD-представлением;

b) Инициализировать состояние схемы в соответствии с нулевым входным вектором;

c) Инициализировать полную энергию интервалом [0,0], максимальную энергию – нулем;

d) Для каждого последующего входного вектора повторить пп. e-k;

e) Инициализировать тактовую энергию интервалом [0,0];

f) Для каждого вентиля, в топологическом порядке (от входов к выходам), повторить пп. g-i;

g) Определить новое состояние выхода вентиля, найдя в его TDD путь для нового состояния его входов;

h) Определить интервальную оценку энергии, потребленной вентилем на данном такте;

i) Добавить интервальную оценку энергии, потребленной вентилем, к тактовой энергии;

j) Добавить тактовую энергию к полной энергии;

k) Обновить максимальную энергию в соответствии с тактовой энергией;

l) По полной энергии и времени моделирования вычислить интервальную оценку мощности.

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

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

В Таблице 1 приведены результаты эксперимента для 6-и схем. Для каждой схемы выбраны два входных вектора по количеству неопределенных входов (UND в таблице). Название схем и количество транзисторов в схеме указаны в колонках 1 и 2. В колонках 2, 3, 4 указаны, соответственно, количество входов, количество выходов схем и количество неопределенных входов. В колонке 6 указана процентная доля транзисторов в неопределенном состоянии от их общего числа. В колонках 7,8,9, соответственно, минимальная мощность, максимальная мощность и пиковая мощность. Количество циклов – 2000 на все схемы.

 

2

3

4

5

6

7

8

9

Схема

Gates

PI

PO

UND

Part Ugates %

minPower

maxPower

peakPower

C432

160

36

7

10

28,1

90.99

252.51

367

C432

160

36

7

20

53,7

49.17

358.58

456

C1355

546

41

32

12

65,5

154.5

1190.61

1450

C1355

546

41

32

25

88,4

38.52

1374.58

1450

C1908

880

33

25

10

52,5

392.12

1877.33

2398

C1908

880

33

25

20

72,6

140.35

2192.29

2576

C5315

2485

178

123

50

4,4

2800.57

3132.53

4041

C5315

2485

178

123

100

31,1

1851.24

4188.15

4879

C6288

2416

32

32

10

58,0

909.14

5157.76

5508

C6288

2416

32

32

20

96

1211.12

6594.42

6736

Cla

304

33

19

10

33,7

210.59

497.748

677

Cla

304

33

19

20

63,9

106.37

636.063

734

Таблица 1

Заключение

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

Рецензенты:

Амербаев В.М., д.т.н., профессор, главный научный сотрудник ИППМ РАН, г. Зеленоград.

Гаврилов С.В., д.т.н., профессор НИУ МИЭТ, г. Зеленоград.