Например, Бобцов

ИСПОЛЬЗОВАНИЕ РЕЛЯЦИОННОЙ ТЕОРИИ ПРИ ОПТИМАЛЬНОМ ПРОЕКТИРОВАНИИ ИНТЕГРАЛЬНЫХ СХЕМ

ИСПОЛЬЗОВАНИЕ РЕЛЯЦИОННОЙ ТЕОРИИ ПРИ ОПТИМАЛЬНОМ...

УДК 004.312.2, 004.021, 510.649
ИСПОЛЬЗОВАНИЕ РЕЛЯЦИОННОЙ ТЕОРИИ ПРИ ОПТИМАЛЬНОМ ПРОЕКТИРОВАНИИ ИНТЕГРАЛЬНЫХ СХЕМ
Д.В. Демидовa, b
a Университет ИТМО, 197101, Санкт-Петербург, Россия b ЗАО «Интел А/О», 196247, Санкт-Петербург, Россия, Daniil.demidov@gmail.com
Аннотация. Предложен подход к адаптации реляционной теории для решения задач систем автоматизированного проектирования интегральных схем. Разработан алгоритм оптимального поиска неявных Don't Care (безразличных) значений. Алгоритм описан в терминах адаптированной теории, что позволило получить простое описание алгоритма как для неформального понимания, так и для формального анализа. Предложенный подход позволяет использовать позитивный опыт реляционных баз данных по эффективной (в том числе распределенной) реализации операций реляционной алгебры. Проведен сравнительный анализ предложенного алгоритма и классического алгоритма оптимального поиска неявных Don't Care значений. В ходе сравнительного анализа формально доказана корректность предложенного алгоритма. Показано, что предложенный алгоритм, по сравнению с классическим, имеет значительно меньшую асимптотическую сложность в худшем случае. Поиск неявных Don't Care значений в процессе проектирования интегральных схем позволяет повысить такие качества схем, как занимаемая площадь кристалла, энергопотребление, верифицируемость и надежность. Однако классический алгоритм оптимального поиска неявных Don't Care значений не применяется на практике ввиду его чрезмерно высокой вычислительной сложности. Применение алгоритмов субоптимального поиска не позволяет в полной мере реализовать возможности оптимизации интегральных схем. Реализация предложенного в работе алгоритма в системах автоматизированного проектирования интегральных схем целесообразна в силу значительно меньшей вычислительной сложности, потенциально позволяет улучшить соотношение скорости процесса разработки и качества получаемых интегральных схем в аспектах занимаемой площади кристалла, энергопотребления, верифицируемости и надежности. Предложенный подход делает возможным создание распределенной системы автоматизированного проектирования интегральных схем, что позволит повысить доступную системе вычислительную мощность и автоматизировать проектирование более сложных интегральных схем соответственно. Ключевые слова: САПР, интегральные схемы, оптимизация комбинационных схем, логические сети, частично определенные булевы функции, неявные Don't Care значения, ODC, реляционная теория, реляционная алгебра, естественное соединение.
RELATIONAL THEORY APPLICATION FOR OPTIMAL DESIGN OF INTEGRATED CIRCUITS
D.V. Demidova, b
a ITMO University, 197101, Saint Petersburg, Russia b “Intel A/O”, Ltd., 196247, Saint Petersburg, Russia, Daniil.demidov@gmail.com
Abstract. This paper deals with a method of relational theory adaptation for integrated circuits CAD systems. A new algorithm is worked out for optimal search of implicit Don’t Care values for combinational multiple-level digital circuits. The algorithm is described in terms of the adapted relational theory that gives the possibility for a very simple algorithm description for both intuitive understanding and formal analysis. The proposed method makes it possible to apply progressive experience of relational databases in efficient implementation of relational algebra operations (including distributed ones). Comparative analysis of the proposed algorithm and a classic one for optimal search of implicit Don’t Cares is carried out. The analysis has proved formal correctness of the proposed algorithm and its considerably less worst-case complexity. The search of implicit Don’t Care values in the integrated circuits design makes it easier to optimize such characteristics of IC as chip area, power, verifiability and reliability. However, the classic algorithm for optimal search of implicit Don’t Care values is not used in practice due to its very high computational complexity. Application of algorithms for sub-optimal search doesn’t give the possibility to realize the potential of IC optimization to the full. Implementation of the proposed algorithm in IC CAD (a.k.a., EDA) systems is adequate due to much lower computational complexity, and potentially makes it possible to improve the quality-development time ratio of IC (chip area, power, verifiability and reliability). Developed method gives the possibility for creation of distributed EDA system with higher computational power and, consequently, for design automation of more complex IC. Keywords: CAD, EDA, VLSI, optimization of combinational schemes, Boolean networks, partially defined Boolean functions, implicit Don’t Cares, ODC, relational theory, relational algebra, natural join.
Введение
В силу возрастающей сложности и миниатюризации, а также ускоряющихся темпов производства электронных устройств возрастают требования к занимаемой площади кристалла, энергопотреблению, верифицируемости, надежности и скорости разработки интегральных схем (ИС). Неотъемлемой частью процесса проектирования ИС является решение задачи оптимизации логических схем, причем противоречивые ограничения требуют создания многоуровневых логических схем. Однако поиск оптимальной многоуровневой логической схемы неприемлемо сложен, поэтому на практике решается задача поиска субоптимальной схемы, а многие исследования направлены на разработку методов и эвристик, позволяющих снизить сложность решаемой задачи и приблизить результат к оптимальному [1–5].

