Математический аппарат диаграммы двоичного выбора (BDD) в настоящее время используется в различных областях науки [1, 2]. В системах проектирования цифровых сверхбольших интегральных схем (СБИС) графовый аппарат BDD применяется при верификации цифровых систем [3], программы минимизации BDD используются на этапе технологически независимой оптимизации [4] при синтезе логических схем.

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

Известны также подходы, ориентированные на заключительный этап синтеза – технологи- ческое отображение (technology mapping) на основе покрытия BDD (формул разложения Шеннона) описаниями логических элементов, в результате чего получаются структурные описания – нетлисты логических схем в заданном технологическом базисе, часто называемом целевой библиотекой логического синтеза.

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

Задача BDD-минимизации

BDD-минимизация булевых функций основана на разложении Шеннона. Разложением Шеннона булевой функции f(x) = f(x1, …, xn) по переменной xi является представление f(x) в виде f(x) = f0 Ú xif1.

Каждый из коэффициентов (cofactors) f0 = = f(x1, …, xi–1, 0, xi+1, …, xn), f1 = f(x1, …, xi–1, 1, xi+1, …, xn) может быть разложен по одной из переменных из множества {x1, …, xi–1, xi+1, …, xn}. Процесс разложения коэффициентов заканчивается, когда все n переменных будут использованы для разложения. В процессе разложения либо на его последнем шаге некоторые коэффициенты могут вырождаться до констант 0, 1. На каждом шаге разложения осуществляется сравнение полученных коэффициентов на равенство и из множества равных коэффициентов оставляется один. Под BDD понимается ориентированный ациклический граф, задающий последовательные разложения Шеннона булевой функции f(x1, …, xn) по всем ее переменным x1, …, xn  при заданном порядке (перестановке) переменных, по которым проводятся разложения. Функциональная вершина, соответствующая функции f, называется корнем, листовым вершинам соответствуют константы 0, 1. Далее для системы булевых функций f(x)  = (f1(x), …, fm(x)), x = (x1, …, xn), будут рассматриваться BDD, построенные по общей для всех компонентных функций fi(x) перестановке переменных. Иногда в литературе BDD такого вида называются совместными. Если исходная система функций представлена в виде системы дизъюнктивных нормальных форм (ДНФ), заданной на общем множестве элементарных конъюнкций, то в результате BDD-оптимиза­ции матричная форма исходной системы функций заменяется графом BDD, каждой вершине которого соответствует полная либо сокращенная (редуцированная) формула разложения Шеннона. Пример графа BDD, построенного для системы (ДНФ)

булевых функций (n = 4, m = 3), приведен на рисунке 1. Матричная форма (табл. 1) рассматриваемой системы ДНФ булевых функций состоит из троичной матрицы Tx задания элементарных конъюнкций в виде троичных векторов и булевой матрицы Bf вхождений конъюнкций в ДНФ компонентных функций.

Данному графу BDD (рис. 1), построенному по перестановке переменных, со- ответствуют 12 формул разложения Шеннона (^ обозначает инверсию, * – конъюнкцию, + – дизъюнкцию в языке SF, являющемся внутренним языком пакетов [5, 6]):

f1 = ^x3*sf0 + x3*sf1; f2 = ^x3*sf2 + x3*sf3;

f3 = ^x3*sf4 + x3*sf5; sf0 =^x2*^x4 + x2*sf9;

sf4 = ^x2*sf6 + x2*sf14; sf2 = ^x2*sf6 + x2*x4;

sf3 = ^x2*x4 + x2; sf5 = x2*^x4;

sf1 = x2*sf6; sf14 = ^x1*^x4 + x1*x4;

sf9 = ^x1*x4; sf6 = ^x1*x4 + x1*^x4.

Данные формулы содержат 9 операций дизъюнкции и 20 операций конъюнкции. Функциональные вершины нижнего (неконстантного) уровня BDD равны переменной либо ее инверсии, в примере это функциональные вершины x4, . В виде уравнений такие функции не будут записываться, поэтому число уравнений многоуровневого представления обычно меньше сложности BDD на одну либо две функциональные вершины. Под сложностью SBDD в литературе обычно понимается число функциональных вершин BDD.

BDD задает в виде графа последовательность разложений Шеннона исходной функции и получаемых коэффициентов разложения по некоторой перестановке переменных. Минимизация сложности BDD основана на том, что в процессе разложения могут появляться одинаковые коэффициенты разложения не только у одной, но и у нескольких (либо даже у всех) компонентных функций. Хорошо известно, что от перестановки переменных, по которым ведется разложение, зависит сложность (число вершин) BDD, поэтому основной задачей компактного представления булевой функции (либо системы функций) в виде BDD является нахождение перестановки, дающей минимальное число вершин графа BDD. Далее под BDD-минимизацией будет пониматься оптимизация многоуровневых представлений систем булевых функций, соответствующих сокращенным упорядоченным BDD, то есть ROBDD (Reduc­ed Ordered BDD). Подробное описание ROBDD дано в [1]. Далее под BDD будут пониматься ROBDD.

