En ciencias de la computación, el pipelining de instrucciones es una técnica para implementar paralelismo a nivel de instrucciones dentro de un procesador. Esta técnica intenta mantener cada parte del procesador ocupada con una instrucción diferente dividiendo la ejecución de las instrucciones en una serie de pasos secuenciales efectuados por etapas diferentes, las cuales procesan las diversas partes de las instrucciones en paralelo (organizadas en pipeline). De esta forma, las instrucciones fluyen a través de la CPU en etapas, las cuales típicamente utilizan una etapa por cada paso del ciclo de Von Neumann: obtener la siguiente instrucción; recuperar los operandos necesarios; ejecutar la instrucción; escribir los resultados.

Las computadoras RISC (Reduced Intruction Set Computer) tiene un conjunto de instrucciones simple y reducido en lugar de un conjunto de instrucciones complejo y especializado (CISC, Complex Instruction Set Computer). La principal característica distintiva de una arquitectura RISC es que el conjunto de instrucciones está optimizado para fluir en un pipeline de instrucciones altamente regular. Mediante arquitecturas RISC es posible comprender el funcionamiento de un pipeline de instrucciones simple, para luego estudiar pipelines más complejos y avanzados.



DLX es uno de los ejemplos clásicos de un diseño RISC. Se trata de una arquitectura de procesador RISC diseñada por John L. Hennessy y David A. Patterson (los principales diseñadores de Stanford MIPS y Berkeley RISC respectivamente) y fue creada principalmente con el propósito de la enseñanza. Es una de las arquitecturas más ampliamente utilizadas en los cursos de Arquitectura de Computadoras en las universidades de todo el mundo.

En el curso de Arquitectura de Computadoras de la Universidad Nacional del Sur utilizamos variaciones del pipeline DLX como herramienta de aprendizaje del pipeline de instrucciones de una CPU. Este artículo pretende demostrar un ejemplo del solapamiento de instrucciones a lo largo del pipeline de un procesador con arquitectura RISC de tipo DLX empleando diferentes optimizaciones.

Caso de estudio

Cierto procesador utiliza un pipeline RISC con cinco etapas: FETCH (obtener la instrucción desde memoria), DECODE (interpretar la instrucción y obtener sus operandos inmediatos o desde registros), EXECUTE (ejecutar la instrucción), MEMORY (leer/escribir a memoria en instrucciones LOAD/STORE) y WRITE-BACK (escribir los resultados de vuelta a registros).

El banco de registros se este procesador se lo accede dos veces por ciclo: para escritura en la primera mitad y para lectura en la segunda. Esto permite que sea posible obtener en la etapa de DECODE un operando que está siendo escrito por una instrucción previa en la etapa de WRITE-BACK en el mismo ciclo. Ya que primero ocurre el WRITE-BACK (en la primera mitad del ciclo) y luego la obtención de operandos del DECODE (en la segunda mitad del ciclo). Esta optimización simple a los conflictos de dependencias de datos RaW (Read after Write) permite evitar 1 ciclo de STALL del pipeline (retraso en la ejecución de instrucciones para resolver un hazard).

Además cuenta con caché independiente para instrucciones y para datos. Esta optimización evita conflictos de memoria ya que la siguiente instrucción a ejecutar se obtiene (durante el FETCH) desde la caché de instrucciones; mientras que un acceso a memoria (en la etapa MEMORY) se hace en la caché de datos. Se evitan así conflictos estructurales entre FETCH y MEMORY.

Este procesador posee una unidad funcional de suma de 1 ciclo, una unidad específica para el cálculo de direcciones efectivas de 1 ciclo y una unidad de multiplicación de 4 ciclos.

Sobre este procesador, se desea ejecutar la siguiente secuencia de instrucciones:

I1:   ADD  R1, R0, 0x0F
I2:   LD   R2, 0(R1)	
I3:   MUL  R3, R2, R7
I4:   MUL  R4, R2, R8
I5:   ADD  R5, R4, R3
I6:   ST   R4, 0(R1)