110

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics

2014, № 5 (93)

Д.В. Демидов
Одним из ключевых моментов при оптимизации многоуровневых логических схем является поиск так называемых неявных Don't Care (безразличных или DC) значений, который, с одной стороны, позволяет существенно приблизиться к оптимальному решению, но, с другой стороны, заключает в себе значительную часть сложности исходной задачи [6].
Автором было замечено, что используемые при решении этой задачи структуры данных по своей семантике весьма близки к отношениям, используемым в теории реляционных баз данных. Алгоритмы работы с такими структурами хорошо проработаны как теоретически, так и практически, что потенциально позволяет сократить сложность поиска DC-значений, а также разработать распределенную версию алгоритма.
В работе предложен алгоритм оптимального поиска неявных DC-значений, описанный в терминах реляционной теории, адаптированной к задачам систем автоматизированного проектирования интегральных схем (САПР ИС), и доказана корректность последнего. Показано, что для предложенного алгоритма вычислительная сложность в худшем случае значительно ниже, чем для классического (экспоненциальная сложность против более чем факториальной).
Возможно внедрение результатов предлагаемой работы в существующие САПР ИС, что позволит ускорить (соответственно удешевить) и повысить качество разработки ИС (в том числе сократить занимаемую площадь кристалла и энергопотребление, повысить верифицируемость и надежность ИС [7–12]). На основе предложенного подхода к адаптации реляционной теории возможно создание распределенной САПР ИС, что позволит автоматизировать проектирование более сложных ИС, требующее высокой вычислительной мощности.
Объект исследования
В работе исследуется алгоритм оптимального поиска неявных DC-значений, применяемый на одном из этапов оптимизации многоуровневых комбинационных схем – неотъемлемой части проектирования ИС. В силу противоречивых требований к ИС используются многоуровневые комбинационные схемы, позволяющие производить минимизацию как по площади (занимаемой схемой), так и по задержке (при которой схема работает корректно). Математически многоуровневые комбинационные схемы представляют в виде логических сетей [13, 14] – ациклических ориентированных графов, которые подробно описаны в следующем разделе.
Процесс оптимизации многоуровневой комбинационной схемы является итерационным [1–5, 14, 15]. Основные этапы данного процесса показаны на рис. 1.

Рис. 1. Основные этапы процесса оптимизации многоуровневых комбинационных схем. Этапы, на которых используются исследуемые алгоритмы, выделены цветом

На этапе оптимизации структуры сети изменяется структура графа, представляющего логическую сеть (объединяются или разделяются узлы), и процесс, в основном, направлен на минимизацию задержки схемы.
На этапе оптимизации узлов сети структура графа остается неизменной, а изменяется внутреннее представление узлов, и процесс направлен на минимизацию площади (занимаемой схемой) и косвенно энергопотребления. Данный этап разделяется на два подэтапа – выделение неявных DC-значений и двухуровневую оптимизацию. На подэтапе двухуровневой оптимизации происходит собственно оптимизация внутреннего представления узла с применением точных (например, метод Квайна–Мак-Класки) или эвристических (например, используемых в семействе программ Espresso) алгоритмов [13–16]. Однако, если не выполнять предшествующий подэтап выделения неявных DC-значений, данный подэтап оперирует

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, № 5 (93)