Задача 1 (BDD-минимизации). Для заданной системы ДНФ булевых функций найти такую перестановку  переменных, по которой будет получена BDD минимальной сложности.

Задача BDD-минимизации имеет достаточно богатую историю, аппарат BDD в настоящее время широко используется при решении SAT-проблем [7] многими исследователями. Оптимизации BDD-представлений систем полностью определенных булевых функций посвящено много работ, их обзоры и библиографию можно найти в [2, 8–10]. Не претендуя на полноту, сделаем краткий обзор.

Предшествующие работы. Появлению BDD предшествовало создание бинарных программ для представления булевых функций [11] и граф-схем решений [12]. Бинарные программы [13] содержат только два оператора: присвоения значений 0, 1 и условного перехода «если … то». Каждому оператору присваивалась метка, при выполнении программы для вычисления значения булевой функции пе- реходы осуществляются на метки. По сути такая модель задает ориентированный граф BDD в другой форме. BDD является ориентированным графом, который может интерпретироваться как орграф с помеченными вершинами и дугами, пометки дуг могут отсутствовать, но порядок (сначала младший потомок, затем старший) может быть установлен по умолчанию. Для целей проектирования логических схем каждую вершину BDD удобно интерпретировать как мультиплексор; корневая вершина в данном случае соответствует выходному полюсу логической схемы, на котором реализуется функция, представленная BDD. Так как каждая вершина BDD может быть реализована мультиплексором с одним управляющим входом, синтез каскадных схем в базисе таких мультиплексоров по существу может быть отнесен к проблематике BDD, в таких методах также возникала проблема выбора нахождения лучшей перестановки переменных. Для мультиплексоров с несколькими управляющими входами это была проблема разбиения входных переменных на непересекающиеся блоки [14].

BDD-структуры данных. Термин BDD ввел Ш. Акерс и показал, что путям BDD от корневых вершин к листовым соответствуют ортогональные элементарные конъюнкции – непересекающиеся кубы [15]. Огромный интерес к BDD возник в связи с работой [16], в которой предложены эффективные алгоритмы для сокращения BDD и выполнения логических (двухместных) операций над BDD. Статья оказалась настолько актуальной, что стала наиболее цитируемой в информатике, поскольку революционизировала структуры данных, используемые для представления булевых функций [1, с. 303]. Суть этих алгоритмов сводится к выполнению сначала операции слияния BDD (получению совместной BDD-системы функций), а затем логических операций в листовых вершинах, после чего выполнялось сокращение BDD [4]. Подробное описание алгоритмов над структурами BDD дано в [1], там же приведены различные прикладные задачи, где может использоваться аппарат BDD, в том числе для задач астрономической сложности.

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

BDD в формальной верификации цифровых систем. Области применения BDD расширились, этот аппарат явился вычислительной основой решения задач верификации параллельных систем с конечным числом состояний на основе метода model checking, что позволило увеличить сложность анализируемых систем в миллионы миллионов раз [2, с. 295]. В работе [2] приводится много примеров применения BDD, там же указываются и некоторые из модификаций аппарата BDD. В [3] аппарат BDD применяется для целей верификации и тестирования цифровых систем.

BDD и SAT-проблемы. В настоящее время проблематика BDD связана также с решением SAT-проблем [7, 17]. Аппарат BDD был обобщен на случай конечнозначных функций, появились разнообразные обобщения классических BDD [18]. Перспективным признается применение BDD при решении SAT-задачи (задачи «выполнимость») [2, с. 329], а также идей BDD для решения логических уравнений [19].

BDD в синтезе логических схем. В области автоматизации проектирования цифровых систем применение BDD позволило достичь значительных успехов в формальной верификации алгоритмических описаний цифровых систем. Однако использование BDD в проектировании цифровых систем не ограничивается только верификацией. Компактность и удобство оперирования BDD привлекли их в качестве структур данных в системах автоматизированного проектирования цифровых систем на СБИС. Минимизация BDD стала одним из основных видов технологически независимой оптимизации в промышленных синтезаторах логических схем [3]. Она стала заменять классическую логическую минимизацию [20, 21] двухуровневых (И-ИЛИ) представлений дизъюнктивных нормальных форм, обычно представляемых в виде троичных и булевых матриц. Многоуровневые скобочные представ- ления комбинационной логики – булевы сети [22], вершины которых соответствуют логическим функциям и операциям, успешно стали заменяться BDD-представлениями. Ос- новные усилия были направлены на различные алгоритмы (например, [23–26] и др.) нахождения перестановок переменных, по которым строятся BDD, то есть на решение задачи BDD-минимизации. Кроме технологически независимой оптимизации, BDD стали использоваться и при технологическом отображении при синтезе структур FPGA [27] и синтезе схем из библиотечных элементов. В работе [28] рассматриваются задачи поиска на BDD дизъюнктивного, конъюнктивного и «сумма по моду- лю 2» разложений подфункций, а также задачи факторизации (выделения одинаковых подвыражений). В работе [29] предложено оптимизировать булевы сети, находя не только одинаковые подфункции при разложении Шеннона скобочного представления системы функций, а не матричной формы системы ДНФ булевых функций, но и одинаковые узлы.

