Mini-Tutorial de Software Pipelining (Organización del Computador II)

En esta página encontrarás una pequeña introducción a Software Pipelining para después poder abordar ejemplos más complicados. De cualquier manera se supone que leiste todos los ejemplos del manual de Intel y que tenés una idea del tema pero... no sabés por donde empezar. Voy a ir poniendo las cosas con las que me topé mientras trataba de hacer un ejercicio.

Enunciado

En este ejercicio vamos a llenar un vector de gran tamaño con unos ciertos datos iniciales:

v[i] = i * 2

...y luego usando software pipelining vamos a calcular:

v[i] = v[i] + v[i - 2]

Código C

Tendremos un código C que hace las cosas que en este momento no nos interesan y llama a la función que haremos luego.

#include <stdio.h>
#include <string.h>

/* un tam considerable para que de diferencia en el pfmon */
#define TAM 100000

/* funcion en asm para probar software pipelining */
extern void func_asm(int *vec);

#ifdef _DEBUG_
/* esta la hacemos en C para comparar */
void func_C(int *vec)
{
    int i;
    for(i = 2; i < TAM; ++i) vec[i] = vec[i] + vec[i - 2];
}
#endif

/* punto de entrada */
int main()
{
    int i;
#ifdef _DEBUG_
    int vec1[TAM];
#endif
    int vec2[TAM];

    /* llena el vector con algo */
    for(i = 0; i < TAM; ++i)
    {
#ifdef _DEBUG_
        vec1[i] = i * 2;
#endif
        vec2[i] = i * 2;
    }

    /* aplico las funciones a los respectivos vectores */
#ifdef _DEBUG_
    func_C(vec1);
#endif
#ifndef _SOLO_LLENAR_
    func_asm(vec2);
#endif

#ifdef _DEBUG_
    /* compara y nos dice que piensa */
    if(memcmp(vec1, vec2, sizeof(int) * TAM) == 0)
    {
        printf("Iguales!\n");
    }
    else
    {
        printf("Distintos!\n");
    }

    /* muestra los primeros 10 */
    for(i = 0; i < 10; ++i)
    {
        printf("[%i] vec1 = %i, vec2 = %i\n", i, vec1[i], vec2[i]);
    }
    
    /* muestra los ultimos 10 */
    for(i = TAM - 10; i < TAM; ++i)
    {
        printf("[%i] vec1 = %i, vec2 = %i\n", i, vec1[i], vec2[i]);
    }
#endif
	
    return 0;
}

Voy a hacer una breve explicación de lo que trata de hacer este código: Crea un vector y lo llena con los datos previamente mencionados, le aplica una función que escribiremos en assembler y opcionalmente luego compara los contenidos con un vector generado con una rutina en C. Los "#define _DEBUG_" y "#define _SOLO_LLENAR_" serán usados más tarde para la etapa de benchmarking.

Version sin software pipelining

Primero hagamos una funcion que cumpla con lo pedido pero no use software pipelining, luego la usaremos para comparar la eficiencia de la técnica.

.global func_asm
.align 32
.text

.proc func_asm
func_asm:
    alloc loc0 = ar.pfs, 1, 4, 0, 0

    mov loc1 = in0
    add in0 = 8, in0
    movl loc2 = 100000 - 2
    mov ar.LC = loc2

for_loop:
    ld4 loc2 = [loc1], 4
    ld4 loc3 = [in0]
    add loc2 = loc2, loc3
    st4 [in0] = loc2, 4
    br.cloop.dptk.few for_loop
    
    mov ar.pfs = loc0
    br.ret.sptk.many b0;;
.endp func_asm

Esta versión funciona, compilamos el programa con el comando: "icc -D_DEBUG_ main.c func_normal.s -o normal", esto crea un ejecutable llamado "normal". El parámetro "-D_DEBUG_" es para que el precompilador defina el macro _DEBUG_ y se compilen los bloques condicionales a ese macro.

A por el software pipelining!

Vamos a complicarnos un rato la vida para lograr un programa con eficiencia digna de los dioses. ¿Cómo empezamos? Bueno, vamos a usar rotación de registros ya que en la fórmula

