Хабрахабр

FPGA для программиста, конечные автоматы (verilog)

Стиль описания конечного автомата как образ мышления

Когда нужно преодолеть врожденную параллельность FPGA, и появляется желание заставить схему работать последовательно, по алгоритму, на помощь приходят конечные автоматы, про которые написано не мало академических и практических трудов.

Например, очень популярной является работа: Clifford E. Cummings, The Fundamentals of Efficient Synthesizable Finite State Machine Design using NC-Verilog and BuildGates. Всякий раз, когда специалисты решают обсудить, как правильно писать конечные автоматы, кто-то обязательно достает эту публикацию.

Статья стала настолько авторитетной, что многие даже не стараются анализировать аргументы автора. В частности, бытует мнение, что профессионалы всегда используют двухчастный способ описания конечных автоматов, имеется ввиду, описание конечных автоматов в 2 always блока. Это утверждение продолжает вызывать жаркие споры, и я хочу пояснить различия в описаниях конечного автомата с разным количество always блоков.

В беседах с коллегами я понял, что споры о том, как надо писать конечные автоматы в 1 или 2, 3 always блока, связаны с разным представлением (осознанием) реализуемого алгоритма, разным типом мышления. Попробую показать это на примере.

Я полагаю, что эта статья не первая статья о FSM и Verilog в вашей жизни, поэтому я не буду объяснять ни что такое конечный автомат, ни как он описывается на Verilog, а перейду сразу к делу.
Представьте, вы сидите дома, вам нужно сходить в магазин, купить хлеба, и вернуться обратно. Реализовать такое поведение просто — это алгоритмическая последовательность действий, ее можно описать так:

  • Одеться и выйти на улицу
  • Пойти в магазин, взять хлеб
  • Оплатить его в кассе
  • Вернуться домой и раздеться

Для многих такое описание покажется естественным. Четкая последовательность действий, похожа на строки программы. Однако, тот же алгоритм можно описать и по другому:

  • Из дома направиться на улицу
  • С улицы направиться в магазин (хлебный отдел)
  • Из хлебного одела направиться в кассу
  • Из кассы направиться домой

при этом

  • когда мы дома — мы раздеты
  • когда мы на улице — мы одеты
  • когда мы в магазине (хлебном отделе) — мы берем хлеб
  • когда мы у кассы — мы платим деньги

Интересно, хоть кто-то сейчас подумал, что последний вариант логичнее, чем первый?

Так или иначе, оба этих описания имеют представление в виде конечного автомата. Первое в виде описания с одним always блоком, а второе — с двумя или тремя. Оговорюсь, что описание в 2 и 3 always блока — это близнецы-братья, отличаются только техническими нюансами, которые нам сейчас не важны.

Покажем, как описания представляются в виде автомата:
У нас есть состояния автомата: HOME_STATE, STREET_STATE, MARKET_STATE, CASHIER_STATE, есть выходы автомата (наши действия): GET_DRESSED_ACT, UNDRESS_ACT, TAKE_BREAD_ACT, PAY_MONEY_ACT

Описание с 1 always блоком, выглядит так:

always @(posedge clk) begin if(reset) begin State <= HOME_STATE; Action <= UNDRESS_ACT; end //--------------------------------- else begin case(State) //----------------------------- HOME_STATE: begin Action <= GET_DRESSED_ACT; //одеться State <= STREET_STATE; //и пойти на улицу end //----------------------------- STREET_STATE: begin State <= MARKET_STATE; //пойти в магазин Action <= TAKE_BREAD_ACT; //взять хлеб end //----------------------------- MARKET_STATE: begin State <= CASHIER_STATE; //пойти в кассу Action <= PAY_MONEY_ACT; //оплатить хлеб end //----------------------------- CASHIER_STATE: begin State <= HOME_STATE; //пойти домой Action <= UNDRESS_ACT; //и раздеться end //----------------------------- default: //если не знаем где мы (чего быть не может, но вдруг) begin State <= HOME_STATE; //идём домой Action <= UNDRESS_ACT; //и раздеваемся end endcase end end