Еще одним направлением применения BDD является схемная реализация BDD, при которой решаются проблемы сокращения энергопотребления [30, 31]. Обычно здесь учитывается вероятность появления единичных значений входных сигналов, что влияет на перестановку переменных при построении BDD [4]. Получение коэффициентов разложения Шеннона позволяет записать и другие виды разложения по одной переменной. Использование коэффициентов разложения по двум переменным и соответствующее представление, названное BBDD (Biconditional Binary Decision Diagrams, BBDD – диаграмма двоичного выбора с двумя условиями), изучаются в [18]. Поиск лучшей перестановки для схемной реализации зависит от формы представления исходной системы функций, поэтому различаются алгоритмы для матричных форм и алгоритмы для многоуровневых представлений, которые получаются записью уравнений по нетлистам схем. В этом случае говорят о поиске перестановки для описания «с учетом структуры схемы». Речь идет о том, что трудно сравнить на равенство многоуровневые представления коэффициентов, ведь для сравнения их подфункций целесообразно получать какую-либо каноническую форму, например, полином Жегалкина, как это сделано в [32].

Современные синтезаторы логических схем, например LeonardoSpectrum, имеют в своем составе BDD-оптимизацию (об этом кратко сообщается в технической документации), однако информация о реализованных методах и алгоритмах не приводится. Там же отмечается, что для схем умножителей BDD не может быть построена. Однако в кни- ге [1, с. 271] приводятся цифры (более 136 миллионов вершин) размерности BDD для умножителей, выполняющих перемножение чисел, представленных 16-разрядными двоичными кодами.

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

Алгоритмы и программы минимизации BDD-представлений систем булевых функций

Описшем алгоритмы и реализующие их программы, строящие оптимизированные BDD-представления по исходным матричным формам систем ДНФ на языке SF – это известные программы BDD_OPT [4, с. 195], BDD_Energy [4, с. 206] и новая программа BDD_Builder.

Алгоритм и программа BDD_Builder

Эвристический алгоритм решения задачи 1, реализованный в программе BDD_Builder, является итерационным и выполняется до тех пор, пока текущая система функций (коэффициентов разложений) не выродится до констант 0, 1. На первой итерации в качестве текущей берется исходная система функций, для которой выполняется переход к полиномиальному представлению каждой функции в виде полинома Жегалкина [32].

На каждой итерации j (j = 1, …, n) выполняются следующие шаги.

Шаг 1. Выбор переменной xj, по которой производится разложение Шеннона всех функций текущей системы.

1.1. Построение разложений Шеннона по каждой из переменных x1, x2, …, xn каждой из ДНФ текущей системы функций системы, то есть получение ДНФ коэффициентов, не равных 0. Исключение из рассмотрения коэффициентов, равных 0.

1.2. Проверка полученных полиномов Жегалкина на равенство, в результате чего из всего множества ДНФ, представляющих коэффициенты, формируется множество  попарно различных подфункций – коэффициен- тов разложения.

1.3. Исключение из дальнейшего рассмотрения коэффициентов, равных константе 1.

1.4. Оценка переменных, от которых зависят функции текущей системы. Каждая переменная  текущей системы оценивается числом  – мощностью  =  множества  различных коэффициентов, полученных при разложении всех функций текущей системы по переменной xi.

1.5. В качестве переменной xj для разложения Шеннона на итерации j выбирается переменная xi, оцениваемая минимальным числом . Если таких переменных несколько, выбирается первая по порядку. Переход на шаг 2.

Шаг 2. Построение разложений Шеннона текущей системы функций и формирование системы функций для итерации j + 1.

2.1. Построение разложений Шеннона функций текущей системы (на итерации j) по выбранной переменной xi, то есть получение ДНФ коэффициентов, не равных 0. Исключение из рассмотрения коэффициентов, равных 0.

2.2. Проверка полученных подфункций на равенство и формирование множества  попарно различных коэффициентов.

2.4. Исключение из множества  (то есть из дальнейшего рассмотрения) коэффициентов, равных 1.

2.5. Проверка, является ли множество  пустым, то есть остались ли в нем коэффициенты, не равные константе 1. Если  оказалось пустым, осуществляется переход на шаг 3. В противном случае множество подфункций из  является текущей системой функций для итерации j + 1.

Шаг 3. Конец.

Программа BDD_Builder позволяет работать с внутренними данными (подфункциями), представленными как полиномами Жегалкина, так и в виде ДНФ, использует распараллеливание вычислений на ядра процессора как на трудоемком этапе 1.4 алгоритма, так и на начальном этапе получения полиномов Жегалкина по ДНФ каждой из функций.

Алгоритм и программа OPT_BDD

Алгоритм выбора перестановки аргументов подробно описан в [4] и состоит в последовательном применении трех эвристик. Каждая эвристика применяется итерационно до тех пор, пока очередная итерация не даст уменьшения сложно- сти BDD. Для каждой из рассматриваемых перестановок подсчитывается сложность BDD.

