Este artículo demuestra cómo aplicar las técnicas de desenrollado de bucles, reordenamiento de instrucciones y renombramiento de registros para evitar conflictos en el pipeline de instrucciones de un procesador, originados por dependencias de datos verdaderas.



Sea el siguiente conjunto de instrucciones que implementa un bucle:

I1:  LOOP:  LD      F0, 0(R1)
I2:         ADDD    F4, F0, F2
I3:         SD      F4, 0(R1)
I4:         DADDUI  R1, R1, #-8
I5:         BNE     R1, R2, LOOP

Rápidamente es posible darse cuenta que se trata de una porción de código que suma un valor (almacenado en F2) a todos los elementos de un arreglo, donde la dirección de memoria del último elemento se encuentra en el registro R2 (avanza de posiciones hacia direcciones de memoria descendentes).

La técnica de compilación de pipeline scheduling busca reordenar las instrucciones para evitar conflictos al ejecutar instrucciones en paralelo dentro del pipeline de instrucciones del procesador. Se trata de explotar el paralelismo a nivel de instrucciones (ILP, Instruction Level Parallelism).

Se observa que las instrucciones I1, I2 e I3 poseen dependencias RaW (read after write) en cascada. Se trata de dependencias de datos verdaderas. I2 requiere que I1 escriba F0 e I3 requiere que I2 escriba F4 antes de poder continuar. Esto implica que no es posible reorganizar el código (cambiar el orden de estas instrucciones) para acelerar el cómputo evitando conflictos.

A su vez, existe otra dependencia de datos RaW entre I4 e I5. I5 requiere que I4 escriba el valor de R1.

Por otro lado hay una antidependencia entre I4 e I3 (dependencia WaR, write after read) que impide que se ejecute I4 antes que I3. Si se cambia el valor en R1 antes del STORE, la instrucción I3 escribirá en la dirección de memoria incorrecta.

Supongamos que la latencia entre instrucciones para que los conflictos de datos verdaderos (RaW) no provoquen STALL del pipeline están dictadas por la siguiente tabla:

Instrucción que
escribe un valor
Instrucción que
lee un valor
Latencia
FP ALU opFP ALU op3
FP ALU opST double2
LD doubleFP ALU op1
LD doubleST double0
INT ALU op*1

Se observa, por ejemplo que se necesita una latencia de 2 ciclos entre I2 e I3 para que no haya STALL del pipeline.

La naturaleza de este código implica que poco pueda hacer la técnica de pipeline scheduling para evitar conflictos. Precisamente porque se trata de dependencias de datos verdaderas. Más aún teniendo en cuenta que existe una dependencia verdadera (RaW) adicional entre la instrucción I4 y la instrucción I1 de la iteración siguiente. Esto evita que se pueda aplicar la técnica de renombramiento de registros.

Se sabe que los conflictos de control (saltos condicionales e incondicionales) frenan el pipeline. Especialmente los saltos condicionales como el de la instrucción I5. Esto se debe a que, hasta que no se resuelva la condición, no es posible saber si se debe ejecutar la instrucción siguiente al salto o la instrucción destino del salto (target).

La técnica de loop unrolling (desenrollar bucles) busca minimizar la cantidad de conflictos de control repitiendo el código del bucle y utilizando menor cantidad de iteraciones. Esto siempre que el compilador sepa cuál es el número de iteraciones (o un múltiplo de ellas) que realizará el código. De esta forma se reduce la cantidad de STALLS.

Por ejemplo, si se desenrollan 4 copias del código del bucle, el resultado es el siguiente:

LOOP:  LD      F0, 0(R1)
       ADDD    F4, F0, F2
       SD      F4, 0(R1)
       LD      F0, -8(R1)
       ADDD    F4, F0, F2
       SD      F4, -8(R1)
       LD      F0, -16(R1)
       ADDD    F4, F0, F2
       SD      F4, -16(R1)
       LD      F0, -24(R1)
       ADDD    F4, F0, F2
       SD      F4, -24(R1)
       DADDUI  R1, R1, #-32
       BNE     R1, R2, LOOP

