Visión general
Esta página, que es la última de una serie de páginas dedicadas a las FIFO, muestra cómo modificar una FIFO existente para convertirla en otra. Primero, cómo convertir una «FIFO estándar» en una FIFO FWFT y, después, en el sentido contrario. A continuación se presentan algunos métodos más avanzados para mejorar la temporización (timing) de la FIFO, es decir, conseguir que funcione a frecuencias más altas.
Desde un punto de vista práctico, no tiene mucho sentido leer esta página a menos que tengas problemas para cumplir las restricciones de temporización (timing constraints) y que ese problema esté relacionado con una FIFO. El contenido de esta página es difícil, y no es necesario para el uso habitual de las FIFO. Puede que, aun así, merezca la pena como ejercicio, para entrenar los músculos que utilizarás al diseñar lógica, en particular lógica que procesa datos.
No está directamente relacionado, pero hay otra página que muestra cómo crear una FIFO de mucha profundidad con la ayuda de memoria externa (normalmente memoria DDR, aunque vale cualquier cosa que esté envuelta con una interfaz AXI). Lo bueno de este truco es que, aunque esa FIFO enorme puede ser tan profunda como la memoria externa que utiliza, todo esto es transparente para la lógica de la aplicación: tiene la misma interfaz que una FIFO básica.
Debo mencionar que escribí el código Verilog de esta página hace muchos años, así que el estilo de código difiere ligeramente del actual.
De FIFO estándar a FIFO FWFT
Para recapitular rápidamente lo que son las FIFO FWFT, de la página anterior: con una «FIFO estándar», un puerto @empty (vacía) en bajo significa que en la salida de la FIFO se presentará un dato válido después de que @rd_en esté en alto en un flanco ascendente del reloj. Una FIFO FWFT presenta el dato en la salida en cuanto está disponible, así que una señal @empty (vacía) en bajo significa que el dato en la salida es válido.
El significado de @rd_en también es distinto: en una «FIFO estándar» significa «tráeme un dato». En una FIFO FWFT viene a ser «acabo de usar el dato, tráeme el siguiente si lo tienes».
Pues bien, este es el módulo que convierte una «FIFO estándar» en una FIFO FWFT. Como era de esperar, no hace más que manipular @rd_en y @empty (vacía). El resto de las señales se pasan directamente.
module basic_fwft_fifo(rst,
rd_clk, rd_en, dout, empty,
wr_clk, wr_en, din, full);
parameter width = 8;
input rst;
input rd_clk;
input rd_en;
input wr_clk;
input wr_en;
input [(width-1):0] din;
output empty;
output full;
output [(width-1):0] dout;
reg dout_valid;
wire fifo_rd_en, fifo_empty;
// orig_fifo is just a normal (non-FWFT) synchronous or asynchronous FIFO
fifo orig_fifo
(
.rst(rst),
.rd_clk(rd_clk),
.rd_en(fifo_rd_en),
.dout(dout),
.empty(fifo_empty),
.wr_clk(wr_clk),
.wr_en(wr_en),
.din(din),
.full(full)
);
assign fifo_rd_en = !fifo_empty && (!dout_valid || rd_en);
assign empty = !dout_valid;
always @(posedge rd_clk or posedge rst)
if (rst)
dout_valid <= 0;
else
begin
if (fifo_rd_en)
dout_valid <= 1;
else if (rd_en)
dout_valid <= 0;
end
endmodule
Normalmente explicaría aquí el código, pero eso no haría más que repetir las explicaciones que ya se dieron para la FIFO FWFT en la página anterior.
De FIFO FWFT a FIFO estándar
Esto es realmente sencillo. Como un @empty (vacía) en bajo de una FIFO FWFT significa que hay un dato presente en el puerto de salida, basta con crear un registro que muestree ese dato cuando @rd_en esté en alto.
Así que es simplemente esto:
module standard_fifo(rst,
rd_clk, rd_en, dout, empty,
wr_clk, wr_en, din, full);
parameter width = 8;
input rst;
input rd_clk;
input rd_en;
input wr_clk;
input wr_en;
input [(width-1):0] din;
output empty;
output full;
output [(width-1):0] dout;
reg [(width-1):0] dout;
wire [(width-1):0] dout_w;
always @(posedge rd_clk)
if (rd_en && !empty)
dout <= dout_w;
fwft_fifo wrapper
(
.wr_clk(wr_clk),
.rd_clk(rd_clk),
.rst(rst),
.din(din),
.wr_en(wr_en),
.rd_en(rd_en && !empty),
.dout(dout_w),
.full(full),
.empty(empty)
);
endmodule
Observa que solo se manipula @dout. La señal @empty (vacía) se deja pasar tal cual: si está en alto, @dout_w no es válido, así que @dout no puede tomar un valor de ahí.
Trucos para mejorar la temporización
Bienvenido al gran final de estas cuatro páginas sobre FIFO, que sin duda es la parte más difícil de leer.
De vez en cuando, al intentar averiguar por qué un diseño FPGA no cumple las restricciones de temporización, es decir, no alcanza la frecuencia de reloj deseada, resulta que la ruta crítica (critical path) empieza y/o termina en una FIFO. Primero repasaremos los casos fáciles de resolver y terminaremos con el hueso duro.
Cuando @empty (vacía) y/o @full (llena) están en la ruta crítica
Las señales @empty (vacía) y @full (llena) pueden aparecer en la ruta crítica, sobre todo si @wr_en y @rd_en son funciones combinacionales de esas señales. Esto se debe principalmente a que estas señales no sirven solo para solicitar una operación de escritura o lectura a la FIFO, sino que hacen también las veces de señales de habilitación para la lógica de la aplicación que consume o produce datos: si el flujo de datos no circula, la lógica también se congela.
Por tanto, hay a menudo muchas ecuaciones lógicas que dependen de @wr_en y @rd_en, y con frecuencia son funciones lógicas bastante complicadas. El resultado es un alto fan-out. Todo esto se traduce en un retardo de propagación (propagation delay) problemático.
@empty (vacía) y @full (llena) son salidas de biestables (flip-flops) en cualquier FIFO bien escrita, así que en ese sentido no hay mucho que mejorar. Pero como el software de la FPGA suele entregar la FIFO como una netlist sintetizada, es imposible, o al menos difícil, duplicar esos registros para reducir su fan-out. Además, puede haber una gran distancia física en el tejido lógico de la FPGA entre esos registros y la lógica de la aplicación que utiliza sus valores de salida. En FPGAs grandes, esto puede ser la contribución decisiva al retardo de las rutas.
La solución a este problema ya se ha dado en esa página, al hablar de @almost_empty (casi vacía) y @almost_full (casi llena). Si se utilizan estos puertos, las salidas @wr_en y @rd_en pueden ser registros. Esto resuelve el problema de la función combinacional y permite además controlar el fan-out de estas señales. Por si fuera poco, esto también ayuda a las herramientas a colocar esos registros más cerca de la lógica que consume sus valores, lo que contribuye a reducir el retardo de propagación.
Cuando @wr_en y/o @din están en la ruta crítica
Esta situación es, sin duda, la más fácil de resolver. Basta con añadir una capa de registros. Algo así como
always @(posedge wr_clk)
begin
wr_en_reg <= wr_en;
din_reg <= din;
end
y conectar entonces @wr_en_reg y @din_reg a la FIFO. Para evitar que la FIFO se desborde (overflow), conviene utilizar @almost_full (casi llena) en lugar de @full (llena). O, dicho de un modo más general, el umbral de llenado de la FIFO debería reducirse en uno.
Cuando @rd_en y/o @dout están en la ruta crítica
Ahora la cosa se pone seria. No solo es un problema relativamente difícil de resolver, sino que es también el que tiene más probabilidades de aparecer. Hay varias razones para ello:
- La señal @rd_en se utiliza en lógica combinacional (combinatorial logic) dentro de la FIFO, entre otras cosas para calcular la siguiente dirección de lectura. Así que la propia FIFO contribuye con una cierta cantidad de retardo.
- La lógica de la aplicación que genera @rd_en suele ser una función combinacional que puede ser complicada. Esa función lógica puede estar formada por registros de estado y varios indicadores (flags) que provienen de distintas partes del tejido lógico.
En cuanto a @dout:
- La salida de datos de la FIFO suele estar conectada directamente a una RAM de bloques (block RAM). En comparación con los flip-flops de la FPGA, estas RAM tienen una temporización de reloj a salida significativamente peor. Si la FIFO se implementa con varias RAM, sus salidas de datos se insertan en un multiplexor, así que @dout es el resultado de esa lógica combinacional. Eso añade aún más retardo.
- La lógica de la aplicación puede utilizar el valor de @dout en funciones combinacionales.
- La distancia física en la FPGA entre las RAM de la FIFO y la lógica de la aplicación puede añadir retardo en FPGAs grandes.
El objetivo es, pues, eliminar la ruta combinacional entre @rd_en y la lógica de la FIFO, y hacer lo mismo con @dout.
Desconectar solo la ruta combinacional de @dout
No pretendo presentar esto como una solución, pero la discusión puede ayudar a entenderlo como preparación para comprender el siguiente paso. Si esto solo te confunde, sáltate esta sección.
Supongamos que solo quisiéramos desconectar la ruta combinacional de @dout. Observa que el módulo contenedor (wrapper) que convierte una FIFO FWFT en una «FIFO estándar», mostrado arriba, hace exactamente eso: añade un registro y, al hacerlo, pone fin a la ruta combinacional de @dout. Pero eso requiere una FIFO FWFT como punto de partida.
Pero antes había un módulo contenedor que convertía una «FIFO estándar» en una FIFO FWFT. Entonces, ¿quizá convertir la FIFO de un lado a otro? ¿O escribir un único módulo que haga lo equivalente? En cualquier caso, una solución de este tipo empeora la situación con @rd_en.
Con todo, merece la pena examinar esta solución más de cerca: la conversión a una FIFO FWFT consistía simplemente en llevar la cuenta de cuándo era válido el @dout de la FIFO envuelta y mantener @fifo_rd_en en alto cuando @dout no era válido (y/o cuando el @rd_en externo estaba en alto).
La conversión de vuelta a una «FIFO estándar» se hacía copiando el valor del @dout de la FIFO envuelta a un registro cuando @rd_en estaba en alto.
En resumen, el primer mecanismo mantenía válido el @dout de la FIFO envuelta cuando era posible, y el segundo copiaba @dout a otro registro cuando el @rd_en externo lo solicitaba.
Pero esto no resuelve el problema de la ruta combinacional de @rd_en: para permitir la lectura continua, hay que leer una palabra de la FIFO original en cada ciclo en que el @rd_en externo esté en alto. De lo contrario, el @dout de la FWFT se vuelve no válido porque se ha consumido pero no se ha actualizado. Por tanto, el @rd_en de esa FIFO interna debe ser una función combinacional del @rd_en externo. Si queremos cambiar esto, hay que añadir otro registro al camino de @dout, como se muestra a continuación.
Desconectar ambas rutas combinacionales con reg_fifo
Sin más preámbulos, este es el módulo reg_fifo, que desconecta las rutas combinacionales de @rd_en y @dout:
module reg_fifo(rst,
rd_clk, rd_en, dout, empty,
wr_clk, wr_en, din, full);
parameter width = 8;
input rst;
input rd_clk;
input rd_en;
input wr_clk;
input wr_en;
input [(width-1):0] din;
output empty;
output full;
output [(width-1):0] dout;
reg fifo_valid, middle_valid;
reg [(width-1):0] dout, middle_dout;
wire [(width-1):0] fifo_dout;
wire fifo_empty, fifo_rd_en;
wire will_update_middle, will_update_dout;
// orig_fifo is "standard" (non-FWFT) FIFO
fifo orig_fifo
(
.rst(rst),
.rd_clk(rd_clk),
.rd_en(fifo_rd_en),
.dout(fifo_dout),
.empty(fifo_empty),
.wr_clk(wr_clk),
.wr_en(wr_en),
.din(din),
.full(full)
);
assign will_update_middle = fifo_valid && (middle_valid == will_update_dout);
assign will_update_dout = rd_en && !empty;
assign fifo_rd_en = !fifo_empty && !(middle_valid && fifo_valid);
assign empty = !(fifo_valid || middle_valid);
always @(posedge rd_clk)
if (rst)
begin
fifo_valid <= 0;
middle_valid <= 0;
dout <= 0;
middle_dout <= 0;
end
else
begin
if (will_update_middle)
middle_dout <= fifo_dout;
if (will_update_dout)
dout <= middle_valid ? middle_dout : fifo_dout;
if (fifo_rd_en)
fifo_valid <= 1;
else if (will_update_middle || will_update_dout)
fifo_valid <= 0;
if (will_update_middle)
middle_valid <= 1;
else if (will_update_dout)
middle_valid <= 0;
end
endmodule
Lo primero que hay que observar es que @dout es un registro definido en este módulo, y que @rd_en provoca una actualización de ese registro. Es importante no confundir estas dos señales con las señales similares que van conectadas a la FIFO interna, que son @fifo_dout y @fifo_rd_en.
Ahora veamos cómo funciona este módulo.
Cómo funciona el pipeline
Esta estructura es, en esencia, un amortiguador deslizante (skid buffer): un pipeline de dos etapas con indicadores de validez que desacopla el @rd_en externo de la habilitación de lectura de la FIFO interna, permitiendo al mismo tiempo que el flujo de datos sea continuo.
Igual que el conversor a FIFO FWFT, hay una instanciación (instantiation) de una FIFO normal, orig_fifo. La lógica del módulo reg_fifo intenta mantener válido el valor de @fifo_dout leyendo una palabra de orig_fifo cuando @fifo_dout no contiene un valor válido. Pero, además, hay un segundo registro, llamado @middle_dout. La lógica intenta mantener también válido este registro, tomando el valor de @fifo_dout cuando es posible.
Así pues, se puede considerar @fifo_dout, @middle_dout y @dout como un pipeline que hace avanzar los datos de orig_fifo.
Hay dos registros que se encargan de saber cuándo las etapas de este pipeline son válidas: @fifo_valid está en alto cuando @fifo_dout es válido, y @middle_valid está en alto cuando @middle_dout es válido.
El propósito de este pipeline es poder saltarse su etapa intermedia: cuando @rd_en está en alto (y @empty (vacía) está en bajo), @dout toma su nuevo valor de @middle_dout o de @fifo_dout, pero siempre prefiere @middle_dout. En otras palabras, si @middle_dout es válido, @dout usa @middle_dout; si no, usa @fifo_dout. Más adelante se explica por qué esta es la clave para desconectar la ruta combinacional de @rd_en.
Así que, primero, veamos los detalles de la implementación. Hay dos caminos separados desde la salida de datos de la FIFO hasta el registro de salida de reg_fifo. Están representados por separado a la izquierda y a la derecha en este dibujo:
Si ninguna de las dos etapas del pipeline (@fifo_dout y @middle_dout) es válida, @empty (vacía) se pone en alto para indicar que no hay de dónde tomar datos:
assign empty = !(fifo_valid || middle_valid);
El intento de mantener válidas estas etapas del pipeline se refleja en
assign fifo_rd_en = !fifo_empty && !(middle_valid && fifo_valid);
que dice que si cualquiera de las dos etapas no es válida, se lee de orig_fifo, si es posible. Si @fifo_dout ya es válido, su valor se copia en @middle_dout al mismo tiempo que se actualiza @fifo_dout (más sobre esto abajo).
Ahora veamos las definiciones del par @will_update_*:
assign will_update_middle = fifo_valid && (middle_valid == will_update_dout);
assign will_update_dout = rd_en && !empty;
Primero fíjate en que @will_update_dout es igual a @rd_en con una protección adicional para no leer de reg_fifo cuando @empty (vacía) está en alto.
A continuación tenemos @will_update_middle, que controla la actualización de @middle_dout, así:
always @(posedge rd_clk)
if (will_update_middle)
middle_dout <= fifo_dout;
Observando la definición de @will_update_middle más arriba, hay dos condiciones para actualizar @middle_dout: una es que el valor de @fifo_dout sea válido, lo cual es bastante evidente; la segunda es la expresión (middle_valid == will_update_dout). Vamos a desglosar esta expresión en las cuatro opciones posibles, porque así se explica cómo funciona toda la maquinaria. Ten en cuenta que todo esto solo tiene importancia cuando @fifo_dout es válido:
- @middle_valid == 0 y @will_update_dout == 0. @middle_dout no es válido, y el valor de @fifo_dout no se va a copiar en @dout. Así que actualiza @middle_dout desde @fifo_dout.
- @middle_valid == 0 y @will_update_dout == 1. @middle_dout no es válido, pero @dout va a actualizarse, así que evidentemente se actualizará desde @fifo_dout. Como el valor de @fifo_dout queda consumido, no puede copiarse a @middle_dout, así que no se hace nada.
- @middle_valid == 1 y @will_update_dout == 0. @middle_dout es válido y no se copia nada en @dout. Ambas etapas del pipeline son válidas y seguirán siéndolo de todos modos. Así que no se hace nada.
- @middle_valid == 1 y @will_update_dout == 1. @middle_dout es válido y va a copiarse en @dout. Así que actualiza @middle_dout desde @fifo_dout para que siga siendo válido.
Observa que @fifo_rd_en está en bajo cuando @middle_valid y @fifo_valid están en alto a la vez. Como resultado, no se lee ningún dato de orig_fifo cuando se dan los escenarios de los dos últimos casos.
En particular, cuando las dos etapas del pipeline son válidas y @rd_en está en alto, el valor de @fifo_dout se copia en @middle_dout. Y como @fifo_rd_en está en bajo, @fifo_valid pasará a bajo en el siguiente ciclo de reloj. Lo cual no es problema, porque @middle_valid seguirá en alto y podrá suministrar datos en ese siguiente ciclo si hace falta. En el ciclo posterior, @fifo_valid volverá a estar en alto (si queda algún dato en orig_fifo).
Entonces, ¿por qué no se define @fifo_rd_en de modo que @fifo_dout siga siendo válido en esta situación concreta? Porque entonces @fifo_rd_en tendría que ser una función combinacional de @rd_en, que es exactamente lo que este pipeline de dos etapas pretende evitar.
Con esto ya podemos ver cómo se define @dout. Salvo por el reset, la definición es:
always @(posedge rd_clk)
if (will_update_dout)
dout <= middle_valid ? middle_dout : fifo_dout;
Sustituyendo @will_update_dout por su definición, queda:
always @(posedge rd_clk)
if (rd_en && !empty)
dout <= middle_valid ? middle_dout : fifo_dout;
Esto es parecido a la conversión de una FIFO FWFT a una «FIFO estándar», solo que hay dos posibles orígenes: si @middle_dout contiene un valor válido, se toma ese. Si no, se toma @fifo_dout. Si ninguno es válido, @empty (vacía) está en alto, así que no ocurre nada de todos modos.
¿Por qué ayuda esto? En cuanto a la temporización de salida, @dout es claramente un registro. En cuanto a @rd_en, observa que @fifo_rd_en depende solo de @middle_valid y @fifo_valid, que son ambos registros, además de @fifo_empty, que es la salida de la propia orig_fifo (esa ruta combinacional es inevitable). Por consiguiente, @fifo_rd_en no depende del @rd_en externo, así que no hay ninguna ruta combinacional desde @rd_en hasta orig_fifo.
Seguimiento de la validez de los registros de las etapas del pipeline
Solo para completar el panorama: los dos indicadores *_valid nos dicen si el registro asociado contiene datos válidos. Con respecto a @fifo_valid:
if (fifo_rd_en)
fifo_valid <= 1;
else if (will_update_middle || will_update_dout)
fifo_valid <= 0;
Esto es como la definición de @dout_valid en la conversión de «FIFO estándar» a FIFO FWFT de arriba: cuando @fifo_rd_en está en alto en un flanco ascendente, @fifo_valid pasa a alto como consecuencia. Lo cual tiene sentido, porque si leemos datos de orig_fifo, la salida de esa FIFO pasa a considerarse válida. Pero si @fifo_rd_en estaba en bajo y se han copiado datos a @middle_dout o a @dout, ya no consideramos válido @fifo_dout: la salida de la FIFO acaba de usarse y la FIFO no la ha sustituido por datos nuevos.
@middle_valid sigue la misma lógica:
if (will_update_middle)
middle_valid <= 1;
else if (will_update_dout)
middle_valid <= 0;
Cuando @will_update_middle está en alto, se copian datos a @middle_dout, así que @middle_valid también pasa a alto. En caso contrario, y si el dato de @middle_dout se copia a @dout, @middle_valid pasa a bajo. @will_update_dout es condición suficiente para esto, porque, recuerda lo dicho antes, @dout prefiere copiar de @middle_dout cuando es posible.
¿Funciona de verdad?
Este módulo es tan complicado que casi requiere una demostración formal de que funciona. Así que una manera de responder a esta pregunta es preguntarse cuántas de las dos etapas del pipeline, @fifo_dout y @middle_dout, son válidas. Este valor no está definido en el módulo reg_fifo, pero podría haberse definido como
wire [1:0] valid_count;
assign valid_count = fifo_valid + middle_valid;
Este imaginario @valid_count puede tomar evidentemente los valores 0, 1 o 2. Cuenta hacia arriba o hacia abajo de la siguiente manera:
- @valid_count aumenta en uno en cada ciclo de reloj en que @fifo_rd_en está en alto y (rd_en && !empty) es falso.
- @valid_count disminuye en uno en cada ciclo de reloj en que @fifo_rd_en está en bajo y (rd_en && !empty) es verdadero.
- En cualquier otro caso, @valid_count no cambia.
Echa un vistazo a las ecuaciones lógicas y convéncete de que estas tres afirmaciones son correctas.
Veamos entonces qué ocurre cuando hay datos en orig_fifo y la lógica de la aplicación quiere leer de forma continua:
La lógica de reg_fifo intenta empujar @valid_count hacia 2 leyendo de orig_fifo. Por otro lado, @empty (vacía) está en bajo cuando @valid_count no es cero; por tanto, @rd_en puede ponerse en alto en cuanto @valid_count sea 1. Así, cuando @valid_count es 1, @fifo_rd_en estará en alto porque @valid_count no es 2.
Pero @valid_count no llegará a 2 porque @rd_en se lo impide manteniéndose en alto. Así que los datos fluyen con @fifo_rd_en y @rd_en ambos en alto, y @valid_count permanece en 1. Salvo al principio, los datos se copian de @fifo_dout a @dout.
Ese equilibrio se rompe cuando orig_fifo se queda vacía: en ese caso @valid_count pasa a cero porque @fifo_rd_en ya no puede estar en alto. Otra situación que lo rompe es cuando la FIFO no está vacía y @rd_en se pone en bajo porque la lógica de la aplicación no quiere leer más: entonces @valid_count sube a 2 y se queda ahí.
Pero más adelante, cuando @rd_en vuelve a ponerse en alto, @valid_count baja a 1, y solo entonces @fifo_rd_en pasa a alto (a menos que orig_fifo esté vacía).
Una vez más, @valid_count es solo una señal teórica que no está implementada en el módulo. Esperemos que esta explicación haya servido para entender por qué las dos etapas extra del pipeline garantizan un flujo de datos continuo.
Notas de uso
Este módulo puede utilizarse como sustituto directo de la «FIFO estándar» a la que envuelve. Desde un punto de vista funcional, nada cambia. orig_fifo verá, no obstante, un pequeño cambio en el comportamiento de @rd_en, @dout y @empty (vacía), pero eso no importa siempre que orig_fifo se comporte correctamente como FIFO (una suposición razonable). Los puertos relacionados con la escritura de datos se dejan pasar sin tocarlos, así que no hay ningún cambio en ellos.
Como el módulo añade un par de etapas de pipeline, los contadores de llenado (fill counters) de orig_fifo pueden presentar valores inferiores al número total de palabras almacenadas en reg_fifo (es decir, la suma de las palabras almacenadas en orig_fifo y en las etapas del pipeline). Por tanto, si se habilitan @almost_empty (casi vacía) o puertos similares en orig_fifo, pueden ofrecer una imagen pesimista.
Un pequeño inconveniente de reg_fifo es que su salida @empty (vacía) no es un registro, sino una función combinacional de dos registros. Esto no es óptimo para la temporización, aunque en la mayoría de los casos su impacto es mínimo. Se puede corregir definiendo registros combinacionales como @next_fifo_valid y @next_middle_valid, con el mismo espíritu que @next_words_in_ram, como se muestra en esa página. No se ha implementado aquí, principalmente porque reg_fifo ya es bastante complicado.
Una FIFO FWFT con mejor temporización
Si se necesita una FIFO FWFT con mejor temporización, es fácil: usa el ejemplo de basic_fwft_fifo mostrado arriba, pero en lugar de instanciar una FIFO normal, usa reg_fifo. Esta solución requiere un registro más, pero es un precio pequeño.
Con esto concluye esta serie dedicada a las FIFO.