Эвристика 1 (перестановка одного аргумента xi с правым соседом). Исходной является начальная перестановка . Аргументы x1, …, xn рассматриваются поочередно. Сначала аргумент x1 меняется позицией с правым аргументом x2 (осуществляется транспозиция элементов перестановки), затем x1 меняется позицией с правым соседом x3 и т.д., пока x1 не окажется на последнем месте. Среди пройденных выбирается лучшая перестановка (лучшей перестановке соответствует BDD меньшей сложности). Она является начальной для последующего движения аргумента x2, при этом x2 помещается на первую позицию и двигается путем перестановки с правым соседом на последнюю позицию и так далее для оставшихся аргументов x3, …, xn. Поочередное движение всех аргументов составляет одну итерацию применения эвристики 1. Если итерация применения эвристики 1 уменьшает сложность BDD, то выполняется следующая итерация. Если же итерация не приводит к уменьшению сложности BDD, то осуществляется переход к применению эвристики 2.

Эвристика 2 (попарная перестановка). Берется лучшая перестановка., полученная в результате применения эвристики 1. Очередная рассматриваемая перестановка отличается от предыдущей переменой мест только двух аргументов, пока не будет найдена новая лучшая перестановка. Если найдена лучшая перестановка, процесс попарной перестановки повторяется уже для новой лучшей перестановки. Эвристика 2 прекращает работу, если после рассмотрения всех попарных перестановок сложность BDD не уменьшается.

Эвристика 3 (оконная перестановка). Исходной является лучшая перестановка Xbest2, полученная в результате применения эвристики 2. Окно представляет собой четыре последовательно расположенных аргумента áxi, xi+1, xi+2, xi+3ñ, внутри которого производятся все 4! = 24 перестановки четырех аргументов.

Затем окно перемещается на один аргумент вправо, получается новое окно áxi+1, xi+2, xi+3, xi+4ñ, внутри которого опять осуществляются все перестановки. Сдвиг окна до последней позиции и перебор внутри него всех перестановок свидетельствуют об окончании одной итерации применения эвристики 3. Лучшая перестановка является начальной для следующей ите- рации применения эвристики 3.

Если итерация не приводит к уменьшению сложности BDD, полученная в результате применения эвристики 3 перестановка является результирующей, именно по ней и строится BDD.

Алгоритм и программа BDD_Energy

Алгоритм, реализованный в программе BDD_Energy, ориентирован на уменьшение энергопотребления логической схемы, построенной по минимизированному BDD-описанию, и основан на переборе случайных перестановок, для каждой из которых строится BDD и оценивается ее сложность SBDD. При этом учитываются вероятности единичных значений сигналов входных переменных. Подробно алгоритм описан в [4]. Во всех экспериментах вероятность появления единичных значений входных переменных полагалась равной 0,5, чтобы оценить эффективность алгоритмов перебора случайных перестановок (без учета «энергетического качества» входных переменных) на сложность SBDD и на сложность синтезируемых логических схем.

Задача минимизации сложности булевой сети

Рассматриваются булевы сети, представляющими функциями вершин которых могут быть бинарные логические операции И (*, конъюнкция), ИЛИ (+, Ú, дизъюнкция), а также унарная операция НЕ (^, инверсия). Сложность булевой сети оценивается суммарным числом бинарных логических операторов, содержащихся в ней. Инверсии переменных при оценке сложности булевой сети не принимаются во внимание. Данная оценка сложности булевой сети хорошо согласуется с такой известной в литературе оценкой сложности алгебраического представления булевой функции, как общее число литералов булевых переменных, содержащихся в нем [22].

Задача 2. Задано многоуровневое представление системы f(x) = (f1(x), …, fm(x)), x = (x1, x2,…, xn) полностью определенных булевых функций в виде взаимосвязанных логических формул. Каждая из формул имеет вид ДНФ. Требуется минимизировать сложность булевой сети, представляющей систему функций f(x).

В работе [29] предложено проводить минимизацию булевых сетей (решать задачу 2) на основе разложения Шеннона и на нахождении одинаковых (и взаимно инверсных) подвыражений, реализуемых узлами булевой сети, для чего была разработана соответствующая программа BoolNet_Opt. Применяя ее к формулам разложения Шеннона, соответствующим графу BDD, можно получить следующие формулы минимизированной булевой сети:

f1 = t7 + t8; t7 = x3*t9; t8 = ^x3*t11;

f2 = t12 + t13; t12 = x3*t14; t13 = ^x3*t16;

f3 = t17 + t18; t17 = x3*t19; t18 = ^x3*t21;

t9 = x2*t22; t14 = x2 + x4; t19 = x2*^x4;

t11 = t25 + ^t14; t25 = x2*t40; t16 = t30 + t31;

t30 = x2*x4; t31 = ^x2*t22; t21 = t35 + t31;

t35 = x2*t37; t22 = t40 + t41; t40 = x4*^x1;

t41 = ^x4*x1; t37 = t46 + t47; t46 = x4*x1;