Notar cómo se ajustan los offsets en las instrucciones de acceso a memoria para reflejar el cambio de iteración. Y cómo al final se modifica el registro R1 de forma adecuada para que se avance a los siguientes 4 elementos

Ahora la cantidad de conflictos de control (saltos) se reduce a 1/4. Si antes se ejecutaban 100 iteraciones, se pasa de 100 conflictos de control a sólo 25. Esto puede ser una gran mejora, más aún teniendo en cuenta que la cantidad de ciclos de STALL involucrados en cada conflicto de control puede ser mayor a 1.

Esta técnica por sí sola no resuelve el problema de las dependencias de datos verdaderas (RaW). Se observa que siguen existiendo. Sin embargo, ahora es posible aplicar la técnica de pipeline scheduling de forma creativa sobre el código desenrollado. ¿Por qué? Porque ahora aparecen instrucciones independientes entre sí (si es que se aplica renombramiento de registros de forma adecuada). Claro está que se asume que la arquitectura dispone de la cantidad suficiente de registros.

Si en cada iteración utilizo un par de registros diferentes para computar la suma, el código resultante es el siguiente:

LOOP:  LD      F0, 0(R1)
       ADDD    F4, F0, F2
       SD      F4, 0(R1)
       LD      F10, -8(R1)
       ADDD    F14, F10, F2
       SD      F14, -8(R1)
       LD      F20, -16(R1)
       ADDD    F24, F20, F2
       SD      F24, -16(R1)
       LD      F30, -24(R1)
       ADDD    F34, F30, F2
       SD      F34, -24(R1)
       DADDUI  R1, R1, #-32
       BNE     R1, R2, LOOP

Con este renombramiento, muchas instrucciones resultan ahora totalmente independientes entre sí, por ejemplo:

       SD      F4, 0(R1)
       LD      F10, -8(R1)

Lo que implica que puedan ordenarse de cualquier forma.

Aplicando pipeline scheduling es posible agrupar instrucciones independientes entre sí para generar latencias suficientemente grandes entre instrucciones con conflictos RaW. El código resultante es el siguiente:

LOOP:  LD      F0, 0(R1)
       LD      F10, -8(R1)
       LD      F20, -16(R1)
       LD      F30, -24(R1)
       ADDD    F4, F0, F2
       ADDD    F14, F10, F2
       ADDD    F24, F20, F2
       ADDD    F34, F30, F2
       SD      F4, 0(R1)
       SD      F14, -8(R1)
       SD      F24, -16(R1)
       SD      F34, -24(R1)
       DADDUI  R1, R1, #-32
       BNE     R1, R2, LOOP

Primero se hacen todos los load, luego las sumas, y finalmente los stores. Ahora las instrucciones con conflictos RaW tienen 4 ciclos de latencia entre sí (asumiendo un pipeline escalar).

Ahora bien, aún se requiere un ciclo de latencia entre la suma del índice y el salto. Es posible optimizar esta solución adelantando la suma del índice de la siguiente forma:

LOOP:  LD      F0, 0(R1)
       LD      F10, -8(R1)
       LD      F20, -16(R1)
       LD      F30, -24(R1)
       DADDUI  R1, R1, #-32
       ADDD    F4, F0, F2
       ADDD    F14, F10, F2
       ADDD    F24, F20, F2
       ADDD    F34, F30, F2
       SD      F4, 32(R1)
       SD      F14, 24(R1)
       SD      F24, 16(R1)
       SD      F34, 8(R1)
       BNE     R1, R2, LOOP

El índice se actualiza luego del último load. Notar cómo se ajustan los offsets de los stores para escribir en las locaciones de memoria correctas.

Por supuesto el límite a esta técnica de compilador es la cantidad de registros lógicos que disponga el hardware subyacente (CPU).


Tal vez pueda interesarte


Compartí este artículo