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

При минимизации многоуровневых скобочных представлений на основе методов факторизации выделяются общие части как элементарных конъюнкций и дизъюнкций, так и алгебраических подвыражений, что является одним из видов совместной минимизации многоуровневых описаний схем и оказалось полез- ным для уменьшения площади схем заказных СБИС. В качестве структур данных при решении задач факторизации использованы булевы сети, представленные ориентированными бесконтурными графами DAG (Directed-Acyclic-Graph). При декомпозиции систем функций были разработаны различные методы совместной декомпозиции, при которой одна и та же промежуточная функция может использоваться совместно – участвовать в разложениях (суперпозициях) нескольких функций исходной системы.

Несколько последних десятилетий в качестве основных методов технологически независимой оптимизации многоуровневых представлений систем булевых функций применяются методы минимизации графовых BDD (Binary Decision Diagram)-представлений [1]  и их модификаций, при этом внимание чаще уделяется совместной минимизации [1, 2] и декомпозиции [3, 4] BDD-представлений систем функций. Следует заметить, что структуры данных в виде BDD-представлений широко используются также при верификации логических схем, построении тестов и решении сложных задач в различных областях информатики. Размерность задач проектирования СБИС возрастает в связи с совершенствованием техно- логических процессов производства СБИС и уменьшением технологических норм [1]. Решение задач логической оптимизации начинается совместно с задачами топологического и физического проектирования СБИС с широким использованием программ проверки выполнимости конъюнктивной нормальной формы (КНФ) булевых функций, называемых SAT-solvers (Boolean Satisfiability problem – задача выполнимости булевой формулы, представленной в виде КНФ) [5–7].