111

ИСПОЛЬЗОВАНИЕ РЕЛЯЦИОННОЙ ТЕОРИИ ПРИ ОПТИМАЛЬНОМ...

только информацией о внутреннем представлении узла, не учитывая структуру сети, и ограничен в возможностях оптимизации. Кроме того, выполнение подэтапа выделения неявных DC-значений позволяет упростить генерацию тестов единичного отказа, а соответственно, повышает верифицируемость и надежность конечной ИС [7–12].

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

Как упоминалось выше, многоуровневую комбинационную схему представляют в виде логической сети – ориентированного ациклического графа, в котором:
 выделена специальная вершина «Primary Inputs», имеющая только исходящие дуги, помеченные литералами, обозначающими входы схемы;
 выделена специальная вершина «Primary Outputs», имеющая только входящие дуги, помеченные литералами, обозначающими выходы схемы;
 прочие вершины помечены булевыми функциями общего вида, представленными в некоторой канонической форме;
 дуги между прочими вершинами помечены литералами, обозначающими внутренние переменные – выходные значения и аргументы для булевых функций, помечающих начальные вершины и конечные вершины дуги соответственно.
Способы представления булевой функции f : Bn  B, B  0,1 в узле можно разделить на два

больших класса: бинарные диаграммы решений (БДР или BDD) и структуры, задающие дизъюнктивную

или конъюнктивную нормальную форму (ДНФ или КНФ) функции (например, Positional Cube Notation).

В настоящей работе рассматриваются способы, задающие ДНФ функции. Семантически такие способы

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

ной форме:

 S  2LB , S 

l n,

sS l,ns

где L  a,b, c – множество литералов; s – терм ДНФ; l – значение аргумента обозначаемого лите-

ралом l .
В действительности для задаваемой функций обычно существует такое множество DC f значений
аргументов, что значение выхода функции неважно. Примерами причин существования подобных входных значений являются следующие ситуации:  некоторые сочетания входных значений могут быть запрещенными и, при корректной работе окру-
жения схемы, никогда не будут поданы на ее входы (например, незаданные коды операций);  в соответствии с некоторым протоколом при определенных условиях (например, схема находится в
состоянии сброса или определенном режиме) некоторые выходы схемы могут быть проигнорированы окружением схемы.
Если множество DC f не пусто, говорят, что функция f определена частично. Математически

частично определенная булева функция f задается парой  fON , fOFF  обычных (полностью определен-

ных) булевых функций при выполнении условия x. fON (x)  fOFF (x) , где fON – ON-set, определяющий значения аргументов x , при которых f (x) должна равняться логической единице, а fOFF – OFF-set, определяющий значения аргументов x , при которых f (x) должна равняться логическому нулю. Тогда

можно определить функцию fDC (x)  fON (x)  fOFF (x) , такую, что DCf  x : fDC (x) . Также можно
сказать, что частично определенная функция задает множество функций
  F  f :  fON (x)  f (x)  fOFF (x)  f (x) , среди которых производится выбор наилучшей альтерна-
тивы на подэтапе двухуровневой оптимизации.

Неявные Don't Care значения. Классический алгоритм поиска

Для каждого узла f сети множество DC-значений определяется как объединение пяти подмно-
жеств: DC f  XCDC f  CDC f  SDC f  ODC f  XODC f (рис. 2). Здесь XCDC f и XODCf – так назы-
ваемые внешние (external) DC-значения, которые задаются инженером для всей схемы (в явном виде или выделяются из описания схемы на уровне регистровых передач (register transfer layer, RTL)). Примеры причин, по которым возникают XCDC f и XODCf соответственно, были приведены в предыдущем раз-
деле. Оставшиеся три множества – SDCf , CDC f и ODC f – называют внутренними или неявными

112

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics

2014, № 5 (93)

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

Рис. 2. Подмножества множества DC-значений для узла f логической сети

SDCf – Satesfability Don't Cares, определяют для узла f комбинации значений его входных и вы-
ходных переменных (аргументов и собственно значений функции), которые являются запрещенными (никогда не наблюдаются при корректной работе узла) в силу зависимости выходного значения от входного. Данное подмножество DC-значений не использует информации о структуре сети, но используется для
вычисления прочих DC-значений. Вычисляются SDCf  ( f , x) : fSDC ( f , x) следующим образом:

fSDC ( f , x)  f (x)  f .

(1)

CDC f – Controlobility Don't Cares, определяют для узла f комбинации значений его входных пе-

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

CDCf  x : fCDC (x) на основе определенных выше SDCg :

fCDC (x)  z  inputs( f ).

gSDC ,

ginputs*( f )

(2)

где inputs( f ) – множество входных переменных узла (аргументов функции) f ,

inputs*( f )  inputs( f ) 

inputs*(g) – транзитивное замыкание последних, а выражение вида

ginputs( f )

x . y(x, z) вычисляется как y x  y x  y(1, z)  y(0, z) .

ODC f – Observability Don't Cares, определяют для узла f комбинации значений его входных пе-

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

ODCf  x : fODC (x) следующим образом:

fODC

(x)



z



inputs(

f

)

.

houtputs*(

f

  )

h f

  

,

(3)

где outputs( f ) — множество конечных узлов, выходных дуг узла f ,

outputs*( f )  outputs( f ) 

outputs*(g) – транзитивное замыкание последних, а h f обозна-

goutputs( f )
чает так называемую булеву производную функции h по переменной f .

Булева производная h f является функцией от inputs* (h) f и возвращает единицу, если изме-

нение значения f приводит к изменению h , и ноль – в противном случае. Если f входит в h в явном

виде ( f  inputs(h) ), то h f вычисляется как булева разность: h f  h f . Если же h зависит от f косвенно (через другие функции), то необходимо применять цепное правило (chaining rule):

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, № 5 (93)

113

ИСПОЛЬЗОВАНИЕ РЕЛЯЦИОННОЙ ТЕОРИИ ПРИ ОПТИМАЛЬНОМ...

h f



  

h g1



g1 f



h gn



gn f



 





2h g1g2



g1 f



g2 f



2h g1g3



g1 f



g3 f

  



  

  Ginputs(h) 

Gh g
gG



gG

g f

  

.

Адаптированная реляционная теория

В данном разделе описан используемый в работе частный случай реляционной теории, адаптированной к задачам САПР ИС, и семантика отношений и некоторых операторов реляционной алгебры в
контексте решаемой задачи. Будем называть отношением R пару h,T  , где h  2L , L  a,b,c – под-
 множество литералов, называемое заголовком, и T  t  B' h – множество кортежей размера h , задан-

ных на расширенном булевом множестве B'  0,1, , в которое включено специальное значение  , на-
зываемое телом. Отношение R можно интерпретировать как некоторую булеву функцию R  f : B h  B , заданную следующей ДНФ:

 x, если tx  1

f (x) 

x, если tx  0 .

tR

xh

 

1,

если

tx





 

Над отношениями можно производить ряд операций; в данной работе используются проекция

 R, селекция  R , переименование  R , объединение A B и две модификации естественного

h' p(h)

x: f (h)

соединения – A  B и A hB . Первые три операции взяты из реляционной алгебры без каких-либо

изменений; остальные операции имеют небольшие изменения, позволяющие естественным образом отобразить их на операции булевой алгебры над соответствующими функциями и, в то же время, сохранить все основные свойства операций.
В классической реляционной алгебре операция объединения разрешена только для отношений с одинаковыми заголовками и возвращает отношение с тем же заголовком и объединением тел, а операция естественного соединения объединяет кортежи двух отношений, если они строго равны по всем общим атрибутам [17–19]. В адаптированной реляционной алгебре разрешается объединять отношения с разными заголовками, при этом значения «недостающих» атрибутов картежей принимаются равными  , а операция естественного соединения игнорирует значения атрибутов, равные  :
 A  B  C  t TA t TB x  hC tx ~ tx   s TC  sx  select(tx ,tx ) ,

где x ~ y   x  y   x     y   , select(x,)  x и select(, y)  y .

Вторая модификация естественного соединения A hB , названная ограниченным естественным

соединением, вводится аналогичным способом с заменой

x~ y

на

x

~h

y



x x

~ 

y, y,

если 

x

 h 
иначе



y



h

.

В таком случае перечисленные операции можно интерпретировать следующим образом (таблица).

Реляционная алгебра Объединение
Естественное соединение
Проекция

