Frecuencia Máxima de un Sistema Digital Sincrónico (Básico)

Introducción 

Comúnmente se expresa que un sistema puede correr satisfactoriamente a 100MHz, o a 133MHz o cualquier otra frecuencia. Qué significa esto? Porqué a esa frecuencia como máxima frecuencia? Quién fija ese límite en un circuito digital? y Cómo se obtiene 6 calcula, ese número? ? Muuuchas preguntas para contestarlas en un simple blog, pero... haré lo que pueda para contestarlas . . .  :) .

Periodo Mínimo

En primer lugar recordemos que el periodo de reloj de un sistema es el que 'marca el paso' en el sistema. Si el periodo es largo, el sistema da pasos (entrega resultados/valores) a pasos grandes (sistema lento), si el periodo del reloj es pequeño, el sistema entregará resultados a pasos mas cortos, es decir mas rápidamente. 

Recordemos también que la frecuencia de funcionamiento de un sistema es la inversa del periodo de ese mismo sistema: F = 1/T (periodo). Por ello para encontrar la máxima frecuencia debemos encontrar el periodo mínimo . . . 

Cómo calcular u obtener el periodo mínimo?
Bien, en un sistema digital el periodo mínimo está compuesto por los retardos MÁXIMOS de los componentes sincrónicos, de los componentes combinacionales , y de las interconecciones entre ellos.
Veamos que significa esto: primero, en un sistema hay muchos caminos sincrónicos (camino de conexión entre flip-flops), pero el que es de interés para el calculo del periodo mínimo es el camino (path) MAS LENTO de todos, es decir el que tiene los retardos MÁXIMOS. El camino mas lento también es llamado camino CRITICO (critical path).

Componentes del periodo mínimo: 

1. Retardo Sincrónico: cuanto se demora en estar estable el dato a la salida de un flip-flip luego del flanco activo del reloj.
2. Retardo combinacional: está compuesto por los componentes no sincrónicos, pueden ser compuertas lógicas, mux, decodificadores, LUTs (en el caso de un FPGA), etc, del camino crítico. Puede haber mas de uno de estos componentes; el retardo de cada uno se suma para lograr el retardo total. La cantidad de componentes combinacionales en el camino critico es normalmente informado en el reporte de frecuencia máxima como 'niveles lógicos' (logic levels). Si se informa que el 'logic level' es 5, significa que en el camino critico hay 5 componentes lógicos combinacionales. 
3. Retardo de ruteo o de conexiones en el camino critico:
1. Entre la salida del componente sincrónico (flip-flop) y la entrada a los componentes combinacionales.
2. Entre los componentes combinacionales.
3. Entre la salida de los componentes combinacionales y la entrada del flip-flop.
4. Tiempo de establecimiento del flip-flop donde termina el camino critico. El dato de entrada tiene que estar un tiempo de establecimiento (dado por la hoja de datos) antes de la llegada del flanco activo del reloj, a fin de evitar problemas de metaestabilidad.
5. Margen de periodo: normalmente los valores de los retardos máximos de los puntos anteriores pueden estar afectados por lo que se llama PVT (process, volume, temperature) y los valores dados por la hoja de datos no son los que realmente tenga el circuito en funcionamiento. Por ello se agrega un cierto margen para asegurarse la estabilidad del sistema.  

Como bien se dice, una imagen vale mas que mil palabras, la siguiente figura muestra gráficamente lo anteriormente descrito en palabras:

En ésta figura los tiempos detallados son los siguientes: 

• Tco: retardo sincrónico, comúnmente llamado 'clock to output'. 
• Rr  : retardo de ruteo.
• Rc  : retardo total de la lógica combinacional, que puede tener varios niveles.
• Tsu: tiempo de establecimiento del flip-flop. 

Con todo esto podemos ahora describir la fórmula para calcular el periodo mínimo que nos va dar la frecuencia máxima de funcionamiento del sistema: 

El 10% de margen se calcula sumando los otros retardos y sacando el 10% de esa suma, el valor obtenido se usa como margen de seguridad del periodo mínimo. 

Periodo Mínimo en FPGAs

Los softwares provistos por los fabricantes de FPGAs ofrecen herramientas que realizan el análisis de todos los caminos sincrónicos del sistema. Estas herramientas realizan lo que se llama un Static Timing Analysis (STA) y reportan el camino más críticos y los siguientes casos no tan críticos. Por ejemplo Altera Quartus provee TimeQuest, Xilinx ISE ofrece Timing Analyzer, Libero de Actel ofrece SmartTime. En un anterior post detallé la información dada por Timing Analyzer. 

