Cuándo utilizar máquinas de estado - FPGA

Question

He leído mucho sobre FSMs (Finite State Machines) cuando hacía tutoriales de VHDL. Son fáciles y las he usado mucho pero todavía no entiendo algo y no puedo encontrar la respuesta en línea:

¿Cuándo debo utilizar FSMs (Moore o Mealy) en mi diseño VHDL?

Por ejemplo, si implemento un algoritmo (previamente en lenguaje C) en VHDL, ¿debo utilizar un FSM?

Answer 1

Si tiene que dividir una operación en varios ciclos de reloj, tiene dos opciones: la canalización y la secuenciación.

Consideremos una operación mítica consistente en cuatro multiplicaciones, por ejemplo, en la que cada multiplicación (excepto la primera) requiere la salida de la multiplicación anterior como una de sus entradas. Sin embargo, las ideas básicas son mucho más generales.

En el pipelining, se dispone de hardware suficiente para realizar cada operación simultáneamente, interconectado por registros pipeline. Esto implica cuatro multiplicadores, separados por registros pipeline. Se tardan 4 ciclos de reloj en obtener el primer resultado (es decir, el pipeline tiene 4 etapas de profundidad y la latencia es de 4 ciclos), pero se obtiene un nuevo resultado cada ciclo de reloj (es decir, la tasa de rendimiento es de 1 ciclo). Un poco más de información sobre el diseño de las tuberías...

Inconveniente: se trata de una gran pieza de hardware. 4 multiplicadores son relativamente caros (por eso algunas familias de FPGA ofrecen muchos multiplicadores pequeños como bloques altamente optimizados).

La alternativa es secuenciar cada operación en el mismo multiplicador, con lo que se obtiene un diseño mucho más pequeño, pero se obtiene un resultado cada 4 ciclos.

En este caso puedes utilizar un único multiplicador, almacenando su resultado en un único registro, para un diseño mucho más pequeño.

Cada 4 ciclos (o siempre que algo indique que hay una nueva entrada preparada) conectas la nueva entrada a un puerto de entrada del multiplicador; en otros ciclos alimentas ese puerto desde el registro de salida (para utilizar el resultado de la multiplicación anterior). Y en cada ciclo alimentas los datos apropiados (coeficientes de filtro, valores de matriz, lo que sea) en el otro puerto del multiplicador. Cuatro ciclos después, presentas el resultado final como salida, y señalas a tu consumidor que un nuevo resultado está listo.

La forma obvia de secuenciar estas operaciones es una máquina de estados (FSM).

De hecho, los cálculos pueden integrarse en las acciones asociadas a cada estado, por ejemplo:

if rising_edge(clk) then
   Done <= '0';   -- and any other default actions
   case state is
   when Idle =>
      if Start = '1' then
         Temp  := Input * C1;
         State := S1;
      end if;
   when s1 =>
      Temp  := Temp * C2;
      State := S2;
   when s2 =>
      Temp  := Temp * C3;
      State := S3;
   when s3 =>
      Temp  := Temp * C4;
      State := S4;
   when s4 =>
      Output <= Temp;
      Done   <= '1';
      State  := Idle;
      -- optional alternative for bombproof handshaking
      -- if Start = '0' then
      --    Done <= '1';
      --    State <= Idle;
      -- end if;
   end case;
end if;

Si estás interactuando con otras unidades - interfaces SPI, UARTs etc, el FSM es de nuevo normalmente el mejor método.

Answer 2

En el diseño de FPGA, hay dos clases principales de operaciones:

• La combinatoria, es decir, la aplicación de la lógica expresiones .
• Operaciones de reloj, es decir, la conexión a latches (por ejemplo, flip flops de tipo D), o en términos de programación; la implementación de secuencias de operaciones .

Como ya sabrás, el tamaño de los circuitos combinatorios tiene un límite. Cada puerta lógica tiene un retardo, si la señal de entrada sube de "0" a "1", la salida tardará en estabilizarse en la respuesta correcta. Si lo conectas en cascada demasiado lejos, verás que la salida puede estar desincronizada, produciendo errores.

La solución es, por supuesto, recurrir a los pestillos. En un momento determinado, se muestrea la salida, manteniéndola válida hasta la próxima vez. Aquí es donde las operaciones con reloj entran en escena.

Pipelining se desprende naturalmente de ello. Si no puede hacerlo todo en un solo ciclo, divídalo en más partes, en las que cada parte alimente el resultado parcial a la siguiente. La última parte presenta el resultado final, normalmente N ciclos más tarde.

Pero a veces no es tan sencillo. Si el problema requiere que ocurra algo diferente en función de un estado (normalmente tiempo o algunas entradas externas), entonces Máquinas de estados finitos (FSM) es la solución más lógica.

Los FSM reducen la complejidad lógica. "Cuando pase esto y aquello, deberíamos hacer esto otro". Los ejemplos están a la orden del día, pero considere que la ejecución de una CPU no es en realidad más que una gigantesca máquina de estados.

Como regla general, si puede dividir su problema en un número finito de pasos en los que el transición de un paso a otro es potencialmente variable entonces debería considerar el uso de un FSM. Dado que este es, con mucho, el escenario más común, usted encontrará que va a utilizar FSMs bastante.

Answer 3

Yo daría una respuesta opuesta. ¿Cuándo no utilizar un FSM?

Si su secuencia de operaciones necesita más de unos 30 estados, probablemente esté :

• Intentar mezclar en un mismo estado el comportamiento de varias máquinas. Por ejemplo, en un protocolo serie, generar los bits a partir de bytes puede hacerlo un FSM, ensamblar los bytes para generar tramas otro.
• Al escribir software, la máquina de estados debe sustituirse normalmente por microcódigo.

Answer 4

Los sistemas digitales no triviales, que casi siempre son síncronos y, por tanto, utilizan un reloj, pueden concebirse como una línea de registros que almacenan datos con una lógica combinatoria entre ellos que procesa los datos. Los datos se representan mediante señales binarias. Esta línea, que puede ser una línea única o ramificarse en otras líneas, se describe como una ruta de datos. Los datos fluyen por este camino y se procesan mediante operaciones booleanas implementadas a través de la lógica combinatoria, los resultados intermedios se almacenan en el registro y luego son procesados por el siguiente grupo de lógica combinatoria. Este es también el aspecto del "pipeline".

Necesitamos una máquina de estados para controlar básicamente este flujo de datos, es decir, tomamos decisiones basadas en resultados intermedios sobre cómo hacer progresar los datos, si continúan de forma lineal, si se ramifican, si se borran o sobrescriben, si obtenemos un nuevo valor de entrada, si guardamos el valor de salida y enviamos una señal a la otra parte del hardware indicando que el procesamiento de datos en esta parte del hardware se ha completado o para solicitar nuevos datos de otra parte del diseño; Estas cosas son sencillas de escribir en un lenguaje de alto nivel. En VHDL, donde describimos el hardware, creamos una máquina de estados para hacer esto.

Lo que he dado es una descripción muy general que puede no tener todo el sentido. Tendrá sentido cuando diseñes realmente un sistema en el que necesites utilizarlo.