AB A  B
R
hx

Дизъюнкция

Булева алгебра

A B

Конъюнкция

AB

Квантор существования

x. R  R x  R x

Селекция

 Rx



π
hx

R
x~1

;

 Rx




hx

R
x~0

Кофактор Шеннона

R x;

R
x

114

Таблица. Интерпретация основных операций адаптированной реляционной алгебры
Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics
2014, № 5 (93)

Д.В. Демидов

 Определим понятие «функционального» заголовка отношения R как fhR  y  hR : Ry  Ry    ,
где   – пустое отношение (с пустым телом). Тогда можно также интерпретировать отношение R отно-
 сительно атрибута y  fhR как частично определенную функцию R y  Ry , Ry . Также легко пока-
зать, что будут верны следующие тождества:

R  R y y;

R y

R ;
y: y y

F  G g  G g  F f , если f  fhF , g  fhG , f  hG , g  hF .

(4) (5)

Описание предлагаемого алгоритма поиска неявных DC-значений

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

 руется пара fON  f  fDC , fDC , являющаяся входом для следующего подэтапа в процессе оптимизации

 сети. В предлагаемом алгоритме для каждого узла f вначале предполагается пара fON  f , fOFF  f

(т.е. предполагается, что DC f пусто), а затем fON и fOFF уточняются, и на вход следующего подэтапа

 передается пара fON  f  fDC , fOFF  f  fDC (для алгоритмов из семейства Espresso в действительно-

сти необходимо передать любые две функции из тройки  fON , fOFF , fDC  [13–15]). Таким образом, DC f
не конструируется в явном виде, что во многом определяет более низкую вычислительную сложность. Описание предлагаемого алгоритма в терминах адаптированной реляционной теории состоит из
трех шагов: первый шаг является подготовительным, второй неявно рассчитывает CDC f для каждого

узла f , а третий – ODC f :

1. для каждого узла f  R составить отношение R  ρ R  ρ R ,

f :1 f :0

где R 

ρ , R  R ;

tTR xt x: x

2. рекурсивно, начиная с вершины «Primary Inputs» (от входов схемы к выходам) для всех смежных

вершин произвести естественное соединение соответствующих отношений и спроецировать резуль-

тат на конечную вершину;

3. рекурсивно, начиная с вершины «Primary Outputs» (от выходов схемы к входам) для всех смежных

вершин произвести естественное соединение соответствующих отношений, ограниченное по поме-

чающему дугу литералу, и спроецировать результат на начальную вершину.

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

только на первой итерации процесса оптимизации логической сети. Кроме того, так как логическая сеть

на первой итерации получена из RTL-описания схемы и обычно ее узлы помечены булевыми функциями

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

влияет на асимптотическую сложность всего алгоритма в целом, что является важным преимуществом

предлагаемого алгоритма.

Доказательство корректности предлагаемого алгоритма

В силу ограничений на объем настоящей работы доказательства приведены в сжатом виде. Под корректностью предлагаемого алгоритма подразумевается то, что для заданной логической сети он рассчитывает в точности то же множество DC f , что и классический алгоритм (с той лишь разни-
цей, что предлагаемый алгоритм рассчитывает DC f неявно, см. предыдущий раздел).
Докажем корректность расчета CDC f , т.е. докажем, что, согласно (2), для





 f  

π
hF

 

F



  

ginputs*(

f

G
)

  

 

верно fDC  z  inputs( f ).

gSDC .

ginputs*( f ) f

(6)

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, № 5 (93)

115

ИСПОЛЬЗОВАНИЕ РЕЛЯЦИОННОЙ ТЕОРИИ ПРИ ОПТИМАЛЬНОМ...

Рассмотрим отрицание правой части тождества (6) и перепишем его в терминах реляционной алгебры (см. (1), (4) и таблицу):

  z  inputs( f ).

gSDC  z  inputs( f ).

ρ G  z : z  inputs( f ).

ρG 

ginputs*( f )

ginputs*( f ) g : g

ginputs*( f ) g : g









   π 

ρ G  π

ρ G  π

G .

hF  ginputs*( f ) g:g 

hF

 

ginputs*(

f

) g : g

 

hF

 

ginputs*(

f

)

 

Теперь рассмотрим

      fON , fOFF  

F  fD C , F  fD C 

ρ
f :1

Ff

 DC

