Стили описания конечных автоматов на языке Verilog

PDF версия
В статье исследуются стили описания конечных автоматов на языке Verilog и рассматривается проблема выбора наилучшего способа описания с точки зрения стоимости реализации и быстродействия конечного автомата. Поставленная задача решается эмпирически путем выполнения большого количества экспериментальных исследований на эталонных примерах конечных автоматов. Предложено семь конструкций языка Verilog для описания комбинационных схем конечных автоматов, из которых выбрано две наилучшие конструкции по стоимости реализации. Представлено шесть стилей описания конечных автоматов на языке Verilog, чья эффективность исследовалась при синтезе конечных автоматов на ПЛИС трех классов: CPLD, FPGA и SoC. Показано, что выбор стиля описания позволяет уменьшить стоимость реализации конечного автомата для отдельных примеров в 3,06 раза и повысить быстродействие в 1,6 раза. В заключение указывается на возможные направления дальнейших исследований в этой области.

Введение

Разработка современных цифровых систем, как правило, требует использования языков описания аппаратуры (Hardware Description Language — HDL). На сегодняшний день широкое распространение получили два языка проектирования: VHDL и Verilog. Язык Verilog появился в среде разработчиков аппаратуры как альтернатива языку VHDL и быстро завоевал популярность среди инженеров‑практиков. К настоящему времени существует несколько стандартов языка Verilog [1–3], которые поддерживаются большинством производителей средств автоматизированного проектирования цифровых систем. В частности, язык Verilog широко применяется при проектировании цифровых систем на основе программируемых логических интегральных схем (ПЛИС), его поддерживают средства проектирования таких фирм, как Altera, Xilinx, Synopsys, Cadence, Mentor Graphics и др.

Вопрос эффективного описания конечных автоматов на языке Verilog [4] возник у разработчиков компиляторов языка в связи с необходимостью выделять из кода проекта на языке Verilog описание конечного автомата с целью его дальнейшего синтеза. Дело в том, что стандарты [1–3] языка Verilog не дают ответа на вопрос, как на языке Verilog описать конечный автомат. В то же время конечный автомат играет важную роль при проектировании цифровых систем, поскольку он является математической моделью последовательностной схемы. Практически ни одна цифровая система не обходится без использования конечных автоматов, причем каждый из них — это оригинальная последовательностная схема, которую разработчик всякий раз проектирует заново.

В указанной статье [5] детально рассмотрены стили описания конечных автоматов на языках проектирования Verilog и VHDL, которые предусмотрены в средствах проектирования фирмы Synopsys. Излагаются общие принципы представления конечных автоматов на языках HDL; предлагаются две структурные модели — с двумя и с одной комбинационной схемой; описываются методы кодирования внутренних состояний: бинарное (binary), унарное (one-hot), почти унарное (almost one-hot). Рассматривается также использование конструкций case и if при описании функций переходов для различных методов кодирования состояний, состояние для восстановления конечного автомата после ошибки (recovery), запрещенные состояния (illegal), умалчиваемые и неопределенные значения выходов. Кроме того, отдельно рассматриваются случаи, когда выход принимает значение 1(0) только в одном состоянии; установка на выходах D‑ или JK-триггеров; реализация асинхронных выходов. Отмечены также особенности неизвестных входов, когда в одни моменты времени их значения известны, а в другие — нет. Утверждается, что наибольшее быстродействие конечного автомата достигается при унарном кодировании.

В статье [6] рассматривается стандартизированный стиль описания конечных автоматов на языке Verilog, используемый в средствах проектирования фирмы Cisco. В данном стиле описание переходов конечного автомата выполняется с помощью конструкции case, внутренние состояния декларируются в виде локальных параметров, для описания переходов используются две переменные: current и next. Объясняется применение директив компилятора cisco_fsm и формирование дополнительного файла ограничений. Предлагаемый стандартизированный стиль описания конечных автоматов позволяет анализировать достижимость каждого состояния, находить терминальные состояния (из которых нет выходов), выполнять динамическую верификацию конечного автомата и строить граф конечного автомата.

