МИКРОЭЛЕКТРОНИКА, 2013, том 42, № 5, с. 389-398
- СХЕМОТЕХНИКА
УДК 004.43
ИСПОЛЬЗОВАНИЕ МОДЕЛЕЙ НЕПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ ПРИ СИНТЕЗЕ СХЕМ ПО VHDL-ОПИСАНИЯМ
© 2013 г. П. Н. Бибило, А. Л. Соловьев
Объединенный институт проблем информатики НАН Беларуси E-mail: bibilo@newman.bas-net.by Поступила в редакцию 10.07.2012 г.
Предлагается заменять некоторые VHDL-конструкции функциональными моделями не полностью определенных булевых функций и систем таких функций. Показывается, что оптимизационные преобразования таких моделей позволяют во многих случаях получать в результате автоматизированного синтеза более быстродействующие логические схемы по сравнению со схемной реализацией исходных VHDL-конструкций. Представлены результаты соответствующих экспериментов.
DOI: 10.7868/S0544126913050025
ВВЕДЕНИЕ
Современные синтезаторы осуществляют синтез логических схем компилятивным способом — на этапе высокоуровневого синтеза каждая VHDL-конструкция заменяется соответствующим RTL-описанием (Register Transfer Level — уровень регистровых передач), которому в случае комбинационной логики соответствует система полностью определенных булевых функций [1]. В данной работе предлагается использовать вместо некоторых VHDL-конструкций эквивалентные по поведению RTL-описания, задающие матричные представления систем частичных (не полностью определенных) булевых функций. Приводятся примеры VHDL-конструкций, которым соответствуют системы частичных булевых функций, предлагаются синтезируемые VHDL-модели систем таких функций, заданных наборами значений аргументов. Описываются эксперименты, целью которых была проверка эффективности замены алгоритмических VHDL-конструкций эквивалентными по поведению VHDL-моделями частичных функций. Под эффективностью понимается уменьшение площади логических схем и/или увеличение их быстродействия. Результаты экспериментов показывают, что во многих случаях цепочки последовательно выполняемых VH-DL-операций, либо некоторые параллельные VHDL-операторы можно заменять соответствующими оптимизированными представлениями систем частичных булевых функций, что в ряде слу-
чае приводит к приводит к лучшим результатам автоматизированного синтеза.
1. ЧАСТИЧНЫЕ БУЛЕВЫ ФУНКЦИИ И СИСТЕМЫ
Под системой булевых функций В(х) будем понимать упорядоченный набор т частичных булевых функций/'(х): В(х) = (/т-1(х), ..., / 1(х), /0(х)), I = 1, ...т, х = (хьх2,...,хп). Значениями векторных функций на наборах (элементах) х* булева пространства, образованного над булевыми переменными вектора х, являются т-компонентные троичные векторы В (х*). Пример задания системы функций В(х) = (/3(х), /2(х), /:(х), /0(х)), х = = (х1, х2, х3, х4), на наборах х* представлен в табл. 1.
Значения 0, 1 функции /'(х) являются определенными, значение "—" является неопределенным значением. Частичная функция / (х) (см. табл. 1) может быть задана парой совершенных дизъюнктивных нормальных форм (ДНФ): множество М/з
единичных значений функции / 3(х) задается в виде совершенной ДНФ
Б/ 3 = х 1 х 2 х 3 х4 V х 1 х 2х3 х 4 V х 1 х2 х3 х 4;
множество М/з нулевых значений функции / (х) — в виде совершенной ДНФ
D°3 = X1X2X3X4 V X1Х2X3X4 V XlX2X3Х4 V X1X2X3X4 V X1X2X3X4 V X1X2X3X4.
Таблица 1. Система частичных булевых функций
Х1 Х2 Хз Х4 f 3 f 2 f1 f0
0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1
0 0 1 0 1 1 0 0
0 0 1 1 - - - -
0 1 0 0 0 0 0 1
0 1 0 1 0 0 0 0
0 1 1 0 1 1 0 1
0 1 1 1 - - - -
1 0 0 0 0 1 0 0
1 0 0 1 0 0 1 1
1 0 1 0 0 0 0 0
1 0 1 1 - - - -
1 1 0 0 - - - -
1 1 0 1 - - - -
1 1 1 0 - - - -
1 1 1 1 - - - -
Аналогично, в виде пар совершенных ДНФ могут быть заданы и другие компонентные функции f 2(x), f :(x), f 0(x). Если значения каждой из функций f'(x), входящих в систему F(x), определены на всех 2n наборах x* булева пространства, то система F(x) является системой полностью определенных функций.
В языке VHDL при синтезе логических схем используется девятизначный алфавит на базе перечислимого типа std_logic. Массив (вектор) значений типа std_logic обозначается как std_logic_vector [1]. На базе типов std_logic, std_logic_vector предлагается строить VHDL-модели частичных функций. Дело в том, что одно из девяти значений данного типа называется don't care (неопределенное значение), обозначается как "—" и предназначается для оптимизации при логическом синтезе. Однако в литературе не показано, каким именно образом значение don't care используется при составлении VHDL-моделей и как влияет на результаты синтеза по таким моделям.
Модель поведения системы частичных булевых функций, заданных на наборах значений аргументов, в языке VHDL может представлена на базе оператора case. Данный оператор является последовательным и употребляется в процессах,
функциях и процедурах программ, написанных на УИЭЬ. Например, система частичных функций, заданная в табл. 1, описывается следующим УИЭЬ-оператором:
— ИТЬ-шс^е! 1
case x is
when "0000" => F v = "0000
when "0001" => F v = "1111
when "0010" => F v = "1100
when "0100" => F v = "00 01
when "0101" => F v = "0000
when "0110" => F v = "1101
when "1000" => F v = "0100
when "1001" => F v = "0011
when "1010" => F v = "0000
when others => F v _ "____
end case;
Заметим, что в языке УИЭЬ строка комментария начинается с двух дефисов.
Некоторые параллельные операторы могут также представлять системы частичных функций. Например, представленным ниже параллельным оператором условного назначения сигнала описывается функциональная модель той же системы частичных функций (табл. 1):
Fv <=
"0000" when x = "0000" else
"1111" when x = "0001" else
"1100" when x = "0010" else
"0001" when x = "0100" else
"0000" when x = "0101" else
"0100" when x = "1000" else
"0011" when x = "1001" else
"0000" when x = "1010" else
"____п.
Обе VHDL-модели являются синтезируемыми — по ним автоматически могут быть построены логические схемы. Заметим, что операторами условного назначения сигнала и операторами case могут быть заданы кодовые преобразователи. В результате синтеза функциональные модели систем частичных функций заменяются логическими схемами, которым соответствуют системы полностью определенных функций, иначе говоря, системы частичных функций доопределяются до систем полностью определенных булевых функций [2].
2. МЕТОДИКА ЗАМЕНЫ ФРАГМЕНТА VHDL-КОДА RTL-МОДЕЛЬЮ
В качестве заменяемых фрагментов предлагается рассматривать совокупности (цепочки) последовательных операций в процессах, функциях и
процедурах. Данные цепочки операций (фрагменты кода) заменяются RTL-моделями полностью определенных либо частичных функций. Методика замены фрагмента VHDL-кода, состоящего из последовательных арифметических операций и предназначенного для вычисления целочисленного выражения эквивалентной по поведению RTL-мо-делью, состоит из следующих шагов.
1. Найти в последовательных участках VHDL-кода (процессах, функциях, процедурах) выражение R, в котором участвуют целочисленные (integer) операнды, определенные над "неполными" диапазонами.
Например, если для кодирования (принятого при синтезе по VHDL-коду) целочисленного опе-
ранда (числа) требуется N разрядов вектора (81ё_1о§1с_уее1ог), а для представления всех значений этого операнда используются не все 2ЛГ различных двоичных наборов, то будем считать, что такой операнд имеет неполный диапазон возможных значений или просто неполный диапазон. Полным диапазон будет тогда, когда используются все 2ЛГ наборов.
2. Построить систему ¥ частичных булевых функций, эквивалентную по поведению выражению Я. В случае полных диапазонов всех входных операндов выражения Я строится система полностью определенных функций.
Листинг 1. VHDL-описание с арифметическими операторами
library IEEE;
use ieee.std_logic_1164.all; use ieee.numeric std.all; entity example 1 is
port (a,b : in integer range 0 to 2;
Y : out integer -4 to 4); end;
architecture behl of example 1 is
p0: process(a, b)
begin
Y <= (a + b) * (a - b);
end process; end beh1;
Листинг 2. RTL-описание
library IEEE;
use ieee.std_logic_1164.all; use ieee.numeric std.all; entity example 1 is
port (a,b : in integer range 0 to 2;
Y : out integer range -4 to 4); end;
architecture beh1 of example 1 is Function RTL_1
(signal a, b : integer range 0 to 2) return integer is variable a v : std logic vector(1 downto 0); variable b v : std logic vector(1 downto 0); variable x : std logic vector(3 downto 0); variable F v : std logic vector (3 downto 0); variable Y : integer range -4 to 4; begin
— numbers --> vectors
a_v := std_logic_vector(to_unsigned(a,2)); b_v := std_logic_vector(to_unsigned(b,2)); x := (a_v & b_v);
- RTL-model 1
Таблица 2. Кодирование операндов выражения Y<= (a + b) * (a — b);
Логическая модель VHDL-модель
Система булевых функций Выражение RTL-модель
Операнд (тип integer) Операнд (тип std_logic_vector) Имена разрядов вектора
x1 x2 a a_v (a_v(1),a_v(0))
Х3 x4 b b_v (b_v(1),b_v(0))
f3 f 2 f1 f 0 Y F_v (F_v(3),F_v(2),F_v(1),F_v(0))
case x is
when "0000" => F v = "0000
when "0001" => F v = "1111
when "0010" => F v = "1100
when "0100" => F v = "0001
when "0101" => F v = "0000
when "0110" => F v = "1101
when "1000" => F v = "0100
when "1001" => F v = "0011
when "1010" => F v = "0000
when others => F v = "____
end case;
— vector —> number
Y : = to integer(signed(F v)); Return Y;
end function RTL 1; begin
p0: process(a, b) begin
Y <= RTL_1 (a, b);
end process; end behl;
3. Провести логическую минимизацию функций системы F с помощью программ минимизации в классе ДНФ [3] либо программ [4] оптимизации диаграмм двоичного выбора. Последний вид оптимизации основан на разложении Шеннона и часто называется BDD-оптимизацией (BDD — Binary Decision Diagram) [5, 6].
Если Fпредставляла систему частичных функций, то после логической минимизации в классе двухуровневых представлений в виде ДНФ либо многоуровневых представлений в виде диаграмм двоичного выбора будет получена система полностью определенных функций, реализующая систему F частичных функций. Понятие реализации системы частичных
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.