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



жүктеу 100.49 Kb.
Дата15.10.2018
өлшемі100.49 Kb.

VHDL-МОДЕЛИ СИСТЕМ НЕ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ
П.Н. Бибило
Объединенный институт проблем информатики НАН Беларуси,

Минск, Беларусь
Современные синтезаторы осуществляют высокоуровневый синтез логических схем компилятивным способом – каждая конструкция исходного VHDL-описания заменяется соответствующей логической подсхемой, при этом циклы «разворачиваются» и каждой итерации цикла соответствует своя подсхема [1]. Результатом выполнения высокоуровневого синтеза является RTL-описание. Далее под RTL-описаниями будут пониматься те VHDL-описания, которые составлены из логических операторов, операторов назначения сигналов и операторов port map описания связей элементов памяти. Вместо операторов port map могут быть вызовы функций либо процедур, описывающих поведение элементов памяти. Именно такое множество операторов языка VHDL используется в синтезаторе LeonardoSpectrum для представления RTL-описаний [2]. После этапа высокоуровневого синтеза выполняется этап технологически независимой оптимизации. В работе [3] для схем комбинационной логики было предложено заменять исходные алгоритмические VHDL-конструкции оптимизированными RTL-описаниями, была экспериментально проверена эффективность такой замены. Замена осуществлялась следующим образом: полученные после высокоуровневого синтеза RTL-описания представляли собой многоуровневые (скобочные) представления систем полностью определенных булевых функций, которые сначала с помощью средств САПР [4] преобразовывались в матричные формы функций, а затем подвергались минимизации в классе ДНФ, после чего по минимизированным ДНФ функций системы проводился повторный синтез. В результате во многих случаях был получен выигрыш по быстродействию и/или по сложности схемы в целевой библиотеке проектирования заказной СБИС.

В данной работе предложенный ранее подход обобщается – предлагается методика выделения VHDL-конструкций и замены таких конструкций эквивалентными по поведению матричными представлениями систем не полностью определенных (частичных) булевых функций. В процессе синтеза исходные VHDL-модели частичных булевых функций превращаются в комбинационные логические схемы, моделями поведения которых являются системы полностью определенных функций. Известно [5], что использование при синтезе логических схем неопределенных значений частичных булевых функций может приводить к более экономичным схемам. Далее приводятся синтезируемые VHDL-модели систем частичных булевых функций, заданных как наборами значений аргументов, так и в интервальной форме. Сообщается о результатах эксперимента замены некоторых алгоритмических VHDL-конструкций эквивалентными по поведению VHDL-моделями частичных функций.

Под векторной булевой функцией , будем понимать упорядоченную систему частичных булевых функций , значениями векторных функций на элементах булева пространства являются m-компонентные троичные векторы . Пример интервального задания частичной векторной функции представлен в табл. 1. Частичная функция (см. табл. 1) может быть задана парой ДНФ: множество задается в виде ДНФ =; множество – в виде ДНФ =. Аналогично, в виде пары ДНФ может быть задана функция .

Таблица 1



Интервальная форма

системы функций










0 - - 1

0 – 1 1


1 – 0 0

- - 1 0


0 0 0 0

1 1 1 1


- 1 1 0

- 1

1 -


1 -

- 0


1 1

0 0


0 -

Интервальная форма задания векторной функции состоит из троичной матрицы задания элементарных конъюнкций и троичной матрицы вхождений конъюнкций в ДНФ, представляющих области нулевых и единичных значений функций , компонент векторной функции . Неопределенное значение «–» элемента , i=1,…,m, j=1,…,k, матрицы не означает, что функция принимает неопределенное значение на наборах, которые порождает троичный вектор строки i матрицы ; например, на пересечении первой строки и первого столбца матрицы находится «–», однако это не означает, что на четырех наборах 0001, 0011, 0101, 0111 функция не определена. Рассмотрев вторые строки матриц и , можно убедиться, что на наборах 0011, 0111 функция принимает единичное значение. Если же все строки матрицы являются попарно ортогональными, то в строках матрицы задаются значения 0,1, «–» компонентных частичных функций .

В языке VHDL при синтезе логических схем используется девятизначный алфавит на базе перечислимого типа std_logic. Массив (вектор) значений типа std_logic обозначается как std_logic_vector [2]. На базе типов std_logic, std_logic_vector предлагается строить VHDL-модели частичных функций. Дело в том, что одно из девяти значений данного типа называется don’t care (неопределенное значение), обозначается как «–» и предназначается для оптимизации при логическом синтезе. Однако в литературе не показано, каким именно образом значение don’t care используется при составлении VHDL-моделей и как влияет на результаты синтеза по таким моделям. Предлагаемая VHDL-модель системы частичных функций состоит из двух частей: в первой части с помощью логических операторов записываются ДНФ , , вторая часть – это VHDL-функция value_f, формирующая значения функций системы. Например, в листинге 1 задана VHDL-модель системы функций из табл. 1.

Листинг 1. VHDL-модель интервальной формы системы частичных функций


package chast_pack is

constant N : natural := 4;

constant M : natural := 2;

constant K : natural := 7;

end chast_pack;

LIBRARY ieee;

USE ieee.std_logic_1164.all;

USE work.chast_pack.all;

ENTITY chast_matr IS

PORT (x : IN std_logic_vector (1 to N);

F : OUT std_logic_vector (1 to M));

END;


ARCHITECTURE BEH of chast_matr is

signal f_nul : std_logic_vector (1 to M);

signal f_ed : std_logic_vector (1 to M);

Function value_f (f_nul : std_logic_vector (1 to M);

f_ed : std_logic_vector (1 to M) )

return std_logic_vector is

variable prom : std_logic_vector (1 to M);

begin


for i in f_nul'range loop

if ((f_nul(i)='1') and (f_ed(i)='0')=true) then prom (i):='0';

elsif ((f_nul(i)='0') and (f_ed(i)='1')=true) then prom(i):='1';

elsif ((f_ed(i)='0') and (f_nul(i)='0')=true) then prom(i):='-';

elsif ((f_ed(i)='1') and (f_nul(i)='1')=true) then prom(i):='X';

report "error";

end if;

end loop;

return prom ;

end value_f ;

BEGIN

f_nul(1) <= (x(1) and x(2) and x(3) and x(4)) or



(x(2) and x(3) and not x(4));

f_ed(1) <= (not x(1) and x(3) and x(4)) or

(x(1) and not x(3) and not x(4) ) or

(not x(1) and not x(2) and not x(3) and not x(4));

f_nul(2) <= (x(3) and not x(4)) or

(x(1) and x(2) and x(3) and x(4));

f_ed(2) <= (not x(1) and x(4) ) or

(not x(1) and not x(2) and not x(3) and not x(4));

F <= value_f (f_nul, f_ed);

END;
Если же функции системы заданы на наборах значений аргументов, то VHDL-модель упрощается. Например, для системы функций, заданных в табл.2, соответствующая VHDL-модель приводится в листинге 2. Приведенные в листингах 1 и 2 VHDL-модели являются синтезируемыми – по ним синтезатор может построить логическую схему.

Таблица 2

Задание системы функций

на наборах значений аргументов






0 0 0 0

0 0 0

0 0 0 1

0 0 1

0 0 1 0

0 1 0

0 0 1 1

- - -

0 1 0 0

0 0 1

0 1 0 1

0 1 0

0 1 1 0

0 1 1

0 1 1 1

- - -

1 0 0 0

0 1 0

1 0 0 1

0 1 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

- - -

Листинг 2. VHDL-описание, соответствующее системе частичных функций (табл. 2)


library ieee;

use ieee.std_logic_1164.all;

entity example_2 is

port (x : in std_logic_vector (1 to 4);

y : out std_logic_vector (1 to 3));

end;


architecture BEHAVIOR of example_2 is

begin


y <= "000" when x = "0000" else

"001" when x = "0001" else

"010" when x = "0010" else

"001" when x = "0100" else

"010" when x = "0101" else

"011" when x = "0110" else

"010" when x = "1000" else

"011" when x = "1001" else

"100" when x = "1010" else