В статье [7] детализируются и расширяются стили описания конечных автоматов работы [5]. При этом рассматривается два стиля описания конечных автоматов: с одним и двумя процессами, для каждой используемой конструкции отмечаются ее преимущества и недостатки; приводятся структурные модели конечных автоматов типа Мили и Мура; описываются возможные методы кодирования внутренних состояний: бинарное, Грэя, Джонсона, унарное, почти унарное, унарное с нулевым кодом состояния ожидания (idle); обсуждается использование средства Synopsys FSM Tool для генерации бинарного, Грэя и унарного кодирования. Директивы компилятора full_case и parallel_case рекомендуется применять только в случае унарного кодирования. Указывается на возможность декларирования внутренних состояний (кроме использования локальных параметров) с помощью директивы компилятора `define. Отмечаются особенности описания функций переходов и выходов конечного автомата. Предлагается стиль описания для синтеза регистровых выходов автомата Мили.

В статье [8] дальнейшее развитие получили стили описания конечных автоматов работы [7]. При этом особое внимание уделяется вопросу установки регистров на выходах конечного автомата с целью устранения помех (glitch) при переходах между состояниями. Для этого предлагается два метода, первый повторяет метод установки регистров на выходах автомата Мили [7], во втором методе для кодирования внутренних состояний используются значения выходов автомата Мура, приводится алгоритм такого кодирования. Отметим, что метод кодирования внутренних состояний, основанный на использовании значений выходов автомата Мура, впервые был описан в [9], а второй метод в [8] фактически повторяет метод кодирования внутренних состояний автоматов класса C [10].

В указанных материалах [11] исследуются стили описания конечных автоматов на языке Verilog и методы кодирования внутренних состояний, реализованные в средстве проектирования ISE фирмы Xilinx, экспериментальные исследования проводились для ПЛИС Spartan‑6. Рассматривается три стиля описания конечных автоматов: с одним, двумя и тремя процессами, а также следующие методы кодирования внутренних состояний: auto, one-hot, gray, compact, sequential, speed1, user и Johnson. Экспериментальные исследования проводились для одного простого примера конечного автомата с одним входом, одним выходом, четырьмя состояниями и пятью переходами между состояниями. Анализировались следующие параметры: число используемых триггеров, число используемых логических элементов ПЛИС и максимальная частота функционирования конечного автомата. На основании результатов экспериментальных исследований сделаны следующие выводы: проекты с несколькими процессами уменьшают число применяемых триггеров и логических элементов ПЛИС; для увеличения быстродействия конечного автомата следует прибегнуть к методам кодирования состояний one-hot и speed1, а для оптимизации площади ПЛИС — к gray, Johnson и sequential.

Проведенный анализ известных из литературы стилей описания конечных автоматов на языке Verilog показал, что рассматриваются и исследуются только такие стили описания, которые рекомендованы разработчиками средств проектирования или реализованы в этих средствах. Отметим также, что исследование в указанной статье [11] одного простого примера недостаточно для общих рекомендаций по использованию определенных стилей описаний и методов кодирования внутренних состояний конечных автоматов. Открытым остается вопрос, насколько эффективно с точки зрения реализации на ПЛИС можно описать конечный автомат, не руководствуясь рекомендациями разработчиков компиляторов языка Verilog. Таким образом, до настоящего времени не исследовались все возможные стили описания конечных автоматов, предоставляемые языком Verilog.

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

 

Особенности описания конечных автоматов на языке Verilog

В практике инженерного проектирования наибольшее распространение получили два типа конечных автоматов: автомат Мили и автомат Мура. Поведение автомата типа Мили описывается с помощью следующих уравнений:

at+1 = φ(zt, at);              (1)

wt = ψ(zt, at),

где φ— функция переходов; ψ — функция выходов; zt — входной набор в момент автоматного времени t (t = 1, 2, 3 …); wt — формируемый выходной набор; at — настоящее состояние автомата; at+1 — следующее состояние автомата.

Поведение автомата типа Мура описывается следующими уравнениями:

at+1 = φ(zt, at);             (2)

wt = y(at).

Отличительной чертой автомата Мили является то, что выходной набор wt зависит как от входного набора zt, так и от внутреннего состояния at, а в автомате Мура выходной набор wt зависит только от внутреннего состояния at. На рис. 1а и рис. 1б приведены структурные модели автоматов Мили и Мура, где комбинационная схема CLφ реализует функцию переходов, комбинационная схема CLψ реализует функцию выходов, а регистр RG, управляемый сигналом синхронизации CLK, — память конечного автомата.

Структурные модели конечных автоматов

Рис. 1. Структурные модели конечных автоматов:
а) типа Мили;
б) типа Мура

Как самый общий случай рассмотрим модель конечного автомата Мили (рис. 1а), поведение которого описывается с помощью уравнений (1). Из литературы известно три основных стиля описания конечных автоматов на языке Verilog: с тремя процессами, с двумя процессами и с одним процессом. Описание конечного автомата с помощью одного процесса возможно только для конечных автоматов типа Мура, а поскольку наиболее общей является модель автомата Мили, то в дальнейшем будут рассматриваться только два стиля описания: с тремя и с двумя процессами.

В стиле описания конечных автоматов с тремя процессами первый процесс описывает переходы между внутренними состояниями (функции переходов), которые реализуются комбинационной схемой CLφ. Второй процесс описывает выходные сигналы (функции выходов), формируемые на переходах между внутренними состояниями и реализуемые комбинационной схемой CLψ. Третий процесс описывает функционирование памяти конечного автомата. В стиле описания конечных автоматов с двумя процессами первые два процесса объединены в один.

Пример описания конечного автомата с тремя процессами:

module FSM_3 (input clk, reset, input [1:0] in, output reg [1:0] out);
    reg [1:0] state, nextstate;
    localparam [1:0] s0=0, s1=1, s2=2;
   
always @(*)                                                    // первый процесс
        casex(state)
        s0: if(in==2’b00)         nextstate=s1;
              else if(in==2’b01)  nextstate=s2;
        s1: if(in==2’b11)         nextstate=s1;
              else if(in==2’b10)  nextstate=s2;
        s2:                       nextstate=s0;
        endcase
   
always @(*)                                                    // второй процесс
        casex(state)
        s0: if(in==2’b00)         out=2’b00;
              else if(in==2’b01)  out=2’bx1;
        s1: if(in==2’b11)         out=2’b11;
              else if(in==2’b10)  out=2’b1x;
        s2:                       out=2’b00;
        endcase
   
always @(posedge clk)                                          // третий процесс
        if(~reset) state <= s0;
        else state <= nextstate;
endmodule

Прежде чем приступить к построению стилей описания конечных автоматов, остановимся на рассмотрении различных возможностей, которые предоставляет язык Verilog при описании комбинационных схем.

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

В общем случае язык Verilog не накладывает никаких ограничений на описание функционирования конечного автомата: можно использовать любые операторы языка Verilog и любые конструкции этих операторов. Обычно для проверки нахождения конечного автомата в определенном состоянии применяется оператор case, а для проверки условий перехода из некоторого состояния предлагается как оператор if (традиционно), так и оператор case. Рассмотрим различные способы использования операторов if и case для проверки условий перехода и формирования значений выходов конечного автомата.

Назовем исходным состоянием перехода (present state) внутреннее состояние, в котором начинается описываемый переход. Конечным состоянием перехода (next state) назовем состояние, в котором оканчивается переход. Разработчики компиляторов языка Verilog рекомендуют при описании конечных автоматов в операторах if и case всегда использовать дополнительные конструкции else и default, причем в качестве конечного состояния перехода в конструкциях else и default указывать исходное состояние данного перехода. Проанализируем, как это влияет на поведение конечного автомата.

Для полностью определенных конечных автоматов [12, 13] применение дополнительных конструкций else и default никак не влияет на поведение конечного автомата, поскольку данные конструкции никогда не будут выполняться. Для не полностью определенных конечных автоматов (incompletely specified finite state machine) [14] использование дополнительных конструкций else и default доопределяет неопределенные переходы из каждого состояния переходом в исходное состояние перехода. Фактически не полностью определенный конечный автомат заменяется полностью определенным конечным автоматом. Поскольку в не полностью определенных конечных автоматах гарантируется, что на входах конечного автомата никогда не появятся входные наборы, соответствующие неопределенным условиям перехода, то такое доопределение никак не влияет на поведение конечного автомата. Таким образом, использование дополнительных конструкций else и default не оказывает влияния на поведение конечного автомата, однако это позволяет в ряде случаев значительно снизить стоимость реализации комбинационных схем CLφ и CLψ.

Предлагаемые конструкции использования операторов if и case будем сопровождать примерами определения значений выходного вектора out в зависимости от значений входного вектора in (в случае определения значений следующего состояния конструкции операторов if и case выглядят аналогично). При описании комбинационных схем конечных автоматов возможны следующие варианты использования оператора if:

1. IF_1 — проверка каждого условия перехода с помощью отдельного оператора if (считалось, что данный подход приводит к минимальной сложности реализации):

if (in==2`b00)               out = 2`b11;
if (in==2`b01)               out = 2`b01;
if (in==2`b10)               out = 2`b10;

2. IF_2 — проверка первого условия перехода из некоторого состояния с помощью оператора if, а проверка каждого следующего условия перехода с помощью конструкции else if (традиционный подход при описании не полностью определенных конечных автоматов):

if (in==2`b00)            out = 2`b11;
else if (in==2`b01)       out = 2`b01;
else if (in==2`b10)       out = 2`b10;

3. IF_3 — вариант повторяет предыдущий случай, за исключением того, что последнее условие перехода из некоторого состояния реализуется с помощью конструкции else (традиционный подход при описании полностью определенных конечных автоматов):

if (in==2`b00)            out = 2`b11;
else if (in==2`b01)       out = 2`b01;
else                      out = 2`b10;