Теперь описание с 2 alwaysблоками:

//технический блок для организации переходов always @(posedge clk) begin if(reset) State <= HOME_STATE; else State <= NextState; end //блок работы автомата: выбор перехода и действия
always @(*) begin case(Sate) //----------------------------- HOME_STATE: //когда мы дома begin Action = UNDRESS_ACT; //мы раздеты NextState = STREET_STATE; //собираемся идти на улицу end //----------------------------- STREET_STATE: //когда мы на улице begin Action = GET_DRESSED_ACT; //мы одеты NextState = MARKET_STATE; //собираемся в магазин end //----------------------------- MARKET_STATE: //когда мы в магазине begin Action = TAKE_BREAD_ACT; //берем хлеб NextState = CASHIER_STATE; //собираемся в кассу end //----------------------------- CASHIER_STATE: //когда мы у кассы begin Action = PAY_MONEY_ACT; //мы платим деньги NextState = HOME_STATE; //собираемся пойти домой end //----------------------------- default://если не знаем где мы (чего быть не может, но вдруг) begin NextState = HOME_STATE; //мы хотим домой Action = GET_DRESSED_ACT; //мы одеты (на всякий случай) end endcase end

Хочу обратить внимание на особенности этих 2 описаний, которые и являются причиной священной войны за число блоков always.
1 always блок

 HOME_STATE: begin Action <= GET_DRESSED_ACT; //одеться State <= STREET_STATE; //и пойти на улицу end

2 always блока

 HOME_STATE: //когда мы дома begin Action = UNDRESS_ACT; //мы раздеты NextState = STREET_STATE; //собираемся идти на улицу end

Автомат с 1 always блоком в текущем состоянии определяет, какие действия он собирается делать дальше, не заботясь о том, что он делает сейчас. А автомат с 2 always блоками, в текущем состояние определяет, что он делает сейчас, и его не заботит, что он будет делать дальше или делал до этого.

Нельзя однозначно сказать какое поведение лучше или правильнее. Все сильно зависит от задачи, от реализуемого автоматом алгоритма. Для демонстрации изменим ситуацию. Теперь у вас есть дом, работа, бар. Вы ходите на работу — работать, в бар — пить пиво. В бар вы ходите как из дома по выходным, так и с работы в пятницу.

В первой реализации, с 1 always, вам надо внимательно следить куда вы собираетесь идти чтобы случайно не начать пить пиво на работе или работать в баре. Во второй реализации, с 2 always блоками, вы защищены от этого. Тут все четко определено: состояние на работе — работаем, состояние в баре — пьем пиво.

С другой стороны, в описании с 2 always блоками, придя в бар с работы, вы не сможете не пить пиво. Состояние в этой реализации жестко фиксирует действие бар — пьем пиво. А в описании с 1 always блоком, ваши действия в баре определяются в момент выхода из прошлого состояния. С работы вы можете пойти в бар и выпить виски. Каждый второй поход из дома в бар может заканчиваться вечеринкой. Текущее состояние в баре никак вас не ограничивает.

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

Если у вас сложная сеть переходов и в разные состояния вы попадаете многими путями, имеет смысл использовать схему с 2 always блоками. У вас не будет шанса забыть задать какой то из выходов автомата при очередном переходе.

С другой стороны, если вы пишите простой автомат с практически линейной структурой, можно использовать описание с 1 always блоком. Фактически вы задаете последовательность на выходе, а состояния используете просто для организации последовательного выполнения. Так как выходы автомата не зависят от текущего состояния, не надо будет прописывать их значение в каждом состоянии, описание будет короче и логичнее.

В статье, с которой мы начали, хорошо показано почему надо использовать описания с 2 и 3 always блоками, а описание с 1 always блоком отмечено как самое плохое. Автор рекомендует избегать такого описания. Поэтому хочется привести пример реального интерфейса удобного для описания в 1 always блок и защитить данный вид описания. Для сравнения я приведу тот же автомат описанный в 3 always блока. Необходимо 3, а не 2 блока, потому, что мы будем использовать регистровые выходные сигналы.

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