"---";


end BEHAVIOR;
Для проверки эффективности замены VHDL-операторов моделями систем частичных функций был проведен эксперимент. Исходные системы частичных функций, заданные аналогично тому, как это показано в листинге 2, поступали на вход синтезатора LeonardoSpectrum, который строил схемы в библиотеке проектирования [2] заказной СБИС. Полученные схемы сравнивались со схемами, построенными по VHDL-описаниям систем частичных функций, которые были оптимизированы двумя способами: в классе ДНФ (класс двухуровневых представлений систем функций) с помощью программы раздельной минимизации [6] и в классе диаграмм двоичного выбора (BDD), которые представляют собой класс многоуровневых представлений систем функций, строящихся на основе разложения Шеннона. Оптимизация BDD осуществлялась с помощью программы, реализующей модифицированный на случай частичных функций алгоритм из работы [7]. Результаты эксперимента над двумя практическими примерами кодовых преобразователей Verg1, Verg2 представлены в табл. 3. Кодовый преобразователь задавался двумя булевыми матрицами, интерпретируемыми как система частичных функций, заданная на наборах значений аргументов. Первая матрица имела размерность (n столбцов, k строк), вторая – размерность . В табл.3: n – число входов кодового преобразователя; m – число выходов кодового преобразователя; k – число кодовых слов; L – число элементов схемы; S – суммарная площадь кристалла СБИС (в условных единицах), требуемая для размещения элементов схемы; – задержка схемы (нс). При поиске лучшей перестановки последовательности переменных, по которым строится BDD, для примера Verg1 эвристический алгоритм испытал 500 перестановок, для более сложного примера Verg2 – 100 перестановок аргументов. Для данных примеров схем лучшие результаты (выделены жирным шрифтом) дала оптимизация представлений функций в классе ДНФ.
Таблица 3

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

VHDL-оператор

(схема)


n

m

k

Схемная реализация

VHDL-оператора



Схемная реализация

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



S

L



S

L



Задание функций

Verg1

17

61

2003

8940

2183

17.79

3200

826

7.55

ДНФ

3741

991

12.15

BDD

Verg2

18

63

2129

8884

2272

20.29

3141

805

8.33

ДНФ

5809

1508

12.59

BDD

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


СПИСОК ЛИТЕРАТУРЫ
1. Perry D.L. VHDL: Programming by Example. Fourth Edition. McCraw-Hill, 2002. 476 p.

2. Бибило П.Н. Cистемы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum. М.: СОЛОН-Пресс, 2005. 384 с.

3. Бибило П.Н. Теоретические основы синтеза логических схем по VHDL-описаниям в синтезаторе Leonardo. //Микроэлектроника. 2005. Т. 34. № 6. С. 466 – 477.

4.  Бибило П.Н., Василькова И.В., Кардаш С.Н., Кириенко Н.А. , Логинова И.П., Новиков Я.А., Романов В.И., Торопов Н.Р. , Черемисинов Д.И., Черемисинова Л.Д.  Система “Custom Logic” автоматизированного проектирования управляющей логики заказных цифровых СБИС. //Микроэлектроника. 2004. Т. 33. №5. С. 379 – 398.

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

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



7. Бибило П.Н., Леончик П.В. Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций // Управляющие системы и машины. 2009. № 6. С. 42–49.
Каталог: sites -> default -> files -> thesis simple
files -> Ќазаќстан Республикасыныѕ мемлекеттік ќўпияларын ќорєаудыѕ
files -> Заң жобаның ғылыми құқықтық сараптаманың
files -> Беткі сулардың сапасын талдау: НҰра өзені алабының мысалында
files -> Этносаралық Үйлесімділік жүйесіндегі саяси-мәдени механизмдердің орны әлеуметтік ғылым магистрі, аға оқытушы Сыздықова С. М
thesis simple -> Об орграфах, имеющих минимальные вершинные 1-расширения с малым количеством дуг
thesis simple -> Анализ решения установочной задачи для автоматов


Достарыңызбен бөлісу:


©kzref.org 2019
әкімшілігінің қараңыз

    Басты бет