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

Когда нужно преодолеть врожденную параллельность 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 блоковое описание правда неудобно. Быстро разрастается по объему кода и перестает управляться. Однако выкидывать его из арсенала разработки однозначно не стоит.