После BDD для задания систем булевых функций появились новые структуры данных, которые используются при решении задач технологически независимой логической оптимизации [5–7]. Это AIG (AND-Inverter-Graph), XMG (XOR-Majority-Graph) [8], MIG (Majority-Inverter-Graph) [9–11], XAIG (XOR-AND-Inverter-Graph) [12]. Структуры AIG положены в основу системы ABC (http://www.eecs. berkeley.edu/˜alanmi/abc) – известной академической системы оптимизации представлений систем булевых функций и синтеза логических схем. Характерной особенностью решаемых с помощью этих структур оптимизационных задач является то, что они используются для совместной реализации систем булевых функций. Раздельная минимизация многоуровневых представлений и выделение подсистем для их совместных реализаций не изучались.

Одинаковость частей в таблицах истинности булевых функций привела к идее использования связанности (общности) областей определений булевых функций при синтезе многовыходных комбинационных схем. Выделение связанных подсистем функций по таблицам истинности и ДНФ функций рассматривалось  в [13]. Такой подход ограничен размерностью задач: число аргументов системы функций не превышает трех десятков. Для BDD-представ- лений задача выделения связанных по областям определения подсистем функций решалась в [13], где были предложены различные меры связанности функций, в том числе и основанная на общности заданного числа формул разложений Шеннона для всех функций выделяемой подсистемы. Такую связанность можно назвать сильной.

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

Совместная и раздельная минимизация многоуровневых представлений систем  булевых функций на основе  разложения Шеннона

BDDI-представления системы булевых функций. Под BDDI (Binary Decision Diagram with Inverse cofactors) понимается ориентированный бесконтурный граф, задающий последовательные разложения Шеннона булевой функции f(x) либо системы F = {f1(x), …, f m(x)} булевых функций по всем переменным x1, …, xn при заданном порядке (перестановке) переменных, по которым проводятся разложения, при условии нахождения пар взаимно инверсных кофакторов. Разложением Шеннона булевой функции f(x) = f(x1, …, xn) по переменной xi является представление f(x) в виде

Каждый из кофакторов (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 переменных будут использованы для разложения. Если не ищутся взаимно инверсные кофакторы, то в результате последовательных разложений Шеннона строятся ROBDD-пред- ставления (Reduced Ordered Binary Decision Diagram – сокращенная упорядоченная бинарная диаграмма решений). В ROBDD функциональная вершина реализует один кофактор, в то время как в BDDI взаимно инверсные кофакторы представляются парой взаимосвязанных вершин. Таким образом, под BDDI будут пониматься совместные ROBDD, в которых на каждом уровне найдены пары взаимно инверсных кофакторов. Алгоритм построения ROBDD описан в [2], он был модифицирован для минимизации BDDI-представлений.

Булевы сети – Bool-представления системы булевых функций. В статье рассматриваются булевы сети [2], функциями вершин которых могут быть бинарные логические операции И (конъюнкция), ИЛИ (дизъюнкция), а также унарная операция НЕ (инверсия). Логическая минимизация булевых сетей на основе разложения Шеннона описана в [2] и заключается в поиске такой перестановки участвующих в разложении переменных, при которой число литералов в булевой сети является наименьшим. Литерал – это булева переменная либо ее инверсия. Таким образом, после разложения Шеннона по очередной переменной минимизация булевой сети сводится к следующему: ищутся вершины булевой сети, опирающиеся на одинаковые подсети, после чего проводится редукция (сокращение) сети и находятся уравнения, соответствующие редуцированной сети.

Раздельная BDDI и Bool-минимизация заключаются в нахождении своей перестановки <> переменных разложения для каждой из функций f1(x), …, f m(x), в то время как при совместной BDDI- и Bool-минимизации используется одна и та же перестановка переменных разложения для всех функций системы.

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

Пусть система F = {f 1(x), …, f m(x)} булевых функций задана на общем множестве Z взаимосвязанных уравнений (формул) в булевом базисе И, ИЛИ, НЕ – это наборы формул разложений Шеннона либо наборы формул, соответствующих булевым сетям. Каждая формула из Z задает одну промежуточную (внутреннюю) булеву переменную либо функцию, которая является выходной. Обозначим через R(f j) множество всех формул, задающих промежуточные переменные, связанные с формульным заданием только одной функции f j(x), j = 1, …, m, R(f j) Í Z. Заметим, что собственно формула для выходной функции f j в R(f j) не включается. Для многоуровневого формульного представления системы F = {f 1(x) , …, f m(x)} булевых функций через R(F) = R(f 1, …, f m) = обозначим множество внутренних формул для всех функций системы.

Рассмотрим далее понятие связанности представлений функций, которую будем понимать как общность формул в заданиях функций в виде множеств взаимосвязанных алгебраических логических уравнений. Прежде всего следует отметить, что характеристика связанности трактуется как отношение между парой объектов – компонент системы, в роли которых выступает одна или несколько функций, задаваемых уравнениями рассматриваемой системы. Для определения количественных оценок связанности введем ряд обозначений. Пусть Fg,  Fh – подсистемы системы F: Fg Ì F, Fh Ì F. Назовем весом связаности подсистем Fg, Fh число

                 (1)

где через |A| обозначена мощность множества A.

В целях нормирования количественных оценок связанности наряду с весом (1) введем понятие меры M(Fg, Fh) связанности подсистем Fg , Fh, вычисляемой по формуле

           (2)

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

           (3)

Под M( f i,  f j ) понимается мера связанности многоуровневых представлений пары функций f i,  f j.

Предлагаемый далее алгоритм выделения связанных подсистем основан на последовательном пополнении уже выделенной подсистемы Fm = {f 1, …, f m}, m ³ 2, новой функцией f m+1. Под мерой связанности системы функций Fm È f m+1 будем понимать величину

   (4)

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

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

Примем, что рассматриваемая мера связанности обладает уровнем q, если справедливо q ≤ M(f i, f j) для связанности пары функций f i, f j или q ≤ M(F m È {f m+1}) для компонентной связанности при пополнении системы новой функцией. Далее, когда речь пойдет о связанности систем или подсистем функций, будет подразумеваться связанность их многоуровневых представлений с оценкой по мере связанности последнего проведенного пополнения.

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

Таблица 1

Таблица истинности системы полностью определенных булевых функций

Table 1

Truth table of a system of fully defined  Boolean functions

x1 x2 x3 x4	f 1 f 2 f 3 f 4
0  0  0  0 0  0  0  1 0  0  1  0 0  0  1  1 0  1  0  0 0  1  0  1 0  1  1  0 0  1  1  1 1  0  0  0 1  0  0  1 1  0  1  0 1  0  1  1 1  1  0  0 1  1  0  1 1  1  1  0 1  1  1  1	0  0  1  1 1  1  0  0 1  0  0  0 1  1  0  0 0  0  1  1 1  1  0  0 0  1  1  1 1  1  1  0 0  0  1  1 1  0  0  0 1  1  0  0 1  1  0  0 0  0  1  1 1  0  1  1 0  0  0  1 1  0  1  0

Для данной системы функций BDDI-представление состоит из 12 формул:

; ;

; ;

; ; ;       (5); ;

; ;

Множество R(f 1, f 2, f 3, f 4) формул, задающих функции системы F={f 1, f 2, f 3, f 4}, состоит из восьми формул, так как первые четыре формулы из (5) не включаются в множество R(f 1, f 2, f 3, f 4). Отдельные функции системы заданы следующими множествами: R(f 1) = {s1}, R(f 2) = {s2, s3, s6, s8}, R(f 3) = {s4, s5, s6, s7}, R(f 4) = = {s1, s4, s6}. Здесь и далее будем задавать множества формул, перечисляя только их левые части. Подсистема {f 3,  f 4} функций имеет вес связанности S(f 3,  f 4) = 2 (в задании функций имеются две общие формулы – s4, s6. По формуле (3) мера связанности M(f 3, f 4) = 2/4 = 0,5, так как |R(f 3)| = 4, |R(f 4)| = 3 и поэтому max(|R(f 3)|, |R(f 4)|) = max(4,3) = 4. Легко заметить, что пара f 2, f 3 имеет меру связанности, равную 1/4. Мера компонентной связанности (4) подсистемы {f 2, f 3} È f 4 равна 2/7, так как R(f 2,  f 3) = {s2, s3, s4, s5, s6, s7, s8}, R(f 4) = {s1, s4, s6}, R(f 2, f 3) Ç R(f 4) = {s4, s6}, |{s4, s6}| = 2, max(|R(f 2, f 3)|, |R(f 4)|) = 7. Если же к подсистеме {f 2, f 3, f 4} добавить функцию f 1, то мера ком- понентной связанности (4) системы {f 2, f 3,  f 4} È f 1 будет равна 1/7, так как подсистема {f 2, f 3, f 4} имеет одно общее уравнение s1 с функцией f 1.

Рассмотрим другое множество формул, задающих те же функции:

Как видим, каждая формула в (6) состоит только из одного булева оператора и является менее сложной (содержащей меньшее число логических операторов) по сравнению с формулами (5), задающими разложения Шеннона. Формулы (6) описывают булеву сеть, реализующую систему функций из таблицы 1.

Множества уравнений, задающие отдельные функции системы: R(f 1) = {t12, t17}; R(f 2) =  = {t1, t2, t13, t15, t17}; R(f 3) = {t3, t4, t7, t8, t9, t12, t14, t15, t17, t18}; R(f 4) = {t5, t6, t10, t11, t12, t16, t17}.

Подсистема {f 3, f 4} функций имеет вес связанности S(f 3, f 4) = 2 (в задании функций имеются две общие формулы t12 и t17) и меру связанности M(f 3, f 4) = 2/10 = 0,2, так как |R(f 3)| = 10, |R(f 4)| = 7 и max(|R(f 3)|, |R(f 4)|) = max(10,7) = 10. Примеры показывают, что различные представления (множества формул) одних и тех же функций могут иметь различные меры связанности.

Выделение подсистем с заданной  мерой связанности

Предлагаемый эвристический алгоритм является модификацией предложенного в [13] алгоритма и состоит в последовательном формировании (на каждой итерации i) по текущей (остаточной) системе функций очередной подсистемы Pi функций (подсистема Pi характеризуется мерой компонентной связанности, не меньшей q). На первой итерации (i = 1) текущую систему функций образуют функции исходной системы.

На каждой итерации требуется выполнить шаги 1–3.

Шаг 1. Рассмотреть неупорядоченных пар функций {f i, f j}, i, j = 1, ..., m, i¹ j, текущей системы и найти такую пару функций L, которая имеет максимальное значение меры связанности, вычисляемое по формуле (3) и не меньшее параметра q. Если таких пар функций несколько, то выбирается первая из них. Если указанной пары функций нет, то переход на шаг 4.

Шаг 2. Составить из функций найденной на первом шаге пары L формируемую подсистему Pi, исключив выбранную пару функций L из текущей системы, и добавлять в формируемую подсистему поочередно те функции f r, которые находятся с помощью следующей эвристики: из множества функций текущей системы выбирается та функция f r, которая обеспечивает наибольшее возможное значение меры компонентной связанности (4) для подсистемы Pi È {f r}. Если таких функций несколько, то выбирается и добавляется в формируемую подсистему Pi первая из них.

Шаг 3. Если нет ни одной такой функции f r, что подсистема P i È {f r} имеет меру компонентной связанности, не меньшую q, то закончить формирование подсистемы P i и объявить не входящие в нее функции текущей подсистемой. Переход на шаг 1 для формирования подсистемы на итерации i + 1.

Шаг 4. Закончить формирование подсистем, когда все функции текущей системы будут включены в формируемые подсистемы, либо в текущей подсистеме нельзя будет найти ни одной пары функций, характеризуемых мерой (3) связанности, не меньшей q, либо в текущей системе имеется только одна функция. Конец алгоритма.

Достоинствами данного алгоритма являются его высокое быстродействие и возможность обобщения на формулы AIG, MIG, XMG, XAIG, а недостатком – зависимость от последовательности формирования результирующих выделенных подсистем. Чтобы подсчитать меру связанности результирующей выделенной подсистемы, надо знать последнюю добавляемую в подсистему функцию и, очевидно, ту подсистему, в которую она добавляется.

Приведем пример работы алгоритма на формулах (6) при значении допустимого уров- ня связанности q = 0,2 (20 %).

Шаг 1. Рассмотрим все неупорядоченные пары функций из формул (6) исходной системы и найдем для каждой из пар меру связанности (3): M(f 1, f 2) = 1/5; M(f 1, f 3) = 2/10; M(f 1, f 4) =  = 2/7; M(f 2, f 3) = 2/10; M(f 2, f 4) = 1/7; M(f 3, f 4) =  = 2/10.

Исходя из полученных оценок мер связанности пар функций при уровне связанности q = 0,2, результатом выполнения шага 1 является пара {f 1, f 4}, имеющая наибольшую меру связанности M(f 1, f 4) = 2/7.

Шаг 2. К подмножеству {f 1, f 4} функций будем добавлять поочередно функции f 2, f 3 и находить меры компонентной связанности: M({f 1, f 4} È {f 2}) = 1/7, M({f 1, f 4} È {f 3}) = 2/10. Для подсистемы ({f 1, f 4}, f 2): R(f 1, f 4) = {t5, t6, t10, t11, t12, t16, t17}, R(f 2) = {t1, t2, t13, t15, t17}, R(f 1, f 4) Ç R(f 2) = {t17}, |{t17}| = 1, max(|R(f 1, f 4)|, |R(f 2)|) = max(7,5) = 7, откуда M({f 1, f 4} È {f 2}) =  = 1/7, что меньше 0,2.

Шаг 3. Для подсистемы ({f 1, f 4}, f 3) значение M({f 1, f 4} È {f 3}) = 0,2, поэтому на шаге 3 выделенной подсистемой объявляется {f 1, f 4, f 3}. Добавить к этой подсистеме функцию f 2 не удается, так как полученное значение меры компонентной связанности будет меньше 0,2. Текущей подсистемой объявляется {f 2}, и выполняется переход на шаг 1.

Шаг 4. В текущей подсистеме остается одна функция, поэтому алгоритм прекращает работу. Результатом являются одна выделенная подсистема {f 1, f 4, f 3} и остаток – подсисте- ма {f 2}.

Если провести синтез схемы непосредственно по формулам (6) (Bool-представлению), то будет получена схема с площадью 4 336 условных единиц, состоящая из 12 элементов, задержка схемы составит 2,78 нс. Если же провести совместную минимизацию в классе булевых сетей подсистемы {f 1, f 4, f 3} и совместную минимизацию подсистемы {f 2} (для этой подсистемы совместная минимизация вырождается в раздельную одной функции), то в результате синтеза получим схему (см. рисунок) с площадью 4 262 условные единицы, состоящую из 12 элементов, задержка схемы составит 3,21 нс. Функции логических элементов схемы и их площади приведены в таблице 2. Таким образом, параметры схемы изменились – площадь схемы уменьшилась, задержка увеличилась.

Таблица 2

Функции и площади элементов КМОП логической схемы

Table 2

Functions and areas of CMOS  logic circuit elements

Элемент	Функция	Площадь
N		223
NOA		363
NAO3		491
XOR2		692
NOAA		485
NOA3		530

Если же реализовать схему по уравнениям (5) (BDDI-представлению), то получим схему с площадью 4 659 условных единиц, состоящую из  14 элементов, задержка схемы составит 1,72 нс. Данный пример показывает, что различные способы минимизации многоуровневых представлений позволяют получать схемы различной площади и задержки. Проведенные про- граммные эксперименты проверяют конкурентоспособность трех подходов к минимизации представлений на основе двух моделей – BDDI и Bool: это совместная минимизация, раздельная минимизация и выделение отдельных подсистем и их (подсистем) совместная минимизация.

Исходные данные для экспериментов

Исходными описаниями блоков комбинационной логики являлись 39 примеров систем булевых функций на языке SF [14] в виде матричных описаний систем ДНФ – SDF описаний языка SF.

В матричной форме система ДНФ

; ; ;

(7)

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

Таблица 3

Система ДНФ булевых функций

Table 3

DNF system of Boolean functions

Tx	B f
x1 x2 x3 x4	f 1 f 2 f 3 f 4
–  0  1  – 0  1  1  – –  –  –  1 1  0  1  – 1  1  0  – –  1  –  0 –  1  1  1 0  –  –  1 –  –  0  0	1  0  0  0 0  1  1  0 1  0  0  0 0  1  0  0 0  0  1  1 0  0  0  1 0  0  1  0 0  1  0  0 0  0  1  1

Заметим, что данная система ДНФ задается логическими уравнениями (формат LOG языка SF) и представляет ту же систему булевых функций, которая приведена в таблице 1. Таблице истинности соответствует система совершенных ДНФ (СДНФ), если перейти к формульной записи функций.

Из 39 примеров четыре примера (Ttt2, X1, X3, X4) многоуровневых представлений систем функций были преобразованы в матрич- ный формат SDF (добавлялось окончание имени _matr). Примеры Mult_7, Mult_8 – системы ДНФ, задающие функции семи- и вось- миразрядных умножителей. Описания функций умножителей были получены командой unmap в синтезаторе LeonardoSpectrum из схем- ных реализаций умножителей, после чего был осуществлен переход к ДНФ. Заметим, что так может быть осуществлено перепроектирование устройств комбинационной логики из одного базиса логических элементов в другой базис. Примеры Verg_1, Verg_2, Sist_4 взяты из практики проектирования цифровых устройств. Пример Psevdo_1 – сгенерированный псевдослучайный пример. Остальные примеры взяты из библиотеки примеров схем (http://www1.cs. columbia.edu/~cs6861/sis/espresso-examples/ex), представленных в формате PLA, при этом описания из формата PLA переводились в формат SDF системы FLC-2 [14]. Было установлено, что примеры GARY и IN0 задают одну и ту же систему булевых функций в виде различных систем ДНФ, то есть ДНФ с различными множествами элементарных конъюнкций.

Параметры примеров систем функций заданы в таблице 4: n – число аргументов; m – число функций системы ДНФ, заданной на  k общих элементарных конъюнкциях; Area – суммарная площадь элементов схемы в условных единицах; Delay – временная задержка схемы (нс). Если k = 2n, то исходной является матричная форма таблицы истинности системы функций. В таблицах 5–7 символом «*» выделены лучшие решения (в рамках отдельной таблицы) для испытываемого примера – меньшие значения параметров площади и временной задержки.

Организация экспериментов

В экспериментах использовались система FLC-2 [14] и следующие программы.

BDD_Builder – программа минимизации раздельных и совместных BDDI-представ- лений системы булевых функций.

BoolNetOpt2 – программа минимизации раздельных и совместных Bool-представлений системы булевых функций.

Splitter – программа выделения подсистем функций (при заданном значении q меры связанности) из совместных BDDI и из совместных Bool-представлений систем функций.

AutoSplit – программа нахождения лучшего значения q меры связанности по критерию минимальности общего числа литералов в BDDI- либо в Bool-представлениях систем функций.

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

«Представить листья сети в виде LOG» – листья иерархического описания логической сети представлялись в формате LOG (логических уравнений), пример – уравнения (7).

«Представить листья сети в виде SDF» – листья иерархического описания логической сети представлялись в виде SDF (матричных описаний), пример – таблица 3.

«Представить листья сети в виде BDDI» – каждый лист SDF иерархического описания логической сети представлялcя в виде уравнений, соответствующих BDDI-описанию, пример таких описаний – уравнения (5).

«Представить листья сети в виде Bool» – каждый лист SDF иерархического описания логической сети представлялся в виде уравнений, соответствующих Bool-описанию, пример таких описаний – уравнения (6).

Исходными для программы BoolNetOpt2 [2] являются логические уравнения, поэтому исходные матричные представления (формат SDF системы FLC-2) переводились в формат LOG логических уравнений. Для раздельной Bool-минимизации для такого перевода использовалась стратегия «Представить листья сети в виде LOG». После при раздельной BDDI-минимизации и после выделения подсистем программой Splitter проводилась их BDDI-минимизация с помощью стратегий «Представить листья сети в виде SDF» и «Представить листья сети в виде BDDI».

При Bool-минимизации отдельные функции системы (либо выделенные программой Splitter подсистемы) обрабатывались с помощью стратегий «Представить листья сети в виде SDF», «Представить листья сети в виде LOG», «Представить листья сети в виде Bool». При выполнении стратегии «Представить листья сети в виде Bool» для каждого листа в иерархическом описании схемы (листу соответствует подсистема функций) применялась программа BoolNetOpt2 со следующим ограничением – 10 минут для совместной минимизации подсистемы. При раз- дельной Bool-минимизации задавалась одна минута для минимизации булевой сети, реализующей одну функцию исходной системы.

Аппарат стратегий обеспечивал для каждой функции сети (либо подсистемы) нахождение своей перестановки переменных при BDDI- либо Bool-минимизации.

Эксперименты были организованы следующим образом. Сначала выполнялась логическая минимизация, затем минимизированные описания многоуровневых представлений систем функций конвертировались в VHDL-описания [15] и подавались на вход того же синтезатора LeonardoSpectrum, который использовался в экспериментах [2]. Для каждого из примеров синтез осуществлялся с одними и теми же опциями управления синтезом и для одной и той же, что и в работе [2], целевой библиотеки синтеза – библиотеки проектирования заказных цифровых КМОП СБИС.

Эксперименты

Эксперимент 1. Совместная и раздельная минимизация в классе BDDI-представлений. При раздельной минимизации исходные матричные представления систем функций представлялись в виде логических сетей, элементами которых являются отдельные функции системы. Затем данные сети обрабатывались при помощи стратегии «Представить листья сети в виде BDDI». Для минимизации BDDI-представлений всей системы и отдельных функций использовалась программа BDD_Builder.

Эксперимент 2. Исходными для эксперимента 2 являлись совместно минимизированные BDDI-представления, для которых выполнялась программа Splitter выделения связанных подсистем функций для двух фиксированных значений меры связанности q = 10 %, q = 20 %. Полученные сети подсистем обрабатывались с помощью стратегий «Представить листья сети в виде SDF», «Представить листья сети в виде BDDI». Результаты экспериментов 1 и 2 отражены в таблице 5.

Эксперимент 3. Совместная и раздельная минимизация в классе булевых сетей (Bool-представлений). При раздельной минимизации в классе Bool-представлений элементы логической сети (отдельные функции системы) обрабатывались с помощью стратегий «Представить листья сети в виде SDF», «Представить листья сети в виде LOG», «Представить листья сети в виде Bool». Базовой программой являлась программа минимизации булевых сетей BoolNetOpt2 [2].

Под Bool-представлениями в системе FLC-2 понимаются булевы сети, описываемые логическими уравнениями с одним логи- ческим оператором дизъюнкции либо конъюнкции над двумя литералами булевых переменных.

Эксперимент 4. Исходными для эксперимента 4 являлись совместно минимизированные Bool-представления, для которых выпол- нялась программа Splitter выделения q-свя- занных подсистем функций для двух фиксированных значений меры связанности q = 5 %,  q = 20 %. Полученная сеть подсистем обрабатывалась с помощью тех же трех стратегий, что и в эксперименте 3.

Результаты экспериментов 3 и 4 сведены в таблицу 6.

Эксперимент 5. Оценка выделения связанных подсистем. Для выделения совместно минимизируемых связанных подсистем с помощью программы AutoSplit ищутся лучшие  значения параметра связанности q для BDDI-представлений путем итеративного выполне- ния программы Splitter для меры связанности  5 %, 10 %, 15 %, 20 %, ..., 95 %. Оценивается суммарное число литералов в каждой полученной логической сети, и по минимуму найденной оценки выбирается лучший вариант решения. Естественно, если для значения q меры связанности подсистемы не выделялись, то программа AutoSplit прекращала испытывать большие, чем q, значения меры связанности и переходила к выбору решения по критерию меньшего числа литералов. Полученная логическая сеть обрабатывалась с помощью тех стратегий, что и в эксперименте 2. Понятно, что выбор лучшего значения связанности целесообразно находить после выполнения синтеза схемы, но тогда трудоемкая процедура синтеза должна выполняться многократно, поэтому вычислялась погрешность d эвристического критерия «Общее число литералов» при выборе решения – лучшего результата выделения связанных подсистем. Например, в таблице 7 для примера B12 (BDDI-представление) указана погрешность d = 3,8 %. Погрешность d вычислялась следующим образом: программа Au- toSplit нашла лучшее значение q = 5 % меры связанности, программа Splitter выделила подсистемы, которые были минимизированы, синтез схемы по полученному описанию подсистем позволил получить схему с площадью Area = 15 819, однако ручной перебор значений q (табл. 5) и синтез двух схем позволили получить схему площадью Area = 15 239 для значения q = 20 %. Погрешность составила (15 819–15 239)/15 239 = 0,038, что эквивалентно 3,8 %.

Эксперимент 6. Совпадает с экспериментом 5, при этом исходными были совместно минимизированные Bool-представления, а результирующие логические сети обрабатывались с помощью тех же стратегий, что и в эксперименте 3.

Итоги экспериментов 5 и 6 отражены в таблице 7.

Обсуждение результатов экспериментов

Результаты экспериментов 1 и 2 (табл. 5) показывают, что предложенный алгоритм выделения подсистем в 13 примерах схем (из 39 примеров) позволил получить схемы меньшей площади для исходных совместных BDDI-представлений, из которых выделялись подсистемы. Для 17 примеров схем лучшие результаты показала совместная минимизация, для 10 – раздельная минимизация BDDI-представлений. Получение схем с меньшей задержкой чаще было обеспечено применением раздельной BDDI-минимизации и алгоритмом выделения подсистем.

Критерий минимальности общего числа литералов в функциональных BDDI-представ- лениях оказался эффективным при автоматическом выборе лучшего решения для программы, реализующей предложенный алгоритм выделения подсистем. Сравнение с ручным выбором лучшего значения меры связанности показало погрешность в 3,9 % для BDDI-представлений и 6,4 % для Bool-представлений (табл. 7). Программа AutoSplit обеспечила восемь лучших решений для BDDI-представлений и десять – для Bool-представлений.

Проведенные эксперименты показали, что для одной половины примеров систем функций более эффективным является аппарат минимизации на основе матричных представлений, для другой – аппарат минимизации булевых сетей.

Заключение

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

Список литературы

1. Amaru L.G. New Data Structures and algorithms for logic synthesis and verification. Springer Publ., 2017, 156 p. doi: 10.1007/978-3-319-43174-1.

2. Бибило П.Н., Ланкевич Ю.Ю. Экспериментальное сравнение эффективности алгоритмов оптимизации BDD-представлений систем булевых функций // Программные продукты и системы. 2020. Т. 33. № 3. С. 449–463. doi: 10.15827/0236-235X.131.449-463.

3. Kubica M., Kania D. SMTBDD: New form of BDD for logic synthesis. IJET, 2016, vol. 62, no. 1, pp. 33–41. doi: 10.1515/eletel-2016-0004.

4. Kubica M., Kania D. Decomposition of multi-output functions oriented to configurability of logic blocks. Bull. Pol. Acad. Sci. Tech. Sci., 2017, vol. 65, no. 3, pp. 317–331. doi: 10.1515/bpasts-2017-0036.

5. Reis A.I., Drechsler R. Advanced Logic Synthesis. Springer Publ., 2017, 232 p. doi: 10.1007/978-3-319-67295-3.

6. Lee S.-Y., Riener H., Mishchenko A., Brayton R.K., De Micheli G. A simulation-guided paradigm for logic synthesis and verification. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, vol. 41, no. 8, pp. 2573–2586. doi: 10.1109/TCAD.2021.3108704.

7. Haaswijk W., Soeken M., Mishchenko A., De Micheli G. SAT-based exact synthesis: Encodings, topology families, and parallelism. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, vol. 39, no. 4, pp. 871–884. doi: 10.1109/TCAD.2019.2897703.

8. Haaswijk W., Soeken M., Amaru L., Gaillardon P.-E., De Micheli G. A novel basis for logic rewriting. Proc. ASP-DAC, 2017, pp. 151–156. doi: 10.1109/ASPDAC.2017.7858312.

9. Soeken M., Amaru L., Gaillardon P., De Micheli G. Optimizing majority-inverter graphs with functional hashing. Proc. DATE, 2016, pp. 1030–1035.

10. Soeken M., Amaru L., Gaillardon P.-E., De Micheli G. Exact synthesis of majority-inverter graphs and its applications. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, vol. 36, no. 11, pp. 1842–1855. doi: 10.1109/TCAD.2017.2664059.

11. Riener H., Testa E., Amaru L., Soeken M., De Micheli G. Size optimization of MIGs with an application to QCA and STMG technologies. Proc. NANOARCH, 2018, pp. 157–162.

12. Harlecek I., Fiser P., Schmidt J. Are XORs in logic synthesis really necessary? Proc. IEEE 20th Int. Symposium DDECS, 2017, pp. 134–139. doi: 10.1109/DDECS.2017.7934583.

13. Бибило П.Н., Позняк А.М. Выделение подсистем связанных функций из многоуровневого представления системы булевых функций // Информатика. 2020. Т. 17. № 1. С. 63–77. doi: 10.37661/1816-0301-2020-17-1-63-77.

14. Бибило П.Н., Романов В.И. Система логической оптимизации функционально-структурных описаний цифровых устройств на основе продукционно-фреймовой модели представления знаний // Проблемы разработки перспективных микро- и наноэлектронных систем. 2020. № 4. С. 9–16. doi: 10.31114/2078-7707-2020-4-9-16.

15. Тарасов И.Е. ПЛИС XILINX. Языки описания аппаратуры VHDL и Verilog, САПР, приемы проектирования. М.: Горячая линия; Телеком, 2020. 538 с.

References

1. Amaru, L.G. (2017) New Data Structures and Algorithms for Logic Synthesis and Verification. Springer Publ., 156 p. doi: 10.1007/978-3-319-43174-1.

2. Bibilo, P.N., Lankevich, Yu.Yu. (2020) ‘Experimental investigation of effectiveness of algorithms for minimizing BDD representations of Boolean function systems’, Software & Systems, 33(3), pp. 449–463 (in Russ.). doi: 10.15827/0236-235X.131.449-463.

3. Kubica, M., Kania, D. (2016) ‘SMTBDD: New form of BDD for logic synthesis’, IJET, 62(1), pp. 33–41. doi: 10.1515/eletel-2016-0004.

4. Kubica, M., Kania, D. (2017) ‘Decomposition of multi-output functions oriented to configurability of logic blocks’, Bull. Pol. Acad. Sci. Tech. Sci., 65(3), pp. 317–331. doi: 10.1515/bpasts-2017-0036.

5. Reis, A.I., Drechsler, R. (2017) Advanced Logic Synthesis. Springer Publ., 232 p. doi: 10.1007/978-3-319-67295-3.

6. Lee, S.-Y., Riener, H., Mishchenko, A., Brayton, R.K., De Micheli, G. (2022) ‘A simulation-guided paradigm for logic synthesis and verification’, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 41(8), pp. 2573–2586. doi: 10.1109/TCAD.2021.3108704.

7. Haaswijk, W., Soeken, M., Mishchenko, A., De Micheli, G. (2020) ‘SAT-based exact synthesis: Encodings, topology families, and parallelism’, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 39(4), pp. 871–884. doi: 10.1109/TCAD.2019.2897703.

8. Haaswijk, W., Soeken, M., Amaru, L., Gaillardon, P.-E., De Micheli, G. (2017) ‘A novel basis for logic rewriting’, Proc. ASP-DAC, pp. 151–156. doi: 10.1109/ASPDAC.2017.7858312.

9. Soeken, M., Amaru, L., Gaillardon, P., De Micheli, G. (2016) ‘Optimizing majority-inverter graphs with functional hashing’. Proc. DATE, pp. 1030–1035.

10. Soeken, M., Amaru, L., Gaillardon, P.-E., De Micheli, G. (2017) ‘Exact synthesis of majority-inverter graphs and its applications’. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 36(11), pp. 1842–1855. doi: 10.1109/TCAD.2017.2664059.

11. Riener, H., Testa, E., Amaru, L., Soeken, M., De Micheli, G. (2018) ‘Size optimization of MIGs with an application to QCA and STMG technologies’, Proc. NANOARCH, pp. 157–162.

12. Harlecek, I., Fiser, P., Schmidt, J. (2017) ‘Are XORs in logic synthesis really necessary?’ Proc. IEEE 20th Int. Symposium DDECS, pp. 134–139. doi: 10.1109/DDECS.2017.7934583.

13. Bibilo, P.N., Pazniak, A.M. (2020) ‘The search for subsystems of related functions from multilevel representation of systems of Boolean functions’, Informatics, 17(1), pp. 63–77 (in Russ.). doi: 10.37661/1816-0301-2020-17-1-63-77.

14. Bibilo, P.N., Romanov, V.I. (2020) ‘The system of logical optimization of functional-structural descriptions of digital circuits based on production-frame knowledge representation model’, Problems of Advanced Micro- and Nanoelectronic Systems Development, (4), pp. 9–16 (in Russ.). doi: 10.31114/2078-7707-2020-4-9-16.

15. Tarasov, I.E. (2020) XILINX FPGA. Hardware Description Languages VHDL and Verilog, CAD, Design Techniques. Moscow, 538 р. (in Russ.).