jueves, 14 de julio de 2011

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. 

sábado, 2 de julio de 2011

Como mantener (1) el nombre de una señal y (2) un/varios registro/s después de la Síntesis

A veces nos encontramos con la sorpresa que la restricción (constraint) que aplicamos a una señal en particular nos genera un error que mas o menos nos dice que la señal que se quiere restringir no existe (!)(?).... entonces nos preguntamos: pero si la señal está en el código, como puedo obtener este mensaje de error diciendo que la señal no existe? . . .  
Pues, sucede que la herramienta de síntesis muchas veces absorbe algunas señales durante el proceso de optimización y síntesis. Esto sucede porque cuando una señal pasa de un bloque lógico a otro lo que la herramienta de síntesis hace es asignarle un nombre a veces aleatorio, a veces una combinación de los nombres de las señales. Así, cualquier restricción escrita sobre la señal original no será posible que se aplique, como así también si se desea encontrar esa señal dentro de una herramienta de depuración, no será posible, pues el nombre original, que es el que estamos usando en las restricciones o en la herramienta de depuración (debug) interna del FPGA (Chipscope(Xilinx) /SignalTap(Altera)/ Reveal(Lattice)), no existe más.
Para lograr que la señal que deseamos sea mantenida, y por ende mantenga su nombre, se debe usar un atributo de síntesis que normalmente se llama 'keep' (mantener). El uso del atributo 'keep' sobre una señal le dice a la herramienta de síntesis que mantenga la señal, previniendo que la señal con la cual se asocia el atributo sea absorbida y por ende cambiada de nombre. Como 'keep' es un atributo se síntesis el nombre del atributo en sí cambia dependiendo de la herramienta de síntesis que se use:

- XST Xilinx: atributo es 'keep' y es definido como 'string'
- Quartus Altera: atributo es 'keep' y es definido como 'boolean'
- Synplify (para clq vendedor): atributo es 'syn_keep' y es definido como 'boolean'
- Precision (para clq vendedor): atributo es 'keep'

Como todo atributo, 'keep' debe primero ser definido y luego se lo asocia a la señal que se desea mantener (keep). Ejemplo:


1 -- declaracion de la senal interna
2 signal dato_interno: std_logic;
3
4 -- declaracion del attributo
5 attribute keep: string;
6 -- asociacion del atributo con una senal especifica
7 attribute keep of dato_interno: signal is "true";


En el ejemplo al especificar el atributo de síntesis 'keep' como 'true' se está asociando el atributo 'keep' a la señal dato_interno . De este modo el nombre 'dato_interno' asociado a esa señal será mantenido, y por ello será posible referirlo ya sea en el archivo de restricción o en la herramienta de depuración (debug) interna del FPGA.
El mismo ejemplo para los casos en que 'keep' es definido como boolean es el siguiente: 


1 -- declaracion de la senal interna
2 signal dato_interno: std_logic;
3
4 -- declaracion del attributo
5 attribute syn_keep: boolean;
6 -- asociacion del atributo con una senal especifica
7 attribute syn_keep of dato_interno: signal is true;

Como resúmen se puede decir que en las siguientes circunstancias este atributo 'keep' es útil: 
- Para preservar una señal (cable) que de otro modo seria removida como resultado de la optimización, o renombrada en caso de ser absorbida en un bloque lógico. 
- Para prevenir que celdas duplicadas sean unidas durante optimización. En estos casos 'keep' debería ser asociado con las entradas a las celdas que se desean preservar. 
Un ejemplo de este último caso es el siguiente: 


 1 library ieee;
 2 use ieee.std_logic_1164.all;
 3
 4 entity test_keep is
 5   port(
 6     dato_a: in  std_logic;
 7     dato_b: in  std_logic;
 8     clk   : in  std_logic;
 9     out_1 : out std_logic;
10     out_2 : out std_logic
11     );
12 end entity test_keep;
13
14 architecture beh of test_keep is
15  signal and_interna: std_logic;
16  signal and_out_ff1: std_logic;
17  signal and_out_ff2: std_logic;
18
19  attribute syn_keep: boolean;
20  attribute syn_keep of and_out_ff1: signal is true;
21  attribute syn_keep of and_out_ff2: signal is true;
22
23 begin
24
25  and_interna <= dato_a and dato_b;
26  and_out_ff1 <= and_interna;
27  and_out_ff2 <= and_interna;
28
29  test: process (clk)
30  begin
31   if(rising_edge(clk)) then
32     out_1 <= and_out_ff1;
33     out_2 <= and_out_ff2;
34   end if;
35  end process test;
36 end beh;
 



Los resultados de la implementación del código del ejemplo se pueden ver debajo. En la parte izquierda la implementación sin el uso del atributo keep, y sobre la derecha se muestra la conservación de los registros, tal como es descrito en el código, como resultado del uso del atributo 'keep'.





Finalmente, para completar en detalle este tema, quiero comentarles que existe otro atributo similar (pero no igual) comúnmente llamado 'preserve' o 'syn_preserve'. Este atributo se usa para preservar registros, NO se usa para preservar señales (cables). 
El ejemplo anterior puede ser re-escrito para preservar los registros utilizando 'syn_preserve' sobre los dos registros. Debajo se puede encontrar el código correspondiente: 


 1 library ieee;
 2 use ieee.std_logic_1164.all;
 3
 4 entity test_keep is
 5   port(
 6     dato_a: in  std_logic;
 7     dato_b: in  std_logic;
 8     clk   : in  std_logic;
 9     out_1 : out std_logic;
10     out_2 : out std_logic
11     );
12     attribute syn_preserve: boolean;
13     attribute syn_preserve of out_1: signal is true;
14     attribute syn_preserve of out_2: signal is true;
15 end entity test_keep;
16
17 architecture beh of test_keep is
18  signal and_interna: std_logic;
19
20 begin
21
22  and_interna <= dato_a and dato_b;
23
24  test: process (clk)
25  begin
26   if(rising_edge(clk)) then
27     out_1 <= and_interna;
28     out_2 <= and_interna;
29   end if;
30  end process test;
31 end beh;


Las implementaciones respectivas se observan a continuación: 






Cabe mencionar que en éste ejemplo se hace uso del atributo 'syn_preserve' para mantener un registro de un puerto de salida del componente declarado en la entidad. Por esta razón el atributo se define y asocia a la señal (puerto) donde está declarada, es decir en la entidad. Sin embargo, se debe tener claro, que este atributo se puede asociar también a registros internos del componente. En este caso, el atributo se definiría y asociaría en la parte declarativa de la arquitectura, que es donde está declarada la señal de salida del registro. 


Nota: dependiendo de la fuente consultada, algunos consideran 'keep' como una Directiva, otros como un Atributo. Por ejemplo en el manual de referencia de Synplify 'syn_keep' es considerado una Directiva, mientras que en los manuales del XST y Quartus es considerado un Atributo. Independientemente de como es considerado, la función del atributo 'keep' es exactamente la misma.