Solapamiento de instrucciones en un pipeline básico

El solapamiento de instrucciones a lo largo del pipeline se puede esquematizar utilizando un diagrama de Gantt donde se ubica una instrucción en cada fila y los ciclos del procesador en las columnas:

Otra forma de obtener el solapamiento puede ser organizando las etapas del pipe en las filas y rellenando con las instrucciones. También en en una tabla de instrucciones vs. etapas y rellenando con el ciclo en el cual cada instrucción ingresa a una etapa (más difícil de seguir).

En este solapamiento todo procede con normalidad hasta el ciclo 3. Durante el mismo, la instrucción I2 requiere leer el valor en el registro R1 (conflicto de datos RaW). Sin embargo, este resultado aún no ha sido escrito por la instrucción previa, con lo cual se frena el pipeline (STALL) hasta que I1 complete su WRITE-BACK en el ciclo 5. Con la optimización de doble acceso al banco de registros, en el mismo ciclo 5 I2 completa su DECODE y puede comenzar a ejecutar en el ciclo 6.

I2 es una instrucción LOAD que carga en R2 el contenido de la memoria en la dirección almacenada en R1.

En el ciclo 6 ocurre lo mismo. La instrucción I3 ingresa a DECODE pero no puede completarlo porque requiere el valor de R2 escrito por I2. Se frena el pipeline nuevamente hasta que I2 complete la escritura de R2 en el ciclo 8. Nuevamente el DECODE de I3 se puede completar en el mismo ciclo en que se escribe R2.

En el ciclo 9 comienza la ejecución de I3 e I4 ingresa a DECODE y lo completa (no hay conflicto de datos pues R2 ya fue actualizado). Sin embargo en el ciclo 10 R4 no puede ejecutar. Esto se debe a que I3 e I4 son multiplicaciones. La ejecución de una multiplicación demora 4 ciclos, con lo cual la ALU de multiplicación está ocupada hasta el ciclo 12 inclusive. Se trata de un conflicto estructural. Están los datos disponibles para ejecutar pero no se dispone del hardware (está siendo utilizado por otra instrucción). Nuevamente se resuelve con STALL del pipeline.

I4 puede comenzar a ejecutar recién en el ciclo 13. Mientras tanto ninguna instrucción posterior puede avanzar, pues I3 está ocupando la etapa de DECODE (no tiene a dónde ir).

En el ciclo 13 se libera el DECODE para que la instrucción I5 se pueda decodificar y se trae de memoria la instrucción I6 (FETCH). Sin embargo, no se puede completar el DECODE de I5 por conflicto RaW con R4. Debe finalizar la multiplicación (escribir el dato en el registro R4) para que proceda la suma I6.

El DECODE de la instrucción I5 se completa en el ciclo 18 y la ejecución concluye sin conflictos.

La ejecución de las 6 instrucciones concluye luego de 22 ciclos, con lo cual el CPI (Ciclos Por Instrucción) efectivo es igual a 22/6 = 3,66.

Forwarding

La optimización básica para minimizar la cantidad de STALL provocados por conflictos de datos verdaderos (RaW) consiste en disponer de los datos en el momento en que estos se conocen en lugar de esperar a la etapa WRITE-BACK. Se denomina forwarding o by-pass. No esperar que un dato llegue al registro destino para que el decoder lo tome de allí, sino establecer caminos alternativos hacia las entradas de las ALU de forma de reducir ciclos de STALL.

En el ejemplo anterior se observa cómo se retrasa la obtención del operando R4 en el DECODE de la instrucción I5 hasta el ciclo 9, cuando el resultado de la multiplicación ya estaba disponible a partir del ciclo 17. Con forwarding, la salida de la ALU de multiplicación se conecta directamente (by-pass) con la entrada de la ALU de suma.

Esto se puede aplicar a todas las ALU, incluso a operaciones de memoria de tipo LOAD, donde el operando está disponible al finalizar MEMORY.