4. IF_4 — вариант повторяет конструкцию IF_2, за исключением того, что добавляется конструкция else, с помощью которой реализуется возврат в исходное состояние перехода, при описании функций перехода, нулевой или неопределенный выходной набор, при описании выходных функций:

if (in==2`b00)           out = 2`b11;
else if (in==2`b01)      out = 2`b01;
else if (in==2`b10)      out = 2`b10;
else                     out = 2`b00;     // или out = 2`bxx;.

Аналогично при описании комбинационных схем конечных автоматов возможны следующие варианты использования оператора case:

5. CASE_1 — проверка каждого условия перехода с помощью отдельной константы, соответствующей значению набора входных переменных (традиционный подход при описании не полностью определенных конечных автоматов):

case (in)
2`b00: out = 2`b11;
2`b01: out = 2`b01;
2`b10: out = 2`b10;
endcase

6. CASE_2 — вариант повторяет предыдущий случай, за исключением того, что последнее условие перехода из некоторого состояния реализуется с помощью конструкции default (традиционный подход при описании полностью определенных конечных автоматов):

case (in)
2`b00:   out = 2`b11;
2`b01:   out = 2`b01;
default: out = 2`b10;
endcase

7. CASE_3 — вариант повторяет случай CASE_1, за исключением того, что добавляется конструкция default, с помощью которой реализуется возврат в исходное состояние перехода, при описании функций перехода, нулевой или неопределенный выходной набор, при описании выходных функций:

case (in)
2`b00:   out = 2`b11;
2`b01:   out = 2`b01;
2`b10:   out = 2`b10;
default: out = 2`b00;    // или out = 2`bxx;
endcase

Отметим, что при описании переходов в конструкции IF_4 после последнего else и в конструкции CASE_3 после default указывается переход в исходное состояние перехода, а также переход в начальное состояние (s0), состояние восстановления (recovery) и др. Таким образом, имеем семь вариантов описания комбинационных схем конечных автоматов на языке Verilog.

Пример варианта IF_1 для трех условий переходов из некоторого состояния:

module IF_1_3 (input clk, reset, input [1:0] in, output reg [1:0] out);
    reg [1:0] out_t;
    always @(*)  begin        /* вариант IF_1 */
                if (in==2`b00)     out = 2`b11;
                if (in==2`b01)     out = 2`b01;
                if (in==2`b10)     out = 2`b10;
    end
    always @(posedge clk)    /* описание функционирования памяти */
                if(~reset)         out <= 6’bx;
                else               out <= out_t;
endmodule

Для имитации переключения между состояниями конечного автомата в данное описание включены входные сигналы clk и reset, а также процесс, формирующий значение выходного набора на регистровом выходе. Примеры других вариантов применения операторов if и case для проверки различного количества условий переходов строятся аналогично.

Экспериментальные исследования эффективности конструкций языка Verilog для описания комбинационных схем конечных автоматов выполнялись для 19 примеров, каждый из которых отличался от другого числом проверяемых условий. Синтез комбинационных схем проводился с помощью пакета Quartus II версии 13.0 для ПЛИС семейства Cyclone III. В качестве критерия оптимизации была принята стоимость реализации: число логических элементов, необходимых для реализации схемы. Результаты экспериментальных исследований приведены в таблице 1, где ex_n — название примера; n — число проверяемых условий, n ∈ [3, 21]; IF_1, …, IF_4 — варианты описания с оператором if; CASE_1, …, CASE_3 — варианты описания с оператором case; Cmax и Cmin — максимальное и минимальное значение стоимости реализации для данного примера при различных вариантах описания; Cmax/Cmin — отношение соответствующих параметров; mid — среднее значение параметров.

Таблица 1. Результаты экспериментальных исследований стилей описания комбинационных схем конечных автоматов

Примеры

IF_1

IF_2

IF_3

IF_4

CASE_1

CASE_2

CASE_3

Cmax

Cmin

Cmax/Cmin

ex_3

7

7

3

3

7

3

3

7

3

2,33

ex_4

6

7

3

3

3

3

3

7

3

2,33

ex_5

10

10

4

4

10

5

5

10

4

2,5

ex_6

10

10

4

4

10

5

5

10

4

2,5

ex_7

10

10

4

4

11

6

6

11

4

2,75

ex_8

9

9

3

3

4

3

3

9

3

3

ex_9

17

17

5

5

13

7

7

17

5

3,4

ex_10

15

14

6

6

13

7

7

15

6

2,5

ex_11

18

17

8

8

14

8

8

18

8

2,25

ex_12

13

13

5

5

9

6

6

13

5

2,6

ex_13

15

18

7

7

14

8

8

18

7

2,57

ex_14

15

14

6

6

14

8

8

15

6

2,5

ex_15

16

17

7

7

9

8

8

17

7

2,43

ex_16

9

12

4

4

5

4

4

12

4

3

ex_17

23

21

7

7

11

7

7

23

7

3,29

ex_18

22

17

7

7

10

7

7

22

7

3,14

ex_19

28

23

10

10

11

10

10

28

10

2,8

ex_20

18

18

6

6

8

7

7

18

6

3

ex_21

26

22

9

9

11

10

10

26

9

2,89

mid

15,11

14,53

5,68

5,68

9,84

6,42

6,42

15,58

5,68

2,73

Анализ таблицы 1 показывает, что варианты описания IF_3 и IF_4 с оператором if, а также варианты CASE_2 и CASE_3 с оператором case дают одинаковые результаты. Наилучшие результаты по стоимости реализации позволяют получить варианты описаний IF_3 и IF_4, за ними следуют варианты описаний CASE_2 и CASE_3. Отметим, что вариант IF_1 не оправдал ожидания, именно при использовании варианта описания IF_1 получены наихудшие результаты, за ним следует вариант описания IF_2.

Главный вывод, который можно сделать из проведенных экспериментальных исследований, — стили описания комбинационных схем конечных автоматов в значительной мере влияют на стоимость реализации. На это указывает отношение Cmax/Cmin, значение которого в среднем составляет 2,73 (для отдельных примеров 3,4 раза).

Для дальнейших исследований стилей описания конечных автоматов были выбраны конструкции IF_4 и CASE_3, поскольку они обеспечивают малую стоимость реализации и предоставляют дополнительные возможности при описании конечных автоматов.

 

Стили описания конечных автоматов

Рассмотрим два основных стиля описания конечных автоматов на языке Verilog: с тремя и с двумя процессами. Описание конечных автоматов с тремя процессами содержит один процесс для описания комбинационной схемы CLϕ, реализующей функции переходов, второй процесс для описания комбинационной схемы CLψ, реализующей функции выходов, и третий процесс, описывающий переключение памяти конечного автомата. В описании конечных автоматов с двумя процессами комбинационные схемы CLϕ и CLψ представляются с помощью одного процесса.

Каждая комбинационная схема конечного автомата описывается либо с помощью конструкции IF_4 оператора if, либо с помощью конструкции CASE_3 оператора case. Таким образом, можно построить шесть стилей описания конечных автоматов M_1, …, M_6, которые приведены в таблице 2.

Таблица 2. Стили описания конечных автоматов

Стиль описания

Число процессов

Описание комбинационной
схемы CLϕ

Описание комбинационной
схемы CLψ

M_1

3

IF_4

IF_4

M_2

3

CASE_3

IF_4

M_3

3

IF_4

CASE_3

M_4

3

CASE_3

CASE_3

M_5

2

IF_4

M_6

2

CASE_3

Традиционным стилям описания, когда для проверки значений входных переменных используется оператор if, соответствуют M_1, для описаний с тремя процессами, и M_5, для описаний с двумя процессами.

Фрагмент описания конечного автомата с конструкцией IF_4:

casex(state)                                                
s0:   if(in==2’b00)                 nextstate=s1;
        else if(in==2’b01)          nextstate=s2;
        else if(in==2’b11)          nextstate=s3;
        else                        nextstate=s0;
s1:   if(in==2’b10)                 nextstate=s2;
        else if(in==2’b00)          nextstate=s0;
        else if(in==2’b01)          nextstate=s3;
        else                        nextstate=s1;
…
endcase

Фрагмент описания конечного автомата с конструкцией CASE_3:

casex(state)
s0:   casex(in)
        2’b00:         nextstate=s1;
        2’b01:         nextstate=s2;
        2’b11:         nextstate=s3;
        default:       nextstate=s0;
        endcase


s1:   casex(in)
        2’b10:         nextstate=s2;
        2’b00:         nextstate=s0;
        2’b01:         nextstate=s3;
        default:       nextstate=s1;
        endcase
…
endcase

Отметим, что здесь в конструкции CASE_3 вместо оператора case использован оператор casex, поскольку наборы значений входных переменных конечных автоматов могут содержать неопределенные значения.

Исследование эффективности стилей описания конечных автоматов на языке Verilog проводилось на эталонных примерах, разработанных в центре MCNC [15]. Синтез конечных автоматов выполнялся на трех семействах ПЛИС, относящихся к трем классам ПЛИС: MAX II — сложные программируемые логические устройства (Complex Programmable Logic Devices — CPLD), Cyclone III — программируемые пользователем вентильные матрицы (Field Programmable Gate Arrays — FPGA) и Stratix III — системы на одном кристалле (System on Chip — SoP). Для синтеза использовался пакет Quartus II версии 13.0 с параметрами логического синтеза, заданными по умолчанию. В качестве критериев оптимизации рассматривались стоимость реализации (число используемых логических элементов) и частота функционирования конечных автоматов. Следует отметить, что стиль описания влияет не на все эталонные примеры конечных автоматов. Из 44 эталонных примеров только в 23 наблюдается заметное влияние стиля описания на стоимость реализации или частоту функционирования. Поэтому в дальнейшем рассматривались только такие примеры.

Результаты экспериментальных исследований для семейства MAX II по стоимости реализации и частоте функционирования приведены в таблицах 3 и 4 соответственно, где FSM — имя эталонного примера; C_n и F_n — стоимость реализации и частота функционирования (в МГц) конечных автоматов при использовании описания M_n, n  [1,6]; Cmin, Cmax, Fmin и Fmax — минимальное и максимальное значение стоимости реализации и частоты функционирования при различных стилях описания для одного и того же примера; Cmax/Cmin, Fmax/Fmin — отношение соответствующих параметров.

Таблица 3. Сравнение стилей описания конечных автоматов для ПЛИС семейства MAXII по стоимости реализации

FSM

C_1

C_2

C_3

C_4

C_5

C_6

Cmin

Cmax

Cmax/Cmin

BBARA

33

30

29

29

33

29

29

33

1,14

BBSSE

57

57

58

58

57

58

57

58

1,02

BEECOUNT

21

21

14

14

21

14

14

21

1,5

CSE

104

103

101

101

104

98

98

104

1,06

DK14

40

41

39

39

40

39

39

41

1,05

DK15

17

16

16

16

17

16

16

17

1,06

EX1

132

129

121

118

138

118

118

138

1,17

EX3

24

27

22

22

24

22

22

27

1,23

EX5

19

21

20

20

19

20

19

21

1,11

EX6

55

58

56

56

55

56

55

58

1,05

KEYB

83

80

100

87

83

87

80

100

1,25

PLANET

210

224

225

230

216

230

210

230

1,1

S1

160

166

157

156

164

156

156

166

1,06

S1488

211

221

212

212

212

212

211

221

1,05

S1494

209

218

217

219

213

219

209

219

1,05

S208

24

55

41

41

18

41

18

55

3,06

S386

59

59

64

64

61

64

59

64

1,08

S420

34

18

19

19

34

19

18

34

1,89

S820

128

138

137

137

128

137

128

138

1,08

S832

135

132

132

132

134

132

132

135

1,02

SAND

209

213

199

198

208

198

198

213

1,08

STYR

249

252

216

221

258

225

216

258

1,19

TBK

434

328

422

298

449

282

282

449

1,59

mid

115,09

113,35

113,78

108,13

116,78

107,48

103,65

121,74

1,26

 

Таблица 4. Сравнение стилей описания конечных автоматов для ПЛИС семейства MAXII по быстродействию

FSM

F_1

F_2

F_3

F_4

F_5

F_6

Fmin

Fmax

Fmax/Fmin

BBARA

221

203

225

225

221

225

203

225

1,11

BBSSE

155

138

156

156

155

156

138

156

1,13

BEECOUNT

304

304

284

284

304

284

284

304

1,07

CSE

131

123

127

127

131

124

123

131

1,07

DK14

234

192

223

223

234

223

192

234

1,22

DK15

258

413

389

389

258

389

258

413

1,6

EX1

111

144

139

137

127

137

111

144

1,3

EX3

256

230

206

206

256

206

206

256

1,24

EX5

266

229

216

216

266

216

216

266

1,23

EX6

211

195

171

171

211

171

171

211

1,23

KEYB

143

136

112

114

143

114

112

143

1,28

PLANET

111

108

100

91

111

91

91

111

1,22

S1

113

119

111

120

120

120

111

120

1,08

S1488

114

112

112

112

108

112

108

114

1,06

S1494

119

121

105

114

121

114

105

121

1,15

S208

265

192

240

240

253

240

192

265

1,38

S386

166

149

176

176

145

176

145

176

1,21

S420

278

306

319

319

278

319

278

319

1,15

S820

97

115

118

124

107

124

97

124

1,28

S832

118

128

117

114

116

114

114

128

1,12

SAND

105

108

110

109

114

109

105

114

1,09

STYR

91

98

110

101

109

118

91

118

1,3

TBK

86

80

97

83

82

93

80

97

1,21

mid

171, 87

171,43

172,3

171,78

172,61

172,83

153,52

186,52

1,21

Анализ таблиц 3 и 4 показывает, что для ПЛИС семейства MAX II отношение между максимальной и минимальной стоимостью реализации в среднем составляет 1,26 раза, а для отдельных примеров — 3,06 раза (пример S208); отношение между максимальной и минимальной частотой функционирования в среднем составляет 1,2 раза, а для отдельных примеров — 1,6 раза (пример DK14). Наилучшим стилем описания конечных автоматов для семейства MAX II по стоимости реализации является M_6, а по быстродействию — M_2.

Аналогичные исследования также проводились для семейств Cyclone III и Stratix III. Результаты анализа экспериментальных исследований приведены в таблице 5, где Cmax/Cmin — наибольшее отношение максимальной и минимальной стоимости реализации для различных стилей описания; Fmax/Fmin — то же, только для частоты функционирования.

Из таблицы 5 следует, что путем выбора стиля описания конечного автомата стоимость реализации может быть уменьшена в 3,06 раза для семейства MAX II, в 2,5 раза для семейства Cyclone III и в 1,69 раза для семейства Stratix III. Аналогично быстродействие конечного автомата может быть увеличено в 1,6 раза для семейства MAX II, в 1,46 раза для семейства Cyclone III и в 1,33 раза для семейства Stratix III.

Таблица 5. Отношение наилучших и наихудших результатов для различных семейств

Семейство

Cmax/Cmin

Fmax/Fmin

MAX II

3,06

1,6

Cyclone III

2,5

1,46

Stratix III

1,69

1,33

Лучшие стили описания по стоимости реализации и по быстродействию для различных семейств приведены в таблице 6.

Таблица 6. Лучшие стили описания конечных автоматов для различных семейств

Семейство

По стоимости

По быстродействию

MAX II

M_6

M_2

Cyclone III

M_6

M_2

Stratix III

M_4

M_1

Отметим, что из шести рассмотренных стилей описания конечных автоматов в таблице 6 присутствует только один традиционный стиль M_1, который обеспечивает максимальное быстродействие для семейства Stratix III.

Проведенные исследования показали, что стиль описания конечных автоматов на языке Verilog оказывает существенное влияние как на стоимость реализации конечного автомата (для отдельных примеров в 3,06 раза), так и на частоту функционирования (для отдельных примеров в 1,6 раза). Поэтому в рамках пакета ZUBR [16] была разработана программа автоматического формирования описаний конечного автомата на языке Verilog по его представлению в виде списка переходов на языке KISS2 [15]. Данная программа позволяет сформировать описания конечного автомата на языке Verilog в соответствии с предложенными стилями M_1, …, M_6 и выбрать из них наиболее подходящее описание по стоимости и (или) быстродействию.

 

Заключение

Язык Verilog предоставляет большое разнообразие стилей описания конечных автоматов, которые до настоящего времени исследованы не полностью. Традиционные стили описания конечных автоматов не всегда являются лучшими с точки зрения стоимости реализации и быстродействия, поскольку они, как правило, рекомендуются разработчиками компиляторов и связаны с необходимостью выделять из кода проекта описание конечного автомата.

Стиль описания конечного автомата на языке Verilog значительно влияет на стоимость реализации (для наших примеров в среднем в 2,71 раза) и быстродействие конечного автомата. Результаты настоящего исследования имеют большое практическое значение, позволяя без применения каких-либо специальных методов синтеза заметно уменьшить стоимость реализации и повысить быстродействие конечных автоматов.

В то же время исследованы далеко не все возможные способы описания конечных автоматов на языке Verilog, в частности, не рассматривались такие стили описания, как неявное описание конечного автомата, использование операторов непрерывного назначения, описание конечного автомата в виде нескольких отдельных модулей (например, комбинационной схемы и регистра) и др. Для проверки нахождения конечного автомата в определенном состоянии традиционно (а также в данной работе) используется оператор case, но с этой же целью можно применять различные конструкции оператора if. Отдельно стоит вопрос разработки и исследования стилей описания конечных автоматов типа Мура, поскольку модель автомата Мура широко распространена и является очень популярной среди разработчиков цифровой аппаратуры. Все эти вопросы требуют дальнейшего тщательного исследования.

Предложенная методика построения и выбора эффективных стилей описания конечных автоматов на языке Verilog применена для ПЛИС фирмы Altera. Подобные исследования могут быть проведены для ПЛИС других производителей. Аналогичную методику можно также использовать для исследования стилей описания конечных автоматов на языке VHDL.

Литература
  1. IEEE Std 1364-1995, IEEE Standard Hardware Description Language Based on the Verilog Hardware Description Language / The Institute of Electrical and Electronics Engineers, Inc. New York, NY, USA.
  2. IEEE Std 1364-2001 (Revision of IEEE Std 1364-1995), IEEE Standard Verilog Hardware Description Language, IEEE Computer Society / The Institute of Electrical and Electronics Engineers, Inc. New York, NY, USA.
  3. IEEE Std 1364.1-2002, IEEE Standard for Verilog Register Transfer Level Synthesis/The Institute of Electrical and Electronics Engineers, Inc. New York, NY, USA.
  4. Соловьев В. В. Основы языка проектирования цифровой аппаратуры Verilog. М.: Горячая линия– Телеком, 2014.
  5. Golson S. State machine design techniques for Verilog and VHDL // Synopsys Journal of High-Level Design. 1994. Vol. 9.
  6. Wang T. H., Edsall T. Practical FSM analysis for Verilog // Proc. of the Int. Conf. Verilog HDL Conference and VHDL International Users Forum (IVC/VIUF), March 1998, IEEE, 1998.
  7. Cummings C. E. State machine coding styles for synthesis // Proc. of the Conf. Synopsys Users Group (SNUG’98), March 1998, USA, San Jose, CA, Synopsys, 1998.
  8. Cummings C. E. Coding and scripting techniques for FSM designs with synthesis-optimized, glitch-free outputs // Proc. of the Conf. Synopsys Users Group (SNUG’2000), 2000, USA, Boston, MA, Synopsys, 2000.
  9. Соловьев В. В. Синтез микропрограммных автоматов напрограммируемых матрицах логики // Известия Академии наук Беларуси. Сер. физ.-техн. наук. 1994. № 1.
  10. Соловьев В. В. Проектирование цифровых систем на основе программируемых логических интегральных схем. М.: Горячая линия– Телеком, 2001.
  11. Uma R., Dhavachelvan P. Finite state machine optimization in FPGAs // Proc. of the Second International Conference on Computational Science, Engineering and Information Technology, October 2012, ACM, 2012.
  12. Климович А. С., Соловьев В. В. Метод минимизации конечных автоматов типа Мура путем склеивания двух состояний // Известия Российской академии наук. Теория и системы управления. 2011. № 6.
  13. Климович А. С., Соловьев В. В. Минимизация конечных автоматов Мили путем склеивания двух внутренних состояний // Известия Российской академии наук. Теория и системы управления. 2012. № 2.
  14. Климович А. С., Соловьев В. В. Минимизация неполностью определенных конечных автоматов Мили путем склеивания двух внутренних состояний // Известия Российской академии наук. Теория и системы управления. 2013. № 
  15. Yang S. Logic synthesis and optimization benchmarks user guide. Version 3.0. Technical Report. North Carolina. Micro-electronics Center of North Carolina. 1991.
  16. Salauyou V., Klimowicz A., Grzes T., Bulatowa I., Dimitrowa-Grekow T. Synthesis methods of finite state machines implemented in package ZUBR // Proc. of the Sixth International Conference Computer-Aided Design of Discrete Devices (CAD DD’7), 14–15 November, 2007, Minsk, UIIP NASB, 2007.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *