МИКРОЭЛЕКТРОНИКА, 2015, том 44, № 5, с. 383-399
-- СХЕМОТЕХНИКА
УДК 517.98
ЭФФЕКТИВНОСТЬ ЛОГИЧЕСКОЙ ОПТИМИЗАЦИИ ПРИ СИНТЕЗЕ КОМБИНАЦИОННЫХ СХЕМ ИЗ БИБЛИОТЕЧНЫХ ЭЛЕМЕНТОВ
© 2015 г. Н. А. Авдеев, П. Н. Бибило
Объединенный институт проблем информатики НАНБеларуси Поступила в редакцию 05.05.2014 г.
Описываются результаты экспериментального сравнения программ минимизации различных форм представлений систем полностью определенных булевых функций. Эксперименты показали, что более предпочтительными при синтезе комбинационных логических схем из библиотечных элементов являются программы минимизации многоуровневых представлений на основе разложения Шеннона и декомпозиции по сравнению с программами минимизации в классе дизъюнктивных нормальных форм.
БО1: 10.7868/80544126915050026
ВВЕДЕНИЕ
Синтез комбинационных схем в заданном базисе (библиотеке) логических элементов традиционно разбивается на два больших этапа: технологически независимую оптимизацию реализуемых систем булевых функций и технологическое отображение — покрытие оптимизированных представлений описаниями библиотечных логических элементов. Решающее влияние на основные параметры (сложность, быстродействие, энергопотребление) логических схем оказывает первый этап. На данном этапе в качестве основного метода оптимизации до недавнего времени использовались методы раздельной и совместной минимизации систем булевых функций в классе дизъюнктивных нормальных форм (ДНФ). В последнее время к ним добавились методы оптимизации многоуровневых представлений на основе разложения Шеннона — так называемых диаграмм двоичного выбора (англ. Binary Decision Diagram, BDD) и методы декомпозиции, позволяющие уменьшать число аргументов реализуемых систем функций.
Создание эффективных экспертных систем автоматизированного синтеза логических схем требует знаний об областях предпочтительного использования программ технологически незави-
симой оптимизации функциональных описаний логических схем [1]. Данная работа посвящена экспериментальному сравнению эффективности программ оптимизации представлений систем булевых функций, применяемых при синтезе логических схем из элементов библиотеки проектирования отечественных заказных цифровых сверхбольших интегральных схем (СБИС). На наборе широко известных примеров показывается преимущество применения при синтезе схем программ оптимизации на основе разложения Шеннона и программ декомпозиции по сравнению с традиционными программами минимизации функций в классе ДНФ.
1. МАТРИЧНАЯ ФОРМА ЗАДАНИЯ
СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ
Булевыми называются двоичные (0, 1) функции /(х) = / (хь х2, ..., хп) двоичных (булевых) переменных х1, х2, ... х„. Под векторной булевой функцией / (х) будем понимать упорядоченную систему булевых функций /(х) = (/:(х), ..., /т(х)). Матричная форма задания векторной полностью определенной
функции/(х) = (/ 1(х), /2(х), /3(х)), где
f — X1X2X4X5X^ V X1X4X^Xfo V Х2X3X5, f — X1X4X5X^ V X1X3X5 V X-X2X3X5X^ V X-X2X4X^X^; f — X1X2X3X^ V X-X2X4X^ V X-X3X4X^ V X1X2X4X5X^ V X-X2X5 V X2X3X5
представлена в табл. 1. Эта форма состоит из троичной матрицы Тх задания элементарных конъюнкций в виде троичных векторов и булевой мат-
рицы В вхождений конъюнкций в ДНФ компонентных функций (х),] = 1, ..., т. Представление векторной функции парой матриц {Тх, В) будем
называть также матричной формой системы ДНФ булевых функций или просто системой ДНФ.
2. ЛОГИЧЕСКАЯ ОПТИМИЗАЦИЯ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ
Совместная минимизация систем булевых функций в классе ДНФ. Данный способ логической оптимизации является классическим и используется для минимизации общего числа элементарных конъюнкций, на которых заданы все функции исходной системы, и сокращения числа литералов х, х в элементарных конъюнкциях. При матричном представлении функций совместная минимизация позволяет уменьшить число
строк в матрицах Тх, Bf, увеличить число неопредел енных значений "—" в задании конъюнкций
Функции /(хь..., хм, 0, х+1, ...х„), /(хь..., хм, 1, х1+1, ...хп) в (1) называются коэффициентами разложения. Они получаются из функции /(х1,...,хп) подстановкой вместо переменной х1 константы 0 или 1 соответственно. БЭЭ задает в виде графа последовательность разложений Шеннона исходной функции и получаемых коэффициентов разложения. Минимизация сложности БЭЭ основана на том, что в процессе разложения могут появляться одинаковые коэффициенты разложения не только у одной, но и у нескольких (либо даже у всех) компонентных функций. Под совместной BDD-минимизацией в данной работе будет пони-
троичными векторами, и, возможно, уменьшить
/
число единичных значений в булевой матрице В . Методы совместной минимизации систем булевых функций широко известны в литературе [2—5]. Если провести совместную минимизацию системы ДНФ (табл. 1), то можно получить 11 (вместо 12) элементарных конъюнкций для задания ДНФ всех функций системы, минимизированная система ДНФ представлена в табл. 2.
Совместная BDD-минимизация систем булевых функций в классе многоуровневых представлений на базе разложения Шеннона.
Разложением Шеннона полностью определенной булевой функции / (х1,..., хп) по переменной Х1 называется представление / (х1,..., хп) = f в виде
(1)
маться оптимизация многоуровневых представлений систем булевых функций, соответствующих сокращенным упорядоченным BDD (англ. Reduced Ordered BDD, ROBDD). Подробное описание упорядоченных BDD дано в [6], ROBDD — в [7].
Обозначим через (xbx2,x3, x4,x5,x6) последовательность переменных, по которым проводится разложение Шеннона для векторной функции f (x), состоящей из трех компонентных функций
f , f2, f3 (табл. 1). Построенная BDD изображена на рис. 1, данной BDD соответствует многоуровневое представление
f = Xif(X1,^^^, X i 0, X(■ + 1,..., X„) V X('f (Х^..^ Xi_1,l, X(■ + 1,..., X„).
Л — 1 2 J.2 — 2 3 — 2 4
j = x1y v x1y ; j = x19 v x1y ; j = x1y v x1y ;
1 — 1 12 23—1 3 4 — 4 51—2 12 —л3 3
у = x29 v x29 ; у = x29 ; у = x2s v x2y ; у = x2y v x2y ; ф = x3s v x3s ; ф = x3A v x3s ;
3 »4 4 —л 2 2 5 — 2 1 л 1 2 — » 3 л2 3 — л4
Ф = x3A ; ф = x3A v x3s ; ф = x3s ;s = x4A ; s = x4A v x4A ; s = x4A ;
.1—1.2—1 л3 л 4 2 1 2 —
А = x5® ; А = x5® v x5; А = x5; А = x5® ; ю = x6; ю = x6.
Сложность БЭЭ оценивается числом вершин, помеченных символами функций, вершины, соответствующие аргументам, при оценке сложности БЭЭ в расчет не принимаются. Например, сложность БЭЭ (рис. 1) равна 21. Основной проблемой при построении БЭЭ меньшей сложности является выбор перестановки переменных, по которой БЭЭ строится.
Раздельная декомпозиция систем булевых функций. Пусть задано разбиение У^ множества X = = {х1,..., хп} переменных векторной булевой функции /(х) = (/:(х), ..., /т(х)) на два непересекающиеся подмножества У = {уь...,уг}, Z = {г1,..., 1п-г},
2 < г < п -1, п > 3. Обозначим через у = (у1,...,уг) вектор, полученный упорядочением переменных из подмножества У= {у1,...,уг}, а через z = (г1,..., 1п-г) -вектор, полученный упорядочением переменных из подмножества Z= {г1,...,}. Раздельной декомпозицией системы булевых функций /(х) =
= (/:(х), ..., /т(х)) по заданному разбиению У^ множества переменных X будем называть процесс построения функциональных разложений
/ \х) = / 1(у, г) = g \к1(у), г), «... (2) /т(х) = /т(у, г) = Г(Г(у), г),
Таблица 1. Система ДНФ булевых функций
Таблица 2. Минимизированная система ДНФ
7 "'Х В/ 7Х В/
Х1 Х2 Х3 Х4 Х5 Х6 /1 /2 /з Х1 Х2 Х3 Х4 Х5 Х6 /1 /2 /3
1 1 - 0 1 0 1 0 0 1 1 1 - 1 0 0 1 0
0 - - 1 0 1 1 0 0 1 1 - 0 1 0 1 0 0
0 0 1 0 0 1 0 0 1 0 1 1 0 0
- -
0 - 0 - 1 - 0 1 0
0 1 - 0 1 0 0 0 1
1 1 1 - 1 0 0 1 0
0 1 0 1 0 1 0 1 0 - 1 0 1 0 1 1
1 -
1 0 0 - - 1 0 0 1 0 - - 0 1 0 0 1
1 0 - 1 - 1 0 0 1 1 - 0 1 - 1 0 0 1
1 - 0 1 - 1 0 0 1 1 0 0 - - 1 0 0 1
0 1 - 0 1 0 0 0 1 0 - 0 - 1 - 0 1
1 0 - - 1 - 0 0 1 1 0 - - 1 - 0 0 1
- 1 0 - 1 - 1 0 1 - 1 0 - 1 - 1 0 1
где НJ (у) = (А/(у),..., к]р.(у)),] = 1, ..., т; причем для
каждой из компонентных функций /' число р] промежуточных переменных (компонент векторной функции Н (у) = (А/(у), ..., Ар (у))) является минимальным.
Раздельная декомпозиция векторной функции, заданной в табл. 1, по разбиению переменных У = {х 1, х2, х3, х4}, Z = {х5, х6} позволяет получить семь промежуточных функций на первом ярусе (входном блоке) схемы (рис. 2):
А/ = X/ X2X3X4 ;
А2 = X/ Х2Х3Х4 V Х2Х3 Х4 V X 1 Х2Х3, А3 — X/ Х4 ;
А/ — Х1Х3 Х4 V Х/Х2Х3 V Х1Х3, А2 = Х/Х2Х4 V Х1Х3 Х4 V Х1Х2Х3,
А/ — X/Х2Х3 Х4 V Х/Х2Х3Х4 V X/ Х2Х3 V Х/Х2Х4, А2 = Х/Х2Х3 Х4 V Х/Х2Х3Х4 V Х2Х3Х4 V Х/Х2Х3.
Заметим, что данные функции совместно минимизированы в классе ДНФ, а декомпозиция осуществлялась с помощью метода, описанного в [8]. Матричная форма данных функций представлена в табл. 3. Минимизированные в классе ДНФ выходные функции, зависящие от переменных Х5, Х6 и промежуточных переменных, заданы в табл. 4. Легко заметить, что каждая из функций g 1(А/, а2, А], х5,
Хб) = /\ g2 (А/2, А22, Х5, Хб) = /2, g3 (А/3, А23, Х5, Хб) = 13 при раздельной декомпозиции зависит от своего подмножества промежуточных переменных.
Функции входного, как и выходного блока разложения могут быть минимизированы в классе БЭЭ-представлений. После совместной БЭЭ-минимизации представление функций входного блока имеет вид:
А[ = х^; А2 = х2х3; А] = х1х4; А/ = х1ф11 V хдо^ А2 = хдо7 V х^3; А/3 = х^ V х^4; А^ = х^5 V х^6;
ф/ = Х2Ф7; ф2 = Х2Х3; ф3 = Х2Х4 V Х2Х3; ф4 = Х2ф8 V Х2ф9; Ф5 = Х2фп; Фб = Х2Ф7 V X2ф10; Ф7 — Х4Х3; = Х4Х3 V Х4; Ф9 = Х4Х3; ф/0 — Х4Х3; фц = Х4 V Х4Х3.
Многоуровневое БЭЭ-представление функций выходного блока после совместной БЭЭ-миними-зации имеет вид:
/1 = А/^ V А^; /2 = А^3 V А2^; /3 = А/^ V А3^; = А^ V а2^8; ^ = А^; ^ = А22%; ^ = А1х5 V А^п;
55 = А2х5; 56 = А2 511 V А2512; 57 = А3510; = А3 х5 V А3511; 59 = А3 512; 510 = Х6Х5; 511 = х6х5 V х6; 512 = х6х5.
В данном (и предыдущем) многоуровневых В рассматриваемом примере раздельная деком-представлениях не используются переименования позиция позволила уменьшить число аргументов литералов перемен
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.