ρ
f :0

Ff

 DC

 F  DC , где DC  fDC ,


т.е. выполняется тождество f   F  π 

 G  , что и требовалось доказать.

hF

 

ginputs*(

f

)

 

Докажем корректность расчета ODC f . Заметим, что если f  fhF , то в результирующее отноше-

ние входят только те картежи из отношения F , для которых атрибут f в отношении G имеет значение,

отличное от  , т.е. g f  1 .

Аналогично, если f  fhF и g  fhG , то

 π F  f G gH
hF

f



 

z



:

z

 inputs(

f

).

fON



g f



h g

,

z

:

z

 inputs(

f

).

fOFF



g f



h g

  

.

Учитывая (5), получим, что F  f G1  f G2  F  f G , где



G

g



G1  G2

g



 





g1  g2 , g1  g2 ,
g2  g1,

если g   
 если g  fhG2 , g  hG1  hG2 ;
если g  fhG1

тогда

g
    goutputs*( f ) f

 F  f G1 g1

H1,1 h1,1 

g1   f G2

g2

H2,1 h2,1 

g2  .

Преобразуем (3) следующим образом:

fODC



z



inputs(

f

)

.

goutputs*(

f

  )

g f

 





 

z

:

z

 inputs(

f

).
goutputs*(

f

  )

g f

  



z

:

z

 inputs(

f

).
goutputs*(

f

)

g f

,

тогда для f  , вычисляемого согласно третьему шагу предлагаемого

  fON , fOFF   fON  fODC , fOFF  fODC , что доказывает корректность расчета ODC f .

алгоритма,

Сравнение вычислительной сложности предложенного и классического алгоритмов

Произведем оценку асимптотической вычислительной сложности в худшем случае для классиче-
ского и предложенного алгоритмов. Пусть логическая сеть – граф G  V, E – имеет V  m вершин, а

каждая вершина vi ,i  0, m 1 имеет inputs(vi )  ni входных дуг (рáвно аргументов соответствующей

булевой функции, рáвно мощность заголовка соответствующего отношения) и ti , ti  2ni 1 термов ДНФ,

задающей булеву функцию (рáвно количество кортежей в соответствующем отношении). Будем обозна-

чать

n



max
i

ni

.

Рассмотрим классический алгоритм. В сложности fSDCvi (ni ) расчета SDCvi (см. (1)) доминирует

   сложность расчета отрицания vi :

fSDCvi  O niti

O

n 2ni 1
i

, причем результирующая ДНФ будет иметь

116

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics

2014, № 5 (93)

Д.В. Демидов

ni 1 аргументов и до 2  ti термов. Сложность расчета CDCvi (см. (2)) в худшем случае складывается из
сложности расчета SDCvi для m вершин и сложности квантора всеобщности по m 1  n 1Om n
переменным (что в худшем случае сводится к конъюнкции 2mn2 ДНФ по два терма):
    fCDCvi  O m  n2n  O 22mn . Наихудший случай для расчета ODCvi достигается при такой конфигу-
рации графа, что ni  i и максимальная длина пути в графе – m . Тогда сложность задается рекуррент-

ным соотношением fODC (i)  g(i) 

i k 1

fODC

(i



k)

 Cik

,

g



O

 

i

2i 2 1

1

 

.

Точно

решить

данное

соотно-

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

ODCvi

и всего классического алгоритма не лучше чем

O

 

m!

m2m2

1

1

 

.

Анализ сложности предложенного алгоритма значительно проще, причем асимптотическая слож-

ность расчета CDCvi и ODCvi совпадают. Достаточно заметить, что в худшем случае необходимо произ-

 вести естественное соединение отношений для всех пар vi , v j вершин графа, причем сложность есте-

 ственного соединения в худшем случае будет составлять O ti  t j . Таким образом, асимптотическая

сложность

предложенного

алгоритма

в

       O i, j ti t j  O E  2n  2n  O m2  22n  O m2  2m .

худшем

случае

составляет

Заключение

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

Литература