t47 = ^x4*^x1;

Формулы содержат 9 операций дизъюнкции и 16 операций конъюнкции и получены для перестановки переменных. Булева сеть, соответствующая данным формулам, изображена на рисунке 2.

При BDD-минимизации проводится поиск одинаковых подфункций – коэффициентов разложения Шеннона, а при минимизации булевых сетей – одинаковых подвыражений, соответствующих узлам сети. Заметим, что, применив программу BoolNet_Opt к исходной системе ДНФ, заданной в таблице 1, получаем булеву сеть другой структуры, но той же сложности. Данный пример демонстрирует, что число двухвходовых логических операций может быть сокращено путем применения дополнительной оптимизации к формулам, полученным в результате BDD-минимизации, что и было доказано в результате эксперимента на потоке примеров практической размерности.

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

Для оценки эффективности программ BDD-минимизации при синтезе схем из библиотечных КМОП-элементов были проведены вычислительные эксперименты.

Эксперимент 1. Сравнение эффективности программ BDD-оптимизации на потоке промышленных примеров.

Исходными описаниями блоков комбинационной логики являлись системы ДНФ булевых функций на языке SF [6], взятые из библиотеки примеров схем [33]. Для каждой из систем выполнялась BDD-минимизация с помощью трех программ – BDD_OPT, BDD_Energy, BDD_Builder. Программа BDD_Energy выполнялась для вероятностей 0,5 появления единичных значений для каждой из входных переменных системы ДНФ. Минимизированные описания конвертировались в VHDL-описания и подавались на вход синтезатора Leonardo­Spectrum. Для каждого из примеров синтез осуществлялся с одними и теми же опциями управления синтезом и для одной и той же целевой библиотеки синтеза. Целевой являлась библиотека проектирования заказных цифровых КМОП СБИС, состав библиотеки приведен в работе [4]. Этапы эксперимента 1 показаны на рисунке 3.

Результаты эксперимента 1 на потоке промышленных примеров приведены в таблицах 2 и 3 для программ BDD_Energy и BDD_Builder. Для программы BDD_OPT задавалось фиксированное время – 10 минут, результаты выполнения программы BDD_OPT оказались неконкурентоспособными, поэтому не приводятся.

Примеры c окончанием «_matr» – это системы ДНФ, полученные из соответствующих исходных многоуровневых представлений систем функций; Sin_16 – это задание в виде таблицы истинности 16-битного приближения тригонометрической функции y = sinx; примеры Syst4, Syst8 взяты из практики промышленного проектирования цифровых схем.

В таблицах 2 и 3 (и далее) n – число аргументов; m – число функций системы ДНФ, заданной на k общих элементарных конъюнкциях; SBDD – сложность BDD; V + & – число операций конъюнкции и дизъюнкции в формулах разложений Шеннона; t – время выполнения программы на компьютере с процессором Intel(R) Core i5-2320 и тактовой частотой 3 GHz; SASIC – суммарная площадь элементов схемы в условных единицах; t – задержка схемы (нс); a – число случайно генерируемых перестановок входных переменных для программы BDD_Energy. В таблице 3 символом «П» помечены три примера, оптимизированные программой BDD_Builder в режиме распараллеливания вычислений.

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

Были проведены аналогичные эксперименты на потоке псевдослучайных примеров систем ДНФ, характеризуемых различными средними значениями числа конъюнкций, числа литералов в конъюнкциях и средних значений числа вхождений конъюнкций в ДНФ функций системы. Результаты эксперимента 2 приведены в таблицах 4 и 5, где n1 – среднее число литералов в элементарной конъюнкции; m1 – среднее число вхождений конъюнкции в ДНФ функций системы. Для первого псевдослучайного примера GenP_1 число n столбцов троичной матрицы Tx, задающей конъюнкции, равно 15, число k строк матриц Tx, Bf  равно 664, среднее число n1 определенных (0, 1) элемен- тов в строке матрицы Tx равно 10, среднее число единичных значений в строке матрицы Bf равно 3.

Эксперимент 3. Изучение возможности улучшения результатов BDD-оптимизации с помощью оптимизации булевых сетей.

После проведения синтеза в экспериментах 1 и 2 выбирались те BDD-описания, которые приводили к схемам меньшей площади, и для этих BDD-описаний выполнялась программа BoolNet_Opt оптимизации булевых сетей, после чего осуществлялся повторный синтез схем. Результаты этого эксперимента приведены в таблице 6, где символом «*» помечены несколько лучших решений, полученных программой BDD_OPT.

Для псевдослучайных примеров значительно лучшие результаты синтеза показывает синтезатор LeonardoSpectrum при использовании своих встроенных программ технологически независимой оптимизации. BDD-минимизация для псевдослучайных примеров неэффективна, если синтез вести в LeonardoSpectrum.

Эксперимент 4. Исследование эффективности раздельной и совместной минимизации в классе ДНФ для псевдослучайных примеров [21, 22].