A modo de ejemplo de la informacion proviste por una herramienta STA, se puede ver a continuación un ejemplo de la información de un camino critico dada por la herramienta TimeQuest de Altera. 

Analicemos ésta información: La primer columna muestra los tiempos de ya sea de una celda lógica o de un ruteo. La tercer columna detalla el componente o conexión motivo del retardo: el tiempo referenciado como CELL es el retardo combinacional de la celda lógica detallada en le última columna de la derecha. El tiempo IC se refiere al retardo de ruteo o de interconexión entre las celdas lógicas combinacionales. Como puede verse algunos retardos de IC es igual a 0.000; esto se debe al ruteo dedicado que existe dentro de cada bloque básico del FPGA. El retardo total de este camino mas critico, que es el periodo mínimo al que puede correr satisfactoriamente este sistema, es de 2.331ns. Solo como referencia: La información de la quinta columna detalla el componente lógico usado, y la ultima columna el nombre dado por la herramienta de Place and Route para asociar el componente lógico con el nombre usado en el código VHDL.  

Esta información es mas fácil de interpretar viendo el esquemático de éste camino. Tanto Altera, como Actel y Xilinx ofrecen esta vista. He preparado una figura que relaciona todo lo visto hasta acá, asociando el esquemático generado por la herramienta de análisis de tiempo y la figura anteriormente presentada. 

  

Como ya dije al principio este es un cálculo básico del periodo mínimo de un sistema; en un próximo blog trataré de ir mas en detalle teniendo en cuenta por ejemplo el corrimiento del reloj (clock skew), retardos del camino de datos, jitter del reloj, etc....

De todos modos espero que este post haya sido de utilidad (avisen si es así :) .
(version .pdf click acá :) )

Qué es, Cómo, Cuando y Dónde usar Pipelining (Segmentación) ?

Pipelining es una técnica de diseño que se usa en sistemas digitales para mejorar el rendimiento (performance) de un sistema al dividir largo retardos combinacionales y de ruteo ejecutados en un solo ciclo de reloj, en varios pequeños retardos (cmb+ruteo) que son ejecutados en ciclos de reloj mucho mas cortos o en el mismo ciclo original pero ahora con mayor slack. 

Como siempre hay un 'pro' y un 'contra': se mejora la performance, pero se incrementa la latencia. 

Veremos a continuación en detalle como determinar si hace falta pipeline el diseño, como hacerlo y sus concecuencias. 

Cómo saber si hace falta Pipelining? 

La mejor manera es analizando la información dada por la herramienta de análisis de tiempo (Timing Analysis en Xilinx, TimeQuest en Altera, SmartTime en Actel). Esta herramienta analiza todos los caminos sincrónicos del sistema y verifica que el sistema pueda funcionar a la frecuencia solicitada de acuerdo a la restricción (constraint) respectiva del reloj configurada por el diseñador. Si el sistema puede funcionar a la frecuencia requerida el valor del slack es positivo; si el slack es negativo indica que el sistema no puede funcionar correctamente es la frecuencia requerida. Una técnica para solucionar el slack negativo o para mejorar un slack positivo muy pequeño es el reducir el retardo (lógico + ruteo) en el o los caminos críticos. Por ejemplo, a continuación se muestra el informe, dado por la herramienta de análisis del FPGA, del camino mas crítico de un sistema: 