Основной смысл модуля по стробу чтения либо записи «развернуть времянку», выдержать заданные интервалы, а по завершению выдать 1 тактовый сигнал готовности. Нам необходимо соблюдать следующие интервалы

  • Rs — время установки адреса и сигнала выбора памяти перед чтением
  • Rp — время выдержки сигнала разрешения выхода памяти до появления корректных данных
  • Rh — время выдержки сигнала выбора памяти после снятия разрешения выхода
  • Ws — время установки адреса, данных и сигнала выбора памяти перед записью
  • Wp — длительность выставления сигнала разрешения записи
  • Wh — время выдержки данных и адреса после снятия сигнала разрешения записи

Интервалы мы будем измерять в количестве тактов входной частоты и зададим интервалы константами READ_SETUP, READ_PULSE, READ_HOLD и WRITE_SETUP, WRITE_PULSE, WRITE_HOLD.

Описание с 1 always блоком:

module mem_ctrl_1
( //system side input clk, input reset, input w_strb, input r_strb, input [7:0] s_waddress, input [7:0] s_raddress, input [7:0] s_data_to, output reg [7:0] s_data_from, output reg done, //memory side output reg [7:0] m_address, output reg [7:0] m_data_to, input [7:0] m_data_from, output reg cs_n, output reg oe_n, output reg we
); //------------------------------------------------------
parameter PAUSE_CNT_SIZE = 16; parameter READ_SETUP = 5;
parameter READ_PULSE = 3;
parameter READ_HOLD = 1; parameter WRITE_SETUP = 5;
parameter WRITE_PULSE = 3;
parameter WRITE_HOLD = 1; //------------------------------------------------------
reg [PAUSE_CNT_SIZE - 1 : 0] PCounter; //------------------------------------------------------
reg [3:0] State; localparam [3:0] IDLE = 0; localparam [3:0] PREPARE_READ = 1;
localparam [3:0] READ = 2;
localparam [3:0] END_READ = 3; localparam [3:0] PREPARE_WRITE = 4;
localparam [3:0] WRITE = 5;
localparam [3:0] END_WRITE = 6; //------------------------------------------------------
always @(posedge clk) begin if(reset) begin done <= 1'b0; m_address <= 8'd0; m_data_to <= 8'd0; s_data_from <= 8'd0; cs_n <= 1'b1; oe_n <= 1'b1; we <= 1'b0; State <= IDLE; PCounter <= 0; end else begin //счётчик всегда считает до 0 if(PCounter != 0) PCounter <= PCounter - 1'b1; //всегда снимаем сигнал готовности, //он не больше 1 такта done <= 1'b0; case(State) //-------------------------- IDLE: begin if(w_strb == 1'b1) //запрос записи begin cs_n <= 1'b0; m_data_to <= s_data_to; State <= PREPARE_WRITE; m_address <= s_waddress; PCounter <= WRITE_SETUP; end else if(r_strb == 1'b1) //запрос чтения begin cs_n <= 1'b0; m_address <= s_raddress; State <= PREPARE_READ; PCounter <= READ_SETUP; end end //-------------------------- PREPARE_READ: begin if(PCounter == 0) begin State <= READ; oe_n <= 1'b0; PCounter <= READ_PULSE; end end //-------------------------- READ: begin if(PCounter == 0) begin State <= END_READ; oe_n <= 1'b1; PCounter <= READ_HOLD; s_data_from <= m_data_from; end end //-------------------------- END_READ: begin if(PCounter == 0) begin State <= IDLE; cs_n <= 1'b1; done <= 1'b1; end end //-------------------------- PREPARE_WRITE: begin if(PCounter == 0) begin State <= WRITE; we <= 1'b1; PCounter <= WRITE_PULSE; end end //-------------------------- WRITE: begin if(PCounter == 0) begin State <= END_WRITE; we <= 1'b0; PCounter <= WRITE_HOLD; end end //-------------------------- END_WRITE: begin if(PCounter == 0) begin State <= IDLE; cs_n <= 1'b1; done <= 1'b1; end end //-------------------------- default: //невозможная ситуация begin done <= 1'b0; m_address <= 8'd0; m_data_to <= 8'd0; s_data_from <= 8'd0; cs_n <= 1'b1; oe_n <= 1'b1; we <= 1'b0; State <= IDLE; end endcase end end endmodule