Результаты эксперимента 4, представленные в таблице 7, показывают, что для псевдослучайных примеров более эффективна минимизация в классе ДНФ (раздельная либо совместная) при синтезе схем из библиотечных элементов.

Эксперимент 5. Сравнение сложности решений, полученных программой BDD_Builder, с известными решениями из [25].

Результаты эксперимента 5 на потоке промышленных примеров приведены в таблице 8. Они свидетельствуют о том, что программа BDD_Builder конкурентоспособна с программой из [25].

Проведенные экспериментальные исследования показали, что в практике проектирования целесообразно использовать две взаимно дополняющие друг друга программы – BDD_Energy и BDD_Builder. Программа BDD_Builder является быстродействующей, позволяет распараллеливать вычисления и за короткое время получать приемлемое решение. Если задать большое число случайных перестановок, то не исключено, что программа BDD_Energy может получить лучшее решение, чем программа BDD_Builder, однако для этого может понадобиться много времени, так как время вычислений для программы BDD_Ener­gy определяется размерностью задачи и числом заданных (генерируемых случайным образом) перестановок. Дополнительное улучшение решений (уменьшение площади и задержки схемы) достаточно часто можно получить, применяя программу BoolNet_Opt к минимизированным BDD-описаниям систем функций.

Заключение

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

Литература

1.    Кнут Д.Э. Комбинаторные алгоритмы; в кн. Искусство программирования; [пер. с англ.]. М.: Вильямс, 2013. Т. 4А. Ч. 1. 960 с.

2.    Карпов Ю.Г. Model Checking. Верификация параллельных и распределенных программных систем. СПб: БХВ-Петербург, 2010. 560 с.

3.    Чэнь М., Цинь К., Ку Х.-М., Мишра П. Валидация на системном уровне. Высокоуровневое моделирование и управление тестированием; [пер. с англ.]. М.: Техносфера, 2014. 296 с. DOI: 10.1007/ 978-1-4614-1359-2.

4.    Бибило П.Н. Применение диаграмм двоичного выбора при синтезе логических схем. Минск: Беларус. навука, 2014. 231 с.

5.    Бибило П.Н., Авдеев Н.А., Кардаш С.Н., Кириенко Н.А., Ланкевич Ю.Ю., Логинова И.П., Романов В.И., Черемисинов Д.И., Черемисинова Л.Д. Система логического проектирования функциональных блоков заказных КМОП СБИС с пониженным энергопотреблением // Микроэлектроника. 2018. Т. 47. № 1. С. 72–88. DOI: 10.7868/S0544126918010076.

6.    Бибило П.Н., Романов В.И. Логическое проектирование дискретных устройств с использованием продукционно-фреймовой модели представления знаний. Минск: Беларус. навука, 2011. 280 с.

7.    Biere A., Heule M., van Maaren H., Walsh T., eds. Frontiers in Artificifl Intelligents and Applications. Handbook of Satisfiability. IOS Press, 2009, 980 p. DOI: 10.3233/978-1-58603-929-5-3.

8.    Drechsler R., Becker B. Binary Decision Diagrams: Theory and Implementation. Springer, 1998, 210 p.

9.    Bryant R.E., Meinel C. Ordered Binary Decision Diagrams. Logic Synthesis and Verification. Kluwer Acad. Publ., 2002, pp. 285–307. DOI: 10.1007/978-1-4615-0817-5_11.

10. Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications. Springer, 1998, 267 p. DOI: 10.1016/s0898-1221(99)90407-8.

11. Lee C.Y. Representation of switching circuits by binary-decision programs. Bell Systems Technology J., 1959, vol. 38, pp. 985–999.

12. Блох А.Ш. Граф-схемы и их применение. Минск: Вышэйш. школа, 1975. 302 с.

13. Кузнецов О.П. О программной реализации логических функций и автоматов. Ч. I. Анализ и синтез бинарных программ // Автоматика и телемеханика. 1977. № 7. С. 163–174.

14. Бутов А.А. Синтез многовыходных комбинационных схем с использованием мультиплексоров // Кибернетика. 1980. № 3. С. 63–70.

15. Akers S.B. Binary decision diagrams. IEEE Transactions on Computer, 1978, vol. 27, no. 6, pp. 509–516. DOI: 10.1109/TC.1978.1675141.

16. Bryant R.E. Graph-based algorithms for boolean functions manipulation. IEEE Transactions on Computer, 1986, vol. 35, no. 8, pp. 677–691. DOI: 10.1109/TC.1986.1676819.

17. Ebendt R., Fey G., Drechsler R. Advanced BDD Optimization. Springer, 2005, 222 p. DOI: 10.1007/ b107399.

18. Amaru L.G. New Data Structures and Algorithms for Logic Synthesis and Verification. Springer, 2017, 156 p. DOI: 10.1007/978-3-319-43174-1_5.

19. Игнатьев А.С., Семенов А.А. Алгоритмы работы с ROBDD как с базами булевых ограничений // Прикладная дискретная математика. 2010. T. 7. № 1. С. 86–104.