v[i] = v[i] + v[i - 2]

usamos elementos que ya calculamos anteriormente, por lo tanto esta técnica nos puede servir.

¿Cómo, para qué, qué y por qué roto?

En este caso vamos a rotar los registros generales (r32, r33, etc.), nos sirve para calcular lo que dijimos antes. Los registros que rotan empiezan del r32 para adelante y le tenemos que avisar al procesador cuantos vamos a rotar usando la función alloc. El numero debe ser múltipo de 8! ¿Y si la cantidad que quiero usar no es múltiplo de 8? No importa, tenemos muchos registros para desperdiciar asi que ponemos el multiplo de 8 más cercano (hacia arriba). La sintaxis es:

alloc rN = ar.pfs, in, local, out, rot

¿Pero... me rota los "in" también?

Si. Rota desde el registro r32 en adelante por lo tanto si tenés 1 variable de entrada al principio va a caer en r32 y después se va a ir rotando. A veces sirve pero en nuestro caso no porque nos pasan un puntero y no nos interesa que el puntero vaya rotando.

Lo que hay que hacer cuando queremos dejar cosas fijas es ponerlas "lo suficientemente arriba" para que no roten. Eso quiere decir que si le pasamos al alloc que ibamos a rotar 8 tenemos que poner la variable al menos en r32 + 8. Esto sucede porque todos los anteriores rotan pero del r32 + 8 en adelante ya no.

Eligiendo los registros

La fórmula que queremos calcular

v[i] = v[i] + v[i - 2]

se puede pensar (con un cerebro pipelining-enabled) como

r32 = r32 + r34

¿Por qué? En cada iteracion cargamos v[i] en r32, por lo tanto sea cual sea el momento, lo que hace 2 ciclos fue v[i] (o sea v[i - 2]) ahora ya rotó 2 registros y se va a encontrar en r34.

Armando el ciclo

Hagamos un pseudocódigo de lo que queremos hacer

ld4 r32 = v[i]
add r32 = r32, r34
st4 v[i] = r35

Vamos a suponer que en r41 tenemos el puntero del que tenemos que leer y en loc10 el puntero a donde debemos escribir, por lo tanto esto quedaría

ld4 r32 = [r41], 4
add r32 = r32, r34
st4 [r42] = r35, 4

Agregamos los ",4" para que incremente el indice luego de leer o escribir.

Predicando

Ahora tenemos que armar un orden de ejecución del ciclo que controle el llenado del pipe y luego el vaciamiento. Nosotros sabemos que la latencia del load es de 2 ciclos asi que aprovechemos eso también!

(p16) ld4 r32 = [r41], 4
(p18) add r32 = r32, r34
(p19) st4 [r42] = r35, 4

Al principio de todo el unico predicado que valdrá 1 será el p16 (porque asi lo inicializaremos luego) por lo tanto en el primer ciclo sólo se ejecutará un load.

En el segundo ciclo p16 habrá rotado a p17 y un nuevo 1 estará en p16. De esta manera en otro pipe se ejecutará un nuevo load pero en el nuestro todavía no pasa nada porque p18 y p19 siguen siendo 0.

En el tercer ciclo ya se habrá superado la latencia del load y tendremos en r34 el valor que en su momento (hace 2 ciclos) le dijimos que cargue en loc0. ¿Que pasa con el r32 "de ahora"? Bueno, podemos suponer que lo tenemos cargado. Esto es algo así como la inducción, los anteriores ya los tenemos cargados de alguna manera.

Notemos que el que ahora es r32 (y que modificamos con el add) contiene

v[i] = v[i] + v[i - 2]

y que dentro de dos ciclos va a ser r34, si nos ponemos en ese contexto podemos ver que esto funciona! el registro va a ir rotando y tomará su lugar dentro de 2 ciclos para luego morir e irse al cielo de los registros.

Inicializando (eso que siempre falta)

Si los registros empiezan con basura esto no funciona, además no le dijimos al procesador cómo poner los registros de predicado ni cuantas iteraciones debe hacer... un desastre, vamos a hacerlo

alloc r40 = ar.pfs, 1, 11, 0, 8

movl r42 = 100000 - 1
mov ar.LC = r42
mov ar.EC = 4
mov pr.rot = 1 << 16

mov r41 = in0
mov r42 = in0

mov r32 = 0
mov r33 = 0

Ahora por partes...

alloc r40 = ar.pfs, 1, 11, 0, 8

Estamos armando el stack frame y avisamos que viene una variable de entrada y vamos a necesitar 11 locales (en realidad no tantas pero como queremos algunas fijas tienen que ser más de 8). Tenemos 0 variables "de salida" (no llamamos a ninguna otra función) y vamos a rotar los primeros 8 registros. Notar que guardamos esto en loc8 y esta no rota 8 (menos mal).

movl r42 = 100000 - 1
mov ar.LC = r42

100.000 es un numero grande y no nos deja meterlo como inmediato en ar.LC asi que hay que pasarlo por una local. En el caso anterior hacemos 100.000 - 2 iteraciones y en este ponemos 100000 en el Loop Counter, ¿por qué? Porque el manual dice que en caso de "counted loop" pongamos loop count - 1.

mov ar.EC = 4

El epílogo consta de 3 stages, cuando el pipe se empieza a drenar se necesitan 3 ciclos para terminar. El manual dice que para "counted loops" pongamos epilog stages + 1

mov pr.rot = 1 << 16

Esto setea los registros de predicado. El << es un shift y esta instrucción setea en 1 el p16 y en 0 todo el resto.

mov r41 = in0
mov r42 = in0

No queremos que roten los punteros asi que los guardamos en unas variables fijas.

mov r32 = 0
mov r33 = 0

Los primeros dos valores los tenemos que poner a mano porque el loop "supone que los tiene". Es como en fibonacci que tenías que poner que los primeros valen 1.

Juntemos todo!

El código completo y listo para compilar quedaría así:

.global func_asm
.align 32
.text

.proc func_asm
func_asm:
    alloc r40 = ar.pfs, 1, 11, 0, 8

    movl r42 = 100000 - 1
    mov ar.LC = r42
    mov ar.EC = 4
    mov pr.rot = 1 << 16

    mov r41 = in0
    mov r42 = in0

    mov r32 = 0
    mov r33 = 0

for_loop:
    (p16) ld4 r32 = [r41], 4
    (p18) add r32 = r32, r34
    (p19) st4 [r42] = r35, 4
    br.ctop.dptk.few for_loop

    mov ar.pfs = r40
    br.ret.sptk.many b0;;
.endp func_asm

ctop

Hubo otro cambio respecto a la versión sin software pipelining. Ya no tenemos más cloop y tenemos ctop. Esta función hace parte de la magia, en este caso básicamente decrementa el LC y rota todos los registros poniendo un 1 en p16. Dirigirse al artículo correspondiente en la página de Organización del Computador II para más información acerca de estas fuciones.

Compilemos

Si ejecutamos el comando "icc -D_DEBUG_ main.c func_sp.s -o sp" creamos un ejecutable llamado "sp" con esta nueva versión. Si lo ejecutamos podemos ver que funciona perfectamente.

Análisis del pipe

Pongan un lindo grafiquito (tablas) con las etapas, dale?

¿Y todo esto para que?

Performance! performance! Llegó el momento del benchmarking, primero compilemos los dos programas para que no muestren nada por pantalla.

icc -D_SOLO_LLENAR_ main.c func_normal.s -o llenar

Este programa lo unico que hace es llenar el vector con los datos base, lo vamos a usar para comparar.

icc main.c func_normal.s -o normal

Este programa usa la versión sin software pipelining.

icc main.c func_sp.s -o sp

Este programa usa software pipelining.

Ejecutando el comando "pfmon" sobre los archivos llegué al siguiente resultado:

Solo llenar el array:
* 5745658 CPU_CYCLES

Sin software pipelining:
* 6094463 CPU_CYCLES

Con software pipelining:
* 5779235 CPU_CYCLES

Diferencia:
* 315228 ciclos mejor que la version normal
* Sólo 33557 ciclos más que el rellenado del array (incluso cuando el vector es de 100.000 entradas!)

Conclusión

Espero que les sirva y que agreguen lo que sea necesario =)