Описание с 3 always блоками:

module mem_ctrl_3
( //system side input clk, input reset, input w_strb, input r_strb, input [7:0] s_waddress, input [7:0] s_raddress, input [7:0] s_data_to, output reg [7:0] s_data_from, output reg done, //memory side output reg [7:0] m_address, output reg [7:0] m_data_to, input [7:0] m_data_from, output reg cs_n, output reg oe_n, output reg we
); //------------------------------------------------------
parameter PAUSE_CNT_SIZE = 16; parameter READ_SETUP = 5;
parameter READ_PULSE = 3;
parameter READ_HOLD = 1; parameter WRITE_SETUP = 5;
parameter WRITE_PULSE = 3;
parameter WRITE_HOLD = 1; //------------------------------------------------------
reg [PAUSE_CNT_SIZE - 1 : 0] PCounter; //------------------------------------------------------
reg [3:0] State;
reg [3:0] NextState; localparam [3:0] IDLE = 0; localparam [3:0] PREPARE_READ = 1;
localparam [3:0] READ = 2;
localparam [3:0] END_READ = 3; localparam [3:0] PREPARE_WRITE = 4;
localparam [3:0] WRITE = 5;
localparam [3:0] END_WRITE = 6; //------------------------------------------------------
//технический блок
always @(posedge clk) begin if(reset) State <= IDLE; else State <= NextState; end //------------------------------------------------------
//выбор перехода always @(*) begin //по умолчанию сохраняем текущее состояние NextState = State; case(State) //-------------------------------------- IDLE: begin if(w_strb == 1'b1) //запрос записи begin NextState = PREPARE_WRITE; end else if(r_strb == 1'b1) //запрос чтения begin NextState = PREPARE_READ; end end //-------------------------------------- PREPARE_READ: begin if(PCounter == 0) begin NextState = READ; end end //-------------------------------------- READ: begin if(PCounter == 0) begin NextState = END_READ; end end //-------------------------------------- END_READ: begin if(PCounter == 0) begin NextState = IDLE; end end //-------------------------------------- PREPARE_WRITE: begin if(PCounter == 0) begin NextState = WRITE; end end //-------------------------------------- WRITE: begin if(PCounter == 0) begin NextState = END_WRITE; end end //-------------------------------------- END_WRITE: begin if(PCounter == 0) begin NextState = IDLE; end end //-------------------------------------- default: NextState = IDLE; endcase end //-------------------------------------------
//задание выхода
always @(posedge clk) begin if(reset) begin cs_n <= 1'b1; oe_n <= 1'b1; we <= 1'b0; end else begin //чтобы значение выхода изменялось вместе с изменением //состояния, а не на следующем такте, анализируем NextState case(NextState) //-------------------------------------- IDLE: begin cs_n <= 1'b1; oe_n <= 1'b1; we <= 1'b0; end //-------------------------------------- PREPARE_READ: begin cs_n <= 1'b0; oe_n <= 1'b1; we <= 1'b0; end //-------------------------------------- READ: begin cs_n <= 1'b0; oe_n <= 1'b0; we <= 1'b0; end //-------------------------------------- END_READ: begin cs_n <= 1'b0; oe_n <= 1'b1; we <= 1'b0; end //-------------------------------------- PREPARE_WRITE: begin cs_n <= 1'b0; oe_n <= 1'b1; we <= 1'b0; end //-------------------------------------- WRITE: begin cs_n <= 1'b0; oe_n <= 1'b1; we <= 1'b1; end //-------------------------------------- END_WRITE: begin cs_n <= 1'b0; oe_n <= 1'b1; we <= 1'b0; end endcase end end //-------------------------------------------
//обработка задания адреса и данных
//эти сигналы задаются только на границе переходов always @(posedge clk) begin if(reset) begin m_address <= 8'd0; m_data_to <= 8'd0; s_data_from <= 8'd0; done <= 1'b0; end else begin if ((State == IDLE) && (NextState == PREPARE_WRITE)) begin m_address <= s_waddress; m_data_to <= s_data_to; end else if ((State == IDLE) && (NextState == PREPARE_READ)) m_address <= s_raddress; //---------------------------------------------------------------- if ((State == READ) && (NextState == END_READ)) s_data_from <= m_data_from; //---------------------------------------------------------------- if ((State == END_READ) && (NextState == IDLE)) done <= 1'b1; else if ((State == END_WRITE) && (NextState == IDLE)) done <= 1'b1; else done <= 1'b0; end end //-------------------------------------------
//обработка счетчика паузы always @(posedge clk) begin if(reset) begin PCounter <= 0; end else begin //счетчик все время идет до 0, кроме //моментов смены состояния, когда задается величина //паузы для следующего состояния if ((State == IDLE) && (NextState == PREPARE_WRITE)) PCounter <= WRITE_SETUP; else if((State == PREPARE_WRITE) && (NextState == WRITE)) PCounter <= WRITE_PULSE; else if((State == WRITE) && (NextState == END_WRITE)) PCounter <= WRITE_HOLD; //---------------------------------------------------------- else if((State == IDLE) && (NextState == PREPARE_READ)) PCounter <= READ_SETUP; else if((State == PREPARE_READ) && (NextState == READ)) PCounter <= READ_PULSE; else if((State == READ) && (NextState == END_READ)) PCounter <= READ_HOLD; //---------------------------------------------------------- else if(PCounter != 0) PCounter <= PCounter - 1'b1; end end endmodule