20. Brayton K.R., Hactel G.D., McMullen C.T., Sangiovanni-Vincentelli A.L. Logic Minimization Algorithm for VLSI Synthesis. Kluwer Academic Publishers, 1984, 194 p.

21. Торопов Н.Р. Минимизация систем булевых функций в классе ДНФ // Логическое проектирование: сб. науч. тр. 1999. Вып. 4. С. 4–19.

22. Брейтон Р.К., Хэчтел Г.Д., Санджованни-Винчентелли А.Л. Синтез многоуровневых комбинационных логических схем // ТИИЭР. 1990. Т. 78. № 2. С. 38–83.

23. Rudell R. Dynamic variable ordering for ordered binary decision diagrams. Proc. IEEE/ACM ICCAD, Santa Clara, 1993, pp. 42–47. DOI: 10.1109/ICCAD.1993.580029.

24. Ebendt R., Gunther W., Drechsler R. An improved branch and bound algorithm for exact BDD minimization. Computer-Aided Design of Integrated Circuits and System, 2003, vol. 22, no. 12, рр. 1657–1663. DOI: 10.1109/TCAD.2003.819427.

25. Ishiura N., Sawada H., Yajima S. Minimization of binary decision diagrams based on exchanges of variables. Proc. IEEE Int. Conf. on Computer-Aided Design, 1991, pp. 472–475. DOI: 10.1109/ICCAD.1991. 185307.

26. Bollig B., Lobbing M., Wegener I. Simulated annealing to improve variable orderings for OBDDs. Proc. IWLS, pp. 1–10.

27. Chang S.-C., Marek-Sadowska M., Hwang T. Technology mapping for TLU FPGA’s based on decomposition of binary decision diagrams. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1996, vol. 15, no. 10, pp. 1226–1235. DOI: 10.1109/43.541442.

28. Yang C., Ciesielski M. BDS: A BDD-based logic optimization system. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002, vol. 7, no. 21, pp. 866–876. DOI: 10.1109/TCAD.2002.1013899.

29. Бибило П.Н., Ланкевич Ю.Ю. Логическая минимизация булевых сетей с использованием разложения Шеннона // Информатика. 2019. Т. 16. № 2. С. 73–89.

30. Dutta A., Baishnab K.L., Chaudhary S. A new evolutionary algorithm based BDD optimization for area and power. IJEEE, 2010, vol. 3, no. 3, pp. 147–160.

31. Lindgren P., Kerttu M., Thornton M., Drechsler R. Low power optimization technique for BDD mapped circuits. Proc. Conf. ASPDAC-01, 2001, pp. 615–621. DOI: 10.1109/ASPDAC.2001.913377.

32. Бибило П.Н., Ланкевич Ю.Ю. Использование полиномов Жегалкина при минимизации многоуровневых представлений систем булевых функций на основе разложения Шеннона // Программная инженерия. 2017. Т. 8. № 8. С. 369–384. DOI: 10.17587/prin.8.369-384.

33. The Tests in the Monograph «Logic Minimization Algorithms for VLSI Synthesis». URL: http://www1.cs.columbia.edu/~cs6861/sis/espresso-examples/ex (дата обращения: 20.01.2020).

References

1. Knuth D.E. Combinatorial Algorithms. In: The Art of Computer Programming, Pearson Education, Inc., 2011, vol. 4A, 883 p. (Russ. ed.: Moskow, 2013, 960 p.).
2. Karpov Yu.G. Model Checking. Verification of Parallel and Distributed Software Systems.
   St. Petersburg, 2010, 560 p. (in Russ.).
3. Chen M., Qin X., Koo H.-M., Mishra P. System-Level Validation. High-Level Modeling and Directed Test Generation Techniques. Springer, 2013, 250 p. (Russ. ed.: Moskow, 2014. 296 p.). DOI: 10.1007/978-1-4614-1359-2.
4. Bibilo P.N. Applying Binary Selection Diagrams in the Logic Circuit Synthesis. Minsk, 2014, 231 p. (in Russ.).
5. Bibilo P.N., Avdeev N.A., Kardash S.N., Kirienko N.A., Lankevich Yu.Yu., Loginova I.P., Roma-
   nov V.I., Cheremisinov D.I., Cheremisinova L.D. A System for logical design of custom CMOS VLSI functional blocks with reduced power consumption. Microelectronics, 2018, vol. 47, no. 1, pp. 72–88 (in Russ.). DOI: 10.7868/S0544126918010076.
6. Bibilo P.N., Romanov V.I. Logical Design of Discrete Devices Using the Production-Frame Knowledge Representation Model. Minsk, 2011, 280 p. (in Russ.).
7. Biere A., Heule M., van Maaren H., Walsh T., eds. Frontiers in Artificifl Intelligents and Applications. Handbook of Satisfiability. IOS Press, 2009, 980 p. DOI: 10.3233/978-1-58603-929-5-3.
8. Drechsler R., Becker B. Binary Decision Diagrams: Theory and Implementation. Springer, 1998,
   210 p.
9. Bryant R.E., Meinel C. Ordered Binary Decision Diagrams. Logic Synthesis and Verification. Kluwer Acad. Publ., 2002, pp. 285–307. DOI: 10.1007/978-1-4615-0817-5_11.
10. Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications. Springer, 1998, 267 p. DOI: 10.1016/s0898-1221(99)90407-8.
11. Lee C.Y. Representation of switching circuits by binary-decision programs. Bell Systems Technology J., 1959, vol. 38, pp. 985–999.
12. Blokh A.Sh. Graph Diagrams and their Application. Minsk, 1975, 302 р. (in Russ.).
13. Kuznetsov O.P. On implementation of logical functions and automata by programs. Pt. I. Analysis and synthesis of binary-decision program. Autom. Remote Control, 1977, vol. 38, no. 7, pp. 1077–1087 (in Russ.).
14. Butov A.A. Synthesis of multi-output combinational circuits using multiplexers. Kibernetika, 1980,
    no. 3, pp. 63–70 (in Russ.).
15. Akers S.B. Binary decision diagrams. IEEE Transactions on Computer, 1978, vol. 27, no. 6,
    pp. 509–516. DOI: 10.1109/TC.1978.1675141.
16. Bryant R.E. Graph-based algorithms for boolean functions manipulation. IEEE Transactions on Computer, 1986, vol. 35, no. 8, pp. 677–691. DOI: 10.1109/TC.1986.1676819.
17. Ebendt R., Fey G., Drechsler R. Advanced BDD Optimization. Springer, 2005, 222 p. DOI: 10.1007/
    b107399.
18. Amaru L.G. New Data Structures and Algorithms for Logic Synthesis and Verification. Springer, 2017, 156 p. DOI: 10.1007/978-3-319-43174-1_5.
19. Ignatev A.S., Semenov A.A. The algorithms for working with ROBDD as Boolean constraint databases. Prikladnaya Diskretnaya Matematika, 2010, vol. 7, no. 1, pp. 86–104 (in Russ.).
20. Brayton K.R., Hactel G.D., McMullen C.T., Sangiovanni-Vincentelli A.L. Logic Minimization Algorithm for VLSI Synthesis. Kluwer Acad. Publ., 1984, 194 p.
21. Toropov N.R. Minimization of Boolean function systems in the DNF class. Logicheskoe Proektirovanie Proc., 1999, iss. 4, pp. 4–19 (in Russ.).
22. Brayton R.K., Hachtel G.D. Multilevel logic synthesis. Proc. IEEE, 1990, vol. 78, no. 2, рр. 264–300. DOI: 10.1109/5.52213.
23. Rudell R. Dynamic variable ordering for ordered binary decision diagrams. Proc. IEEE/ACM ICCAD, 1993, pp. 42–47. DOI: 10.1109/ICCAD.1993.580029.
24. Ebendt R., Gunther W., Drechsler R. An improved branch and bound algorithm for exact BDD minimization. Computer-Aided Design of Integrated Circuits and Systems, 2003, vol. 22, no. 12,
    рр. 1657–1663. DOI: 10.1109/TCAD.2003.819427.
25. Ishiura N., Sawada H., Yajima S. Minimization of binary decision diagrams based on exchanges of variables. Proc. IEEE Int. Conf. on Computer-Aided Design, 1991, pp. 472–475. DOI: 10.1109/ICCAD.1991.
    185307.
26. Bollig B., Lobbing M., Wegener I. Simulated annealing to improve variable orderings for OBDDs. Proc. IWLS, 1995, pp. 1–10.
27. Chang S.-C., Marek-Sadowska M., Hwang T. Technology mapping for TLU FPGA’s based on decomposition of binary decision diagrams. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1996, vol. 15, no. 10, pp. 1226–1235. DOI: 10.1109/43.541442.
28. Yang C., Ciesielski M. BDS: a BDD-based logic optimization system. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002, vol. 7, no. 21, pp. 866–876. DOI: 10.1109/TCAD.2002.
    1013899.
29. Bibilo P.N., Lankevich Yu.Yu. Logical optimization of Boolean nets using Shannon expansion. Informatics, 2019, vol. 16, no. 2, pp. 73–89 (in Russ.).
30. Dutta A., Baishnab K.L., Chaudhary S. A new evolutionary algorithm based BDD optimization for area and power. IJEEE, 2010, vol. 3, no. 3, pp. 147–160.
31. Lindgren P., Kerttu M., Thornton M., Drechsler R. Low power optimization technique for BDD mapped circuits. Proc. Conf. ASPDAC-01, 2001, pp. 615–621. DOI: 10.1109/ASPDAC.2001.913377.
32. Bibilo P.N., Lankevich Yu.Yu. The use of Zhegalkin polynomials for minimization of multilevel representations of Boolean functions based on Shannon expansion. Software Engineerin, 2017, vol. 8, no. 8,
    pp. 369–384 (in Russ.). DOI: 10.17587/prin.8.369-384.
33. The Tests in the Monograph «Logic Minimization Algorithms for VLSI Synthesis». Available at: http://www1.cs.columbia.edu/~cs6861/sis/espresso-examples/ex (accessed January 20, 2020).