Синтез конечных автоматов класса f
Существенное отличие автомата класса F от автомата класса E заключается в том, что выходные функции автомата класса F непосредственно не зависят от входных переменных. Это позволяет для построения конечных автоматов класса F использовать ПЛИС, входные буферы которых имеют только одну регистровую связь с комбинационной частью ПЛИС, например, SPLD PLS30S16; CPLD семейств MACH 1 и 2, MAX 7000, MAX 9000, FLEX [3]. Таким образом, в общем случае автоматы класса F, по сравнению с автоматами класса E, могут быть реализованы на более широком разнообразии ПЛИС. Следует однако отметить, что в некоторых случаях входные переменные могут являться аргументами дополнительных функций возбуждения элементов памяти, вводимых для различия кодов внутренних состояний автомата класса F.
Для синтеза автомата класса F без всяких изменений может быть примен╦н алгоритм 1.
Программная реализация методов синтеза автоматов классов e и f
Рассмотренные методы синтеза конечных автоматов классов E и F реализованы программно в пакете ZUBR, при этом производится следующая последовательность действий.
Выполняется минимизация внутренних состояний исходного конечного автомата одним из известных методов.
Если необходимо синтезировать автомат класса F, то выполняется алгоритм 2 работы [1] расщепления внутренних состояний для приведения автомата типа Мили к эквивалентному автомату типа Мура.
Выполняется алгоритм 1 синтеза автоматов класса E или F.
Строится система булевых функций, соответствующая комбинационной части конечного автомата.
Построенная в пункте 4 система булевых функций реализуется на выбранной ПЛИС одним из методов синтеза комбинационных схем.
Программа ZUBR позволяет пользователю задавать следующие режимы и параметры синтеза:
разрешать/запрещать минимизацию внутренних состояний исходного конечного автомата;
задавать параметры ПЛИС или указывать семейство ПЛИС из имеющегося списка;
выбирать метод синтеза комбинационной схемы (одноуровневой, двухуровневой или многоуровневой);
задавать параметры метода синтеза комбинационной схемы.
Дальнейшее проектирование конечного автомата может выполняться с помощью индустриального пакета. Для этого программа ZUBR позволяет представлять результаты синтеза на следующих языках проектирования: VHDL, Verilog, AHDL, Abel и других.
Результаты экспериментальных исследований методов синтеза автоматов классов e и f
Для проверки эффективности предложенных методов в качестве исходных данных использовались эталонные примеры конечных автоматов, разработанные в центре MCNC (MicroelectronicsCenterofNorthCarolina) [4]. В качестве исследуемого метода синтеза рассматривался только метод синтеза конечных автоматов класса E, поскольку большинство эталонных примеров являются автоматами типа Мили. Метод синтеза автоматов класса E сравнивался с традиционными методами синтеза конечных автоматов пакета MAX+PLUSII для семейства FLEX 10K фирмы Altera и пакета Webpack для семейства VIRTEX2 фирмы Xilinx.
Результаты сравнения приведены в табл. 5 и 6, где Name - имя эталонного примера; L, N, M и P - число входов, выходов, внутренних состояний и переходов конечного автомата, соответственно; C1 - число используемых макроячеек ПЛИС при синтезе конечного автомата с помощью метода синтеза пакета MAX+PLUSII для семейства FLEX 10K; C2 - число используемых макроячеек ПЛИС семейства FLEX 10K при синтезе конечного автомата класса F с помощью рассматриваемого метода синтеза; C1/C2 - отношение C1 к C2; D1 - временная задержка, измеряемая в наносекундах, при синтезе конечного автомата с помощью метода синтеза пакета MAX+PLUSII для семейства FLEX 10K; D2 - временная задержка, измеряемая в наносекундах, при реализации конечного автомата класса F на ПЛИС семейства FLEX 10K с помощью рассматриваемого метода синтеза; D1/D2 - отношение D1 к D2; C3, C4, D3 и D4 - аналогичные параметры, но в отношении ПЛИС семейства VIRTEX2.
Таблица 5. Сравнение метода синтеза автоматов классов E и F с методом, реализованным в пакете MAX+PLUSII для семейства FLEX 10K
Name |
L |
N |
M |
P |
C1 |
C2 |
C1/C2 |
D1 |
D2 |
D1/D2 |
beecount |
3 |
4 |
7 |
28 |
37 |
10 |
3,7 |
23 |
14,1 |
1,63 |
dk15 |
3 |
5 |
4 |
32 |
49 |
24 |
2,04 |
23,1 |
15,9 |
1,45 |
ex3 |
2 |
2 |
10 |
36 |
22 |
10 |
2,2 |
16,4 |
18,2 |
0,90 |
ex5 |
2 |
2 |
9 |
32 |
23 |
6 |
3,83 |
17,7 |
13,5 |
1,31 |
ex7 |
2 |
2 |
10 |
36 |
20 |
4 |
5,0 |
18,5 |
11,5 |
1,61 |
keyb |
7 |
2 |
19 |
170 |
102 |
83 |
1,23 |
31,3 |
28,6 |
1,09 |
lion |
2 |
1 |
4 |
11 |
10 |
3 |
3,33 |
16,4 |
10,7 |
1,53 |
lion9 |
2 |
1 |
9 |
25 |
23 |
3 |
7,67 |
18,2 |
11,5 |
1,58 |
mc |
3 |
5 |
4 |
10 |
14 |
8 |
1,75 |
15,9 |
12,8 |
1,24 |
s27 |
4 |
1 |
6 |
34 |
40 |
20 |
2,0 |
27 |
19,3 |
1,40 |
shiftreg |
1 |
1 |
8 |
16 |
10 |
3 |
3,33 |
17,2 |
10,2 |
1,69 |
tav |
4 |
4 |
4 |
49 |
42 |
9 |
4,67 |
22,3 |
13,2 |
1,69 |
train11 |
2 |
1 |
11 |
25 |
24 |
3 |
8,0 |
18,6 |
10,7 |
1,74 |
train4 |
2 |
1 |
4 |
14 |
5 |
3 |
2,0 |
12,8 |
10,7 |
1,20 |
|
|
|
|
|
|
|
50,75 |
|
|
20,06 |
mid |
|
|
|
|
|
|
3,63 |
|
|
1,43 |
Анализ табл. 5 показывает, что для привед╦нных примеров применение метода синтеза автоматов класса E, по сравнению с традиционным методом синтеза, реализованном в пакете MAX+PLUSII, позволяет снизить число используемых макроячеек ПЛИС семейства FLEX 10K, в среднем, в 3,63 раза (а для отдельных примеров - в 8 раз), при этом быстродействие конечных автоматов повышается, в среднем, в 1,43 раза (для отдельных примеров - в 1,74 раза).
Таблица 6. Сравнение метода синтеза автоматов классов E и F с методом, реализованным в пакете WebPack для семейства VIRTEX2
Name |
L |
N |
M |
P |
C1 |
C2 |
C1/C2 |
D1 |
D2 |
D1/D2 |
beecount |
3 |
4 |
7 |
28 |
31 |
8 |
3,88 |
8,57 |
6,03 |
1,42 |
dk15 |
3 |
5 |
4 |
32 |
40 |
21 |
1,9 |
7,95 |
6,47 |
1,23 |
ex3 |
2 |
2 |
10 |
36 |
19 |
11 |
1,73 |
7,65 |
6,47 |
1,18 |
ex5 |
2 |
2 |
9 |
32 |
17 |
4 |
4,25 |
8,04 |
6,03 |
1,33 |
ex7 |
2 |
2 |
10 |
36 |
17 |
3 |
5,67 |
7,20 |
5,58 |
1,29 |
keyb |
7 |
2 |
19 |
170 |
99 |
81 |
1,22 |
10,61 |
7,82 |
1,36 |
lion |
2 |
1 |
4 |
11 |
8 |
3 |
2,67 |
7,61 |
5,58 |
1,36 |
lion9 |
2 |
1 |
9 |
25 |
26 |
3 |
8,67 |
7,51 |
5,58 |
1,35 |
mc |
3 |
5 |
4 |
10 |
12 |
6 |
2,0 |
7,94 |
5,93 |
1,34 |
s27 |
4 |
1 |
6 |
34 |
26 |
19 |
1,37 |
7,66 |
6,47 |
1,18 |
shiftreg |
1 |
1 |
8 |
16 |
9 |
3 |
3,0 |
6,25 |
5,13 |
1,22 |
tav |
4 |
4 |
4 |
49 |
9 |
8 |
1,13 |
7,71 |
6,03 |
1,28 |
train11 |
2 |
1 |
11 |
25 |
27 |
3 |
9,0 |
7,63 |
5,58 |
1,37 |
train4 |
2 |
1 |
4 |
14 |
6 |
3 |
2,0 |
6,53 |
5,58 |
1,17 |
|
|
|
|
|
|
|
48,49 |
|
|
18,08 |
mid |
|
|
|
|
|
|
3,46 |
|
|
1,29 |
Анализ табл. 6 показывает, что для привед╦нных примеров применение метода синтеза автоматов класса E, по сравнению с традиционным методом синтеза, реализованном в пакете WebPack, позволяет снизить число используемых макроячеек ПЛИС семейства VERTEX2, в среднем, в 3,46 раза (а для отдельных примеров - в 9 раз), при этом быстродействие конечных автоматов повышается, в среднем, в 1,29 раза (для отдельных примеров - в1,42 раза).
Выводы
Методы синтеза конечных автоматов классов E и F позволяют значительно снизить стоимость реализации и одновременно повысить быстродействие реализуемого конечного автомата.
Снижение стоимости реализации автоматов классов E и F, по сравнению с традиционными автоматами классов A и B, осуществляется за сч╦т упрощения комбинационной части автомата, поскольку значительно упрощаются функции переходов, а также уменьшается число макроячеек ПЛИС для реализации памяти автомата, так как в качестве элементов памяти используются триггеры входных буферов.
Снижению стоимости реализации автоматов классов E и F также способствует то, что в качестве кодов внутренних состояний для этих автоматов выступают элементарные конъюнкции, а не полные конъюнкции, как в традиционных моделях автоматов классов A и B.
Повышение быстродействия автоматов классов E и F, по сравнению с традиционными автоматами классов A и B, обусловлено тем, что для этих автоматов реализуются преимущественно выходные функции, которые, как правило, значительно проще функций возбуждения элементов памяти.
Для реализации автоматов класса F ПЛИС должны допускать буферизацию в регистрах (триггерах) значений входных переменных; для реализации автоматов класса E входные буферы ПЛИС должны иметь две связи, регистровую (буферизированную) и комбинационную (прямую), с внутренней логикой ПЛИС.
В некоторых случаях для реализации конечных автоматов класса F также необходимо, чтобы входные буферы ПЛИС имели две связи (буферизированную и прямую) с внутренней логикой, поскольку функции возбуждения дополнительных элементов памяти могут непосредственно зависеть от входных переменных.
Метод синтеза автоматов классов E и F не зависит от параметров ПЛИС, поэтому его можно применять для любых типов ПЛИС: основанных на концепции двух программируемых матриц или на архитектуре FPGA.
Эффективность метода синтеза автоматов классов E и F позволяет рекомендовать разработчикам архитектур ПЛИС предусматривать возможность буферизации входных переменных, прич╦м входные буферы должны иметь две связи с внутренней логикой ПЛИС: буферизированную (регистровую) и прямую (комбинационную).