En esta imagen se observa en color azul el circuito normal, donde un dato debe escribirse en el registro destino (durante WRITE-BACK) para poder ser leído en el DECODE y pasado a EXECUTE. En rojo se observa un by-pass de ejemplo que realimenta la salida de la ALU a sus entradas. Esto permitiría ejecutar de forma seguida dos sumas con dependencias RaW.

Con forwarding, una vez que finaliza la ejecución de una instrucción que produce un dato, este puede ser pasado a la entrada de la ALU que lo necesita para que se ejecute la instrucción que lo consume en el ciclo siguiente.

La cantidad de by-passes y su conexión entre las diferentes entradas incrementa la complejidad del control en cierta medida, aunque sigue siendo una optimización básica.

Con esta optimización, el diagrama de Gantt cambia de la siguiente forma:

En el ciclo 3 la instrucción I1 finaliza el cálculo de R1. Mediante by-pass es posible que la siguiente instrucción pueda comenzar su ejecución. En este caso se trata de una instrucción LOAD que requiere el operando para computar la dirección efectiva. Al mismo tiempo, en el ciclo 4 comienza el DECODE de I3 pero no se puede completar dado que no es posible obtener R2 mediante forwarding en el próximo ciclo (al tratarse de un LOAD, el dato estará disponible recién al finalizar la etapa MEMORY). Por ende no queda otra alternativa que frenar el pipeline (STALL) 1 ciclo hasta que se complete la etapa MEMORY de I2.

En el ciclo 5 se obtiene el dato desde memoria y se puede utilizar un by-pass para que en el ciclo 6 I3 comience su ejecución.A su vez, como I2 finaliza (WRITE-BACK) en el ciclo 6, durante el DECODE de I4, no se requiere by-pass de R2 hacia la segunda multiplicación (lee R2 directamente desde registro).

El conflicto estructural entre las dos multiplicaciones sigue existiendo. El forwarding sólo permite adelantar datos para mitigar conflictos de datos de tipo RaW. Por ende, en los ciclos 7, 8 y 9 se frena el pipeline hasta que se libere la ALU de multiplicación.

Y ahora viene la parte más interesante. El DECODE de I5 frena el pipeline esperando el dato generado por la multiplicación (registro R4), el cual se provee mediante by-pass para que I5 comience a ejecutar en el ciclo 14. Sin embargo, la instrucción I6 también requiere del valor actualizado del registro R4 (se trata de un STORE que escribirá ese valor en memoria). El DECODE de I6 se hace en el ciclo 14, instante en el que aún no ha sido escrito por I4 (la cual permanece en la etapa MEMORY). Esto implica que el valor de R4 deberá ser reenviado nuevamente (desde MEMORY de I4 a EXECUTE de I6) para que I6 pueda comenzar su ejecución en el ciclo 15. Esto se debe a que el dato de R4 está "en tránsito" desde la etapa EXECUTE a WRITE-BACK.

Mediante esta optimización, el CPI se reduce a 17/6 = 2,83.

Pipelining de unidades funcionales

Una optimización para evitar conflictos estructurales (como ocurre con la multiplicación de 4 ciclos) consiste en aplicar la técnica de pipelining en unidades funcionales. Por ejemplo es posible dividir a la multiplicación en 4 etapas en pipeline. De esta forma puede ingresar una multiplicación por ciclo al pipeline, evitando STALL en el DECODE de instrucciones posteriores.

Es posible implementar un pipeline de multiplicación empleando un árbol de CSA (Carry Save Adder) conocido como Wallace tree y así dividir a la multiplicación en etapas. Sea cual sea la técnica, estructurando la ALU de multiplicación en un pipeline de 4 etapas, es posible ingresar una operación de multiplicación por ciclo.

Con esta optimización, el solapamiento queda de la siguiente forma:

Los forwardings se resuelven exactamente igual que antes. La diferencia es que ahora no hay conflicto estructurales con las multiplicaciones, con lo cual se eliminan los STALL en la decodificación de I4.

Con esta nueva optimización, el CPI baja aún más hasta 14/6 = 2,33.

Referencias


Tal vez pueda interesarte


Compartí este artículo