Александр Владимирович НЕМЧЕНКО аспирант Харьковского национального университета
радиоэлектроники (известный как ХИРЭ) e-mail:alexandre_n@mail.ru www:alexandre-n.narod.ru
Параллельные цифровые автоматы - синтез
Введение
Данная статья - продолжение темы параллельных цифровых автоматов, поднятой
в двух предыдущих статьях - основные сведения и подготовка
к синтезу. Там был начат проимер по синтезу цифрового автомата. Алгоритм
его работы следующий:
Рис. 1 Граф-схема некоторого алгоритма
Были проделаны необходимые операции - разметка состояний и составление таблицы
переходов с необходимыми формулами:
Еще необходимо построить таблицу сбросов - перечислить те состояния, в которые
попадает автомат после сброса. Однако в данном случае очевидно, что это будут
состояния a1,
b1, b2,
... b6.
Синтез в универсальном базисе
Теперь переходим к первому варианту синтеза - синтез в универсальном базисе
"И"-"ИЛИ"-"НЕ". Имеется в виду, что создается
схема, которая потом может быть реализована в виде небольшого устройства с кучей
проводочков и микросхем :-). Потом мы рассмотрим более аккуратный
вариант - синтез с использованием программируемой логики. Но это потом, а сейчас
- универсальный базис!
Из каких основных блоков может состоять цифровой автомат?
Очевидно, что, если есть память (а для цифрового
автомата с состояниями это очевидно :-)), то есть регистры,
где она хранится, или точнее - набор триггеров. Итак, блок номер 1 - триггеры
памяти.
Далее, как видно из таблицы 1, эти состояния нещадно эксплуатируются как логическое
условие - в этом состоянии или нет. Следовательно, удобно иметь один провод,
принимающий "1", когда активно это состояние, или "0", когда
нет. Как это можно сделать? Дешифратор - вот что нам надо! Значит, блок 2 -
дешифратор.
Есть еще блок сброса. Он обусловлен тем, что при поступлении "1"
на вход Reset ПЦА должен переходить в некое начальное
состояние. Следовательно, есть блок 3.
Как совместить переходы в следующее состояние и сброс? Для этого подойдет мультиплексор,
которому на адресный вход подается Reset, а на информационный
- константа с начальным состоянием и новое состояние. Все это для 4-го потока
выглядит следующим образом:
Рис. 2 Память для 5-го потока
А что после этого? После этого идет уже банальная обработка булевых функций.
Настало время их составить для нашого случая.
Какие функции у нас будут? Ну, во-первых, это выходные сигналы. Как они будут
составляться? В нашем случае (как, впрочем, для любых автоматов Мура) они зависят
от текущего состояния и от его одного. Следовательно, это будут выходы с дешифраторов,
заведенные на выходы всего устройства. В нашем случае это будут следующие соответствия:
(2)
Еще необходимо создать формулы переходов. Как это делается?
Возьмем, например, второй поток:
Таблица 2. Прямая таблица переходов для второго потока
Поток
Исходное
состояние
Код
исходного
состояния
Состояние
перехода
Код
состояния
перехода
Входной
сигнал
Функция
возбуждения
2
b2
(—)
00
b2
00
00
a2
01
01
a2
(y2)
01
a3
11
1
11
a3
(y3)
11
b2
00
00
e2
10
10
e2
(—)
10
e2
10
10
b2
00
00
Как было сказано в предыдущей статье,
память мы реализуем на двух D-триггерах. Таблица переходов для этого триггера
выглядит следующим образом:
Таблица 3. Таблица переходов D-триггера
Исходное
состояние
Состояние
перехода
D
CLK
D
D
X
0
D
0
0
0-1
D
1
1
0-1
Другими словами, по переднему форнут на входе CLK
память записывает то значение, что поступает на вход D.
Значит, формула должна создавать то значение, которое потом будет храниться
в памяти.
В таблице 2 перечислены состояния перехода и рядом код, который фактически
записывается в триггер. Значит, формулы перехода должны порождать этот код в
триггере.
Последний столбец - функции возбуждения, по которым определяется значение функций
возбуждения. Сама же функция возбуждения зависит от текущего состояния и входов
(за подробностями обращайтесь в курс "Прикладной теории цифровых
автоматов" :-) ). Таким образом, для второго потока получаем следующее
(D1 - левый бит,
D2 - правый бит):
(3)
Схема для этого блока выглядит следующим образом:
Рис. 3 Формулы переходов для 2-го потока
Таким же образом создаются функции возбуждения и для остальных потоков (подробности
приводить не будем :-)).
Необходимо также помнить о вспомогательной формуле (1). Для нее также строится
обычная комбинационная логика.
Таким образом, получается готовая схема. Полная схема выложена
на сайте.
Схема была составлена силами Active-HDL
6.1. Там же была промоделирована. Все работает :-) (по крайней
мере в качестве модели). Можете посмотреть временнЫе
диаграммы. А вообще - есть ZIP-файл с проектом текущего ПЦА (о нем сказано
ниже).
Правда, моделирование велось без учета временных задержке распространения сигнала
в реальных устройствах. Возможно, в будущем озверею, достану документацию по
родным ЛМ-кам и ЛН-кам и тогда проверю уже совсем серьезно :-)!
Но это не интересно - лучше поработать над ПЛИС.
Программируемая логика - кратко о главном
Программируемая логика - тема большая и отдельная. В данной статье я эту тематику
рассматривать не буду (возможно, рассмотрю в будущем). Жаль, Интернет не могу
сейчас запустить - дал бы массу ссылок. Для желающих - ключевые слова: FPGA,
CPLD, Altera, Xilinx, Atmel... Можете глянуть за классификацией сюда.
Что нам надо знать? А то, что усилиями ученых и буржуев-производителей создана
хорошая база для создания в домашних условиях устройства с любой архитектурой
в заданных пределах. В общем случае ПЛИС (а также ПЛМ, ПМЛ, CPLD, PLD) - это
блок "И", блок "ИЛИ" и память с обратными связями. Блоки
"И" и "ИЛИ" могут быть запрограммированы. В итоге получается,
что на базе такой ПЛИС можно создать устройство с булевыми функциями, где фигурирует
память. Накладываются ограничения на число термов, самих функций и на размеры
памяти. В современных разработках также есть блоки для ускоренного сложения.
Проблема заключается в том, что сигналы распространяются по разным линиям с
разныой длиной и, как следствие, разным временем распространения. В связи с
этим могут возникать гонки сигналов. Но эта проблема решается.
Для программирования всего этого хозяйства используется специальный формат
файлов, абсолютно нечитаемый для человека :-). Писать в нем трудно.
Но чья-то умная голова нашла прекрасный выход из этой проблемы.
Дело в том, что уже много лет назад американское военное ведомство заказало
для себя разработку языка описания аппаратуры VHDL, который бы однозначно описывал
поведение устройства. Это был язык моделирования устройств. Но вышеописанная
голова умудрилась воспользоваться этим языком для программирования ("прошивки")
ПЛИС! В результате вы пишите программу на достаточно простом языке программирования,
проверяете в среде моделирования и прошиваете ПЛИС. Все, устройство готово для
употребления! На сегодняшний день даже не нужен программатор - на схеме, где
стоит ПЛИС, используется несколько выходов для программирования, которое осуществляется
по COM- или другому порту. Дешево и сердито :-).
Однако вылезла другая проблема. Так как VHDL был создан именно для моделирования,
в нем есть непрошиваемые конструкции (работа с файлами, выдача сообщений на
экран, временнЫе задержки). Поэтому VHDL делят на синтезируемое и несинтезируемое
подмножества. Первое синтезируется на раз, второе вообще не синтезируется
:-). Это необходимо учитывать.
Вся эта ситуация стимулировала разработку других языков описания аппаратуры.
Наиболее достойный конкурент сегодня (на 5 января 2004 г. :-))
- это Verilog. Единственное, что сдерживает лидерство Verilog - это масса готовых
проектов для VHDL. Создаются новые языки - например, System C. Там вообще обещают,
что будет писаться программа на C, которая потом будет распадаться на аппаратную
и программную часть. Есть еще сегодня Celoxica C. Что это такое - доподлинно
не знаю, еще не изучил.
Таким образом, VHDL - это прекрасное средство для моделирования и синтеза устройства.
Для создания устройства делают следующее:
создают модель наиболее простым и доступным способом - с помощью VHDL или
даже C. Производится моделирование, проверяется поведение и соответствие
алгоритму. Это делают в среде моделирования типа Active-HDL, Riviera, Metamor;
создают модель на синтезируемом подмножестве VHDL с учетом разных хитростей,
нужных для оптимизации устройства в ПЛИС (нужное время распространения сигнала,
поменьше триггеров, поменьше места и тому подобное). Созданную модель сравнивают
с предыдущей. Если совпадает - движемся дальше;
созданную синтезируемую модель прогоняют через программу синтеза - например,
Synplify - и создают код для данного кристалла (например, для Altera MAX3000A).
В результате получается модель того, что будет на кристале без учета временнЫх
задержек. Эту модель сравнивают с 1-ой. Если совпадает - движемся дальше;
предыдущую модель прогоняют через программу производителя программируемого
устройства - например, MaxPlus для Altera. Та расставляет весь код по ячейкам
устройства и создает модель со всеми временнЫми характеристиками. Если модель
по поведению совпадает с 1-ой - движемся дальше;
все сделано? Тогда можно прошивать реальный кристал! Это делается тут
:-).
Вот нечто подобное мы сейчас и проделаем (за исключением шага 5 :-)).
ПЦА на программируемой логике
Даже если вы не знаете VHDL - не страшно, я постараюсь изложить материал так,
чтобы логика работы была понятна. То есть саму программу вы не поймете, но общий
подход будет понятен :-).
Прежде всего, в VHDL создается заголовок - интерфейс устройства:
entity PFSM_vhdl is
port(
CLK : in STD_LOGIC;
Reset : in STD_LOGIC;
X : in STD_LOGIC_VECTOR(1 to 5);
Y : out STD_LOGIC_VECTOR(1 to 13)
);
end PFSM_vhdl;
STD_LOGIC - это тип данных, соответствующий физическому
понятию сигнала.Сигнал может быть "1" или "0", а может быть
и третьим состоянием "Z", может быть любым - "X", а может
быть вообще неопределенным - "U". Также это может быть обрыв - "-".
Далее создается одна из его реализацией - архитектурное тело. Там, собственно,
и описывается поведение устройства.
Зачем у одного устройства разделяется реализация и интерфейс? Это сделано для
того, чтобы можно было по-разному реализовать один и тот же алгоритм. Дело в
том, что VHDL получился достаточно уникальным языком - в рамках одного и того
же языка (и даже одного проекта) можно создавать устройство с совершенно различными
идеологиями - 1) задается таблица истинности и булевы функции, 2) задается поведение
устройства и 3) задаются компоненты - блоки устройства. Все это можно смешивать-перемешивать,
а можно создавать просто разные программы. Обычно модель делают в одном стиле,
а синтезируемую модель - в другом.
В нашем случае я создал модель в универсальном базисе, пользуясь 3-им подходом,-
в редакторе блоков Active-HDL я использовал обычные блоки - элементы И, ИЛИ,
НЕ, триггеры, дешифраторы и мультиплексоры. В итоге получилась схема устройства.
Потом же я это откомпилировал и получил код VHDL, который потом сравнил с другой
реализацией. Вот так все просто и красиво!
Вернемся к ПЦА. Будем делать модель, используя 1-ый и 2-ой подход.
В VHDL программа выполняется параллельно-последовательно - есть блоки
последовательные (процессы), а все они вместе выполняются параллельно.
Поэтому принято алгоритм разбивать на процессы.
У нас будет несколько процессов. 1-ый будет присваивать значение переменным
состояния - как дешифратор в блок-схеме. 2-ой будет присваивать значение выходам.
3-ий будет описывать вспомогательные функции. 4-ый будет определять будущее
состояние. Ну а 5-ый будет присваивать это будущее состояние по сигналу CLK
или начальное по сигналу Reset.
Соответственно, для каждого потока создается 1) новый тип переменных, где перечисляются
все состояния, 2) переменная с текущим состоянием, 3) переменная с новым состоянием.
Это была общая структура. Теперь будем разбираться с каждым элементом в отдельности.
Новые типы переменных задаются следующим образом:
type StateType1 is (a1, a14, e1, b1, a13);
type StateType2 is (b2, a2, a3, e2);
type StateType3 is (b3, e3);
type StateType4 is (b4, a4, a5, e4);
type StateType5 is (b5, a6, a7, e5);
type StateType6 is (b6, a8, a9, a10, a11, a12, e6);
Создаются типы StateType1, StateType2,
... StateType6, в которых перечислены все возможные
состояния для данного потока.
Далее указываются переменные состояния и нового состояния:
signal State1, NextState1: StateType1;
signal State2, NextState2: StateType2;
signal State3, NextState3: StateType3;
signal State4, NextState4: StateType4;
signal State5, NextState5: StateType5;
signal State6, NextState6: StateType6;
После указываются переменные текущего состояния и вспомогательные состояния:
Сигнал - это любая переменная в коде VHDL. В зависимости от программы
и ее оптимизации при синтезе, сигнал может превратиться в триггер (запись по
фронту импульса), защелку (запись по уровню), обычный провод или вообще ничто.
Корректная работа с сигналами важна, так как позволяет при синтезе уменьшить
затраты на память.
Как вы уже догадались :-),BOOLEAN -
это значение "истина" или "ложь".
Имея эти определения, переходим к первому процессу - определение переменной
состояния:
sa1 <= true when State1 = a1 else false;
sa2 <= true when State2 = a2 else false;
sa3 <= true when State2 = a3 else false;
sa4 <= true when State4 = a4 else false;
sa5 <= true when State4 = a5 else false;
sa6 <= true when State5 = a6 else false;
sa7 <= true when State5 = a7 else false;
sa8 <= true when State6 = a8 else false;
sa9 <= true when State6 = a9 else false;
sa10 <= true when State6 = a10 else false;
sa11 <= true when State6 = a11 else false;
sa12 <= true when State6 = a12 else false;
sa13 <= true when State1 = a13 else false;
sa14 <= true when State1 = a14 else false;
sb1 <= true when State1 = b1 else false;
sb2 <= true when State2 = b2 else false;
sb3 <= true when State3 = b3 else false;
sb4 <= true when State4 = b4 else false;
sb5 <= true when State5 = b5 else false;
sb6 <= true when State6 = b6 else false;
se1 <= true when State1 = e1 else false;
se2 <= true when State2 = e2 else false;
se3 <= true when State3 = e3 else false;
se4 <= true when State4 = e4 else false;
se5 <= true when State5 = e5 else false;
se6 <= true when State6 = e6 else false;
Перед именем состояния добавлена 's' чтобы не совпадать
с именем состояния в вышеопределенных типах. Этот процесс (если быть точнее,
множество процессов,- каждая строка представляет из себя отдельный процесс)
действует как набор дешифраторов.
Дальше идет определение вспомогательных функций:
f1b <= (sa3 OR se2) AND (sa5 OR se4) AND (sa7 OR (sa6 AND x(3) = '1') OR se5) AND (sa10 OR sa12 OR se6);
f1e <= (sa14 AND x(1) = '1') OR se1;
f246c <= sb2 OR sb3 OR sb6;
f3e <= se3;
При должном развитии воображения :-) видно, что эти строки представляют
из себя набор элементов И и ИЛИ.
Назначение выходных сигналов тоже банально:
y(1) <= '1' when sa14 else '0';
y(2) <= '1' when sa2 else '0';
y(3) <= '1' when sa3 else '0';
y(4) <= '1' when sa4 else '0';
y(5) <= '1' when sa5 else '0';
y(6) <= '1' when sa6 else '0';
y(7) <= '1' when sa7 else '0';
y(8) <= '1' when sa8 else '0';
y(9) <= '1' when sa9 else '0';
y(10) <= '1' when sa10 else '0';
y(11) <= '1' when sa11 else '0';
y(12) <= '1' when sa12 else '0';
y(13) <= '1' when sa13 else '0';
Далее идет определение следующего состояния:
NextState1 <=
a14 when sa1 or (sa14 and x(1) = '0') else
e1 when (sa14 and x(1) = '1') or (se1 and f246c) else
b1 when (se1 and not f246c) or (sb1 and not f1b) else
a13 when sb1 and f1b else
a1;
NextState2 <=
a2 when sb2 and f1e else
a3 when sa2 else
e2 when (sa3 and not f1b) or (se2 and not f1b) else
b2;
NextState3 <=
e3 when sb3 and f1e and x(2) = '1' else
b3;
NextState4 <=
a4 when sb4 and f3e else
a5 when sa4 else
e4 when (sa5 and not f1b) or (se4 and not f1b) else
b4;
NextState5 <=
a6 when sb5 and f3e else
a7 when sa6 and x(3) = '0' else
e5 when (sa5 and not f1b) or (sa6 and x(3) = '1' and not f1b) or (se5 and not f1b) else
b5;
NextState6 <=
a8 when sb6 and f1e else
a9 when sa8 and x(4) = '1' else
a10 when sa9 else
a11 when (sa8 and x(4) = '0') or (sa11 and x(5) = '0') else
a12 when sa11 and x(5) = '1' else
e6 when (sa10 and not f1b) or (sa12 and not f1b) or (se6 and not f1b) else
b6;
Вот тут остановимся и осмотримся повнимательней.
Например, переменной NextState2 назначается состояние
a2, если автомат
(вернее, один поток) находится в состоянии b2
и f1e
= 1. В противном случае определяются правила перехода в a3,
потом в e2 (зависимость
посложнее - проверяется два условия), а потом - безусловный переход в b2.
Что получается?
В итоге получается полный набор правил перехода (сравните с таблицей).
Наличие безусловного перехода гарантирует две вещи:
автомат в любом непредусмотренном случае попадает в состояние b2;
NextState2 станет просто комбинационной логикой,
а не элементом памяти, так как его состояние полностью определяется
текущими условиями и не зависит от предыдущего состояния.
При составлении переменных следующего состояния удобней, кстати, пользоваться
обратной таблицей переходов.
В конце следует процесс назначения следующего состояния:
StateAssignmentProcess: process (CLK) is
begin
if rising_edge (CLK) then
if Reset = '1' then
State1 <= a1;
State2 <= b2;
State3 <= b3;
State4 <= b4;
State5 <= b5;
State6 <= b6;
else
State1 <= NextState1;
State2 <= NextState2;
State3 <= NextState3;
State4 <= NextState4;
State5 <= NextState5;
State6 <= NextState6;
end if;
end if;
end process StateAssignmentProcess;
Тут создается процесс StateAssignmentProcess, который
активизируется (или содержит в списке чувствительности) от сигнала CLK.
Это означает, что любое изменение сигнала CLK
и только CLK запускает этот процесс.
Внутри процесса проверяется условие наличие переднего фронта импульса:
rising_edge(CLK). Если это так, то выполняется внутреннее
тело сравнения.
Если сигнал Reset равен "1", то выполняется
сброс в начальное состояние. В противном случае производится назначение, определенное
в переменных следующего состояния.
Из этого процесса видно следующее:
изменение текущего состояния (текущих состояний) производится
по перепаду CLK из "0" и "1".
Можно сделать другой перепад или назначение по уровню;
первым делом производится сброс (если он есть). Значит, сброс у нас синхронный
- производится только при наличии CLK (если бы
мы его вынесли за пределы этого if ... end if,
то он был бы асинхронным);
переменная состояния является триггером, управляемым перепадом уровня.
Если бы мы предусмотрели безусловное назначение (вне проверки перепада
уровня), то это был бы просто провод.
Таким образом, получена модель параллельного цифрового автомата, выполняющего
алгоритм, приведенный на рисунке 1. Модель синтезируема, так как в ней было
использовано только синтезируемое подмножество языка. Текст программы выложен
здесь.
Тестирование
Для тестирования было создано "тестовое устройство" - у него есть
только один выход OK, на который подается единица,
если совпадают выходы всех тестируемых устройств.Тестируемыми же являются 1)
схема, 2) код на VHDL, 3) интезированный код, 4) код с временнЫми задержками.
Создана временнАя
диаграмма, где все это видно :-).
На этой диаграмма видно расхождение в самом начале работы - до подачи Reset.
Это, впрочем, естественно, так как модель и реальная модель используют разные
модели триггеров.
Вы можете загрузить файл с проектом рассматриваемого
ПЦА. В этом архиве вы найдете все необходимые файлы для моделирования и синтеза.
Единственно что - этот проект выполнен универсальным, то есть его можно открывать
в любом редакторе (за исключением файла BDE). Для его использования создайте
новый проект и подключите к нему эти файлы.
Также вы можете посмотреть HTML-версию
проекта, сгенерированную Aldec Active-HDL 6.1. Ее можно смотреть прямо в
вашем браузере.
Выводы
В данной работе рассмотрен синтез ПЦА для универсального базиса "И"-"ИЛИ"-"НЕ"
и языка описания аппаратуры VHDL. Фактически дан шаблон, на основе которого
можно создавать другие устройства.
Шаблон схемы позволяет готовить и проверять схему для ее последующей пайки.
Шаблон VHDL позволяет создавать синтезируемый код, который выдерживает временнЫе
характеристики.
За бортом остались, собственно, вопросы параллелизма - синхронизация и тому
подобное. Это будет рассмотрено в будущем.