1. De Micheli G. Synchronous logic synthesis: algorithms for cycle-time minimization // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1991. V. 10. N 1. P. 63–73.
2. Hachtel G.D., Rho J.K., Somenzi F., Jacoby R. Exact and heuristic algorithms for the minimization of incompletely specified state machines // Proc. of European Conference on Design Automation. Amsterdam, Netherlands, 1992. P. 184–191.
3. Bogatyrev V.A., Bogatyrev S.V., Golubev I.Yu. Optimization and the process of task distribution between computer system clusters // Automatic Control and Computer Sciences. 2012. V. 46. N 3. P. 103–111.
4. Sentovich E.M., Singh K.J., Lavagno L., Moon C., Murgai R., Saldanha A., Savoj H., Stephan P.R., Brayton R.K., Sangiovanni-Vincentelli A.L. SIS: A System for Sequential Circuit Synthesis. Technical Report UCB/ERL M92/41, Electronics Research Lab, Univ. of California, Berkeley, 1992.
5. Pederson D.O. The VIS Group. VIS: Verification Interacting with Synthesis, 1995 [Электронный ресурс]. Режим доступа: http://embedded.eecs.berkeley.edu/Respep/Research/vis, свободный. Яз. англ. (дата обращения 04.12.2013).
6. Bartlett K.A., Brayton R.K., Hachtel G.D., Jacoby R.M., Morrison C.R., Rudell R.L., SangiovanniVincentelli A., Wang A. Multi-level logic minimization using implicit don’t cares // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1988. V. 7. N 6. P. 723–740.
7. Fujiwara H. Logic Testing and Design for Testability. Cambridge: MIT Press, 1985. 304 p. 8. Chang A.C.L., Reed I.S., Beans A.V. Path sensitization, partial boolean difference and automated fault di-
agnosis // IEEE Transactions on Computers. 1972. V. C-21. N 2. P. 189–195. 9. Bogatyrev V.A. Exchange of duplicated computing complexes in fault-tolerant systems // Automatic Con-
trol and Computer Sciences. 2011. V. 45. N 5. P. 268–276. 10. Bogatyrev V.A. Fault tolerance of clusters configurations with direct connection of storage devices // Au-
tomatic Control and Computer Sciences. 2011. V. 45. N 6. P. 330–337.

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, № 5 (93)

117

ИСПОЛЬЗОВАНИЕ РЕЛЯЦИОННОЙ ТЕОРИИ ПРИ ОПТИМАЛЬНОМ...

11. Богатырев В.А., Богатырев С.В. Критерии оптимальности многоуровневых отказоустойчивых компьютерных систем // Научно-технический вестник СПбГУ ИТМО. 2009. № 5 (63). С. 92–97.
12. Богатырев В.А., Богатырев А.В. Функциональная надежность систем реального времени // Научнотехнический вестник информационных технологий, механики и оптики. 2013. № 4 (86). С. 150–151.
13. Muroga S., Kambayashi Y., Lai H.C., Culliney J.N. Transduction method – design of logic networks based on permissible functions // IEEE Transactions of Computers. 1989. V. 38. N 10. P. 1404–1424.
14. Lin B., Touati H.J., Newton A.R. Don’t care minimization of multi-level sequential logic networks // Proc. IEEE International Conference on Computer-Aided Design. 1990. P. 414–417.
15. Brayton R.K., Hachtel G., McMullen C., Sangiovanni-Vincentelli A. Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, 1985. 206 p.
16. Theobald M., Nowick S.M., Wu T. Espresso-HF: a heuristic hazard-free minimizer for two-level logic // Proceedings - Design Automation Conference. Las Vegas, USA, 1996. P. 71–76.
17. Codd E.F. A relational model of data for large shared data banks // M.D. Computing. 1998. V. 15. N 3. P. 162–166.
18. Abiteboul S., Hull R., Vianu V. Foundations of Databases. Addison-Wesley, 1995. 685 p. 19. Date C.J., Darwen H. Foundation for Future Database Systems: The Third Manifesto. 2nd ed. Addison-
Wesley, 2000. 608 p.

Демидов Даниил Валентинович – аспирант, Университет ИТМО, 197101, Санкт-Петербург, Россия; инженер, ЗАО «Интел А/О», 196247, Санкт-Петербург, Россия,
Daniil.demidov@gmail.com

Daniil V. Demidov

– postgraduate, ITMO University, 197101, Saint Petersburg, Russia; software engineer, “Intel A/O”, Ltd., 196247, Saint Petersburg, Russia, Daniil.demidov@gmail.com
Принято к печати 02.07.14 Accepted 02.07.14

118

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics

2014, № 5 (93)