Вот результат моделирования работы описаний

Как мы видим, ведут они себя одинаково и соответствую желаемым временным диаграммам памяти. Описание в 3 always блока получилось в большее число блоков, иначе блок задания выходов сильно бы усложнился. Заряжать счетчик, сохранять данные для записи в память и обратно нам надо в одном конкретном такте. Для этого нужно либо добавлять однотактные состояния в автомат, либо создавать конструкции выделения этих тактов. Я предпочел второй вариант и вынес конструкции в отдельные блоки, чтобы не усложнять блок задания выходов.

Так или иначе, в этом примере мы видим насколько больше получается описание в 3 always блока (брутто 287 строк против 181). В нем больше мест, где можно совершить ошибку. Отлаживается оно тоже сложнее. Если вы просматривали эти два описания, то могли заметить, что в первом описании вся картина работы видна сразу, а во втором мы всегда видим какую то часть. Полная картина разнесена по всему файлу.

Разбирать так описанный чужой автомат отдельное «удовольствие». Особенно, если условия переходов зависит от выходов автомата (в нашем случает состояние задает счетчик, а счетчик задает условие перехода). Сначала смотришь значение выходов в текущем состоянии, потом летишь в блок переходов и смотришь, куда мы переходим в данном состоянии и при таком значении выходов. Потом опять мотаешь в блок задания выходов, смотришь их изменения от нового состояния.

Автомат описанный в 2 always блока анализируется чуть проще, у него выходы и переходы часто лежат рядом в одном блоке, но ровно до момента, пока мы не захотим защелкнуть состояние выхода в регистр. Тут начинают появляться регистры с парными комбинаторными значениями их следующего состояния, потом начинают добавляться условия защелкивания и мы возвращаемся к исходному упражнению.

Надеюсь теперь описание с 1 always блоком, потеряет титул «самое плохое описание, старайтесь его избегать». Конечно не стоит всегда использовать только этот вид описания. При ветвистых сетях переходов 1 блоковое описание правда неудобно. Быстро разрастается по объему кода и перестает управляться. Однако выкидывать его из арсенала разработки однозначно не стоит.

Показать больше

Похожие публикации

Кнопка «Наверх»