Slack (setup path):     -1.576ns (requirement - (data path - clock path skew + uncertainty))

  Source:               in6_reg_3 (FF)

  Destination:          out_reg_15 (FF)

  Requirement:          7.500ns

  Data Path Delay:      9.076ns (Levels of Logic = 10)

  Clock Path Skew:      0.000ns

  Source Clock:         clk_BUFGP rising at 0.000ns

  Destination Clock:    clk_BUFGP rising at 7.500ns

  Clock Uncertainty:    0.000ns

  Maximum Data Path: in6_reg_3 to out_reg_15

    Location             Delay type         Delay(ns)  Physical Resource

                                                       Logical Resource(s)

    -------------------------------------------------  -------------------

    SLICE_X12Y35.XQ      Tcko                  0.592   in6_reg<3>

                                                       in6_reg_3

    SLICE_X12Y42.F2      net (fanout=1)        1.054   in6_reg<3>

    SLICE_X12Y42.X       Tilo                  0.759   s3<3>

                                                       s3<3>1

    SLICE_X13Y43.G1      net (fanout=1)        0.511   s3<3>

    SLICE_X13Y43.COUT    Topcyg                1.001   add2<2>

                                                       Madd_add2_lut<3>

                                                       Madd_add2_cy<3>

    SLICE_X13Y44.CIN     net (fanout=1)        0.000   Madd_add2_cy<3>

    SLICE_X13Y44.X       Tcinx                 0.462   add2<4>

                                                       Madd_add2_xor<4>

    SLICE_X16Y52.G3      net (fanout=3)        0.810   add2<4>

    SLICE_X16Y52.Y       Tilo                  0.759   Madd_add3C3

                                                       Madd_add3C31

    SLICE_X13Y52.BY      net (fanout=1)        0.682   Madd_add3C3

    SLICE_X13Y52.COUT    Tbycy                 0.972   out_reg<4>

                                                       Madd_add3_Madd_cy<5>

    SLICE_X13Y53.CIN     net (fanout=1)        0.000   Madd_add3_Madd_cy<5>

    SLICE_X13Y53.COUT    Tbyp                  0.118   out_reg<6>

                                                       Madd_add3_Madd_cy<6>

                                                       Madd_add3_Madd_cy<7>

    SLICE_X13Y54.CIN     net (fanout=1)        0.000   Madd_add3_Madd_cy<7>

    SLICE_X13Y54.COUT    Tbyp                  0.118   out_reg<8>

                                                       Madd_add3_Madd_cy<8>

                                                       Madd_add3_Madd_cy<9>

    SLICE_X13Y55.CIN     net (fanout=1)        0.000   Madd_add3_Madd_cy<9>

    SLICE_X13Y55.COUT    Tbyp                  0.118   out_reg<10>

                                                       Madd_add3_Madd_cy<10>

                                                       Madd_add3_Madd_cy<11>

    SLICE_X13Y56.CIN     net (fanout=1)        0.000   Madd_add3_Madd_cy<11>

    SLICE_X13Y56.COUT    Tbyp                  0.118   out_reg<12>

                                                       Madd_add3_Madd_cy<12>

                                                       Madd_add3_Madd_cy<13>

    SLICE_X13Y57.CIN     net (fanout=1)        0.000   Madd_add3_Madd_cy<13>

    SLICE_X13Y57.CLK     Tcinck                1.002   out_reg<14>

                                                       Madd_add3_Madd_cy<14>

                                                       Madd_add3_Madd_xor<15>

                                                       out_reg_15

    -------------------------------------------------  ---------------------------

    Total                                      9.076ns (6.019ns logic, 3.057ns route)

                                                       (66.3% logic, 33.7% route)

De este reporte los puntos mas importantes a analizar son los siguientes:  

1- Slack: en este caso es negativo (-1.576ns), lo que implica que el sistema no puede funcionar correctamente a la frecuencia requerida. 

2- Cantidad de niveles lógicos (logic levels): 10 en éste sistema. 

Con estos dos datos se puede deducir que, si el sistema lo permite, una solución para mejorar la performance del sistema es colocar flip-flops para cortar este larguísimo retardo combinacional y de ruteo. Ahora bien:

Dónde colocar los flip-flops de pipelining? 

Veamos, mediante el uso de otra herramienta disponible en todos los software de los distintos fabricantes de FPGA, normalmente llamada RTL Viewer, es posible 'ver' el esquemático, al nivel RTL, del sistema implementado. En la siguiente figura se muestra el RTL View generado por Quartus RTL Viewer del sistema bajo estudio: 

Al analizar el esquemático generado por el RTL Viewer es sencillo 'ver' el/los caminos de lógica combinacional más largos. Justamente estos caminos son los que se deben cortar colocando flip-flops. Así, los flip-flps de pipelining deberían ser: 4 sets de 16 flip-flops (bus es de 16 bits) a la salida de los multiplexer. 2 sets de 16 flip-flops entre los sumadores. Agregando estos flip-flops se corta el largo camino de 10 niveles lógicos (detallado por la herramienta de analisis de tiempo) y sus respectivos retardos de ruteo. De este modo, una vez modificado el código agregándole los respectivos flip-flops, se puede ver el RTL del 'nuevo' sistema:

Analizando ahora este sistema con la herramienta de análisis de tiempo da el siguiente resultado:

Slack (setup path):     2.452ns (requirement - (data path - clock path skew + uncertainty))

   Source:               add2_4 (FF)

   Destination:          out_reg_15 (FF)

   Requirement:          7.500ns

   Data Path Delay:      5.048ns (Levels of Logic = 6)

   Clock Path Skew:      0.000ns

   Source Clock:         clk_BUFGP rising at 0.000ns

   Destination Clock:    clk_BUFGP rising at 7.500ns

   Clock Uncertainty:    0.000ns

 

   Maximum Data Path: add2_4 to out_reg_15

     Location             Delay type         Delay(ns)  Physical Resource

                                                        Logical Resource(s)

     -------------------------------------------------  -------------------

     SLICE_X41Y29.XQ      Tcko                  0.514   add2<4>

                                                        add2_4

     SLICE_X15Y38.F1      net (fanout=1)        2.239   add2<4>

     SLICE_X15Y38.COUT    Topcyf                1.011   out_reg<4>

                                                        Madd_add3_lut<4>

                                                        Madd_add3_cy<4>

                                                        Madd_add3_cy<5>

     SLICE_X15Y39.CIN     net (fanout=1)        0.000   Madd_add3_cy<5>

     SLICE_X15Y39.COUT    Tbyp                  0.103   out_reg<6>

                                                        Madd_add3_cy<6>

                                                        Madd_add3_cy<7>

     SLICE_X15Y40.CIN     net (fanout=1)        0.000   Madd_add3_cy<7>

     SLICE_X15Y40.COUT    Tbyp                  0.103   out_reg<8>

                                                        Madd_add3_cy<8>

                                                        Madd_add3_cy<9>

     SLICE_X15Y41.CIN     net (fanout=1)        0.000   Madd_add3_cy<9>

     SLICE_X15Y41.COUT    Tbyp                  0.103   out_reg<10>

                                                        Madd_add3_cy<10>

                                                        Madd_add3_cy<11>

     SLICE_X15Y42.CIN     net (fanout=1)        0.000   Madd_add3_cy<11>

     SLICE_X15Y42.COUT    Tbyp                  0.103   out_reg<12>

                                                        Madd_add3_cy<12>

                                                        Madd_add3_cy<13>

     SLICE_X15Y43.CIN     net (fanout=1)        0.000   Madd_add3_cy<13>

     SLICE_X15Y43.CLK     Tcinck                0.872   out_reg<14>

                                                        Madd_add3_cy<14>

                                                        Madd_add3_xor<15>

                                                        out_reg_15

     -------------------------------------------------  ---------------------------

     Total                                      5.048ns (2.809ns logic, 2.239ns route)

                                                        (55.6% logic, 44.4% route) 

Fácilmente se puede observar el resultado de usar pipelining: se pasó de un slack negativo de -1.576ns a un slack positivo de +2.452ns. Del mismo modo, los niveles de lógica se redujerón de 10 niveles lógicos (sin pipe) a 6 niveles lógicos (con pipe). 

Observación:

Es importante saber que la herramienta de análisis de tiempo también ofrece una 'vista' tipo esquemático del camino de mayor retardo. Este esquemático puede también ser usado como fuente para saber donde colocar los registros de pipelining. Sin embargo, el problema de usar este esquemático es que éste esquemático es solo del camino mas critico, ofreciendo una 'vista' muy parcial de todo el 'data path' del sistema. Si se desea usar este esquemático como fuente de la ubicación de los registros de pipe se deberá tener mucho cuidado de no 'desbalancear' los distintos caminos de los datos del sistema (data path). Es decir, balancear correctamente los distintos caminos; esto signinfica que cualquier dato proveniente de cualquier entrada de datos debe atravesar el mismo numero de registros (de pipeline)  para alcanzar cualquier salida del sistema.. Por ejemplo, en el esquemático que se detalla arriba, si se hubiera considerado solamente el camino más crítico y colocado registros solo en ese camino, el sistema hubiera quedado algo como se muestra en la siguiente figura: 

Analizando esta vista RTL del sistema se puede observar un desbalance entre los caminos de los datos a sumar: El dato que va por camino (path) naranja sale del mux, para por un flip-flop, un sumador y otro flip-flop. El dato que va por el camino (path) verde, sale del mux, pasa por el sumador y luego al siguiente sumador. Por ello existe un total desbalance entre los caminos, y esto es justamente lo más importante a evitar cuando se pipeline un sistema. 

Desventaja del uso de pipeline: la latencia del sistema original se incrementa en forma proporcional a la cantidad de registros sumados al camino crítico. Sin embargo se debe tener claro que latencia no altera la funcionalidad del circuito. En el ejemplo detallado la latencia se ha incrementado por 2 ciclos de reloj (debido a los dos flip-flops en cadena). Hay sistemas que pueden soportar esta latencia, otros sistema que necesitarían una modificación para tolerar esa latencia, y otros que directamente no toleran latencia. Para los dos primeros casos pipelining es una solución, para el tercer caso, habría que buscar otra solución ya sea modificando el código original, modificando parámetros de place and route, realizando floorplaning, etc.