Software pipelining (Organización del Computador II)

Ejemplo 1

Corresponde a la clase del día 2/11/06

Enunciado

v[n]-> 16bits
w[n]-> 16bits 
x[n]-> 16bits

x[i] = (v[i]+w[i])^2

Pseudo Codigo

for (i=0; i < n; i++) 
    x[i]= (v[i] + w[i]) * (v[i] + w[i])

R32 = v, R33 = w, R34 = x, R35 = n, R36 = i

Codigo

alloc r20 = ar.pfs, 4,3,0,0 
add r36 = r0,r0 
ciclo: 
    cmp.lt p2,p3=r36,r35 
    (p3) br.cond fin

     ld2 r37=[r32],2 // CARGA 
     ld2 r38= [r33],2 

     add r37= r37,r38 //SUMA

     pmpy2.r r37=r37,r37 //PRODUCTO

     st2 [r34]=r37,2 // GUARDADO

     br.cond ciclo

fin:

Optimizacion con rotacion

v[i] ->2reg 
w[i] ->2reg 
Suma ->2reg 
Producto ->2reg

Empiezo de R32 que son los rotativos

r32 r33 r34 r35 r36 r37 r38 r39
|_vi|___|wi_|___|___|___|___|___|___|

r33 r34 r35 r36 r37 r38 r39 r32
|v0_|w1_|w0_|___|___|___|___|v1_|

ld2 r32=[--],2       // 1ªetapa 
ld2 r34= [--],2      //
add r36= r33,r35     // 2ª etapa
pmpy2.r r38=r37,r37  // 3ª etapa
st2 [--]=r39,2       // 4ª etapa

ctop y cexit, pone en 1 pr63 y lo rota (pr16 a pr63 se va poniendo en 1s)(uso para controlar q se ejecuta y q no) wtop y wexit, pone en 0 pr63 y lo rota (pr16 a pr63 va poniendo ceros)

alloc r20= ar.pfs,4,9,0,8 // los de rotacion siempre multiplo de 8
mov ar.ec= 4 mov pr.rot= 0x-----

ciclo: 
  cmp.lt p16,p3=--,-- 
  (p16) br.wexit fin
  (p17)ld2 r32 = [--],2 // 1ªetapa
  (p17)ld2 r34= [--],2 //
  (p18)add r36 = r33,r35 // 2ª etapa
  (p19)pmpy2.r r38 = r37,r37 // 3ª etapa
  (p20)st2 [--] = r39,2 // 4ª etapa
   add -- = 1, -- 
   br.cond ciclo
fin:

Versión completa

.global sumaCuadrado
.proc sumaCuadrado
sumaCuadrado:
	alloc r46=ar.pfs, 4, 14, 0, 8;;
	mov r41=in0
	mov r42=in1
	mov r43=in2
	mov r44=in3
	mov r45=0
	
	mov pr.rot=0
	mov ar.ec=4
	LOOP:	
		cmp.lt p16, p0=r45,r44
		(p16) br.wexit.sptk.many END
		(p17) ld4 r32=[r41], 4
		(p17) ld4 r34=[r42], 4
		(p18) add r35=r33, r35
		(p19) pmpy2.r r36=r36,r36
		(p20) st4 [r43]=r37, 4
		add r45=r0,r45,1
		br.cond.sptk.many LOOP
	END:
	br.ret.sptk.many b0
.endp sumaCuadrado

Código en C para probarlo:

#include "stdio.h"
#define size 9
extern void sumaCuadrado(int*, int*, int*,int);


 
void printArrayInt(int* array,int length)
{
	int i=0;
	printf("[");
	while(i<length)
		{
			
			printf("%i,  ",array[i]);
			i++;
		}
	printf("]\n");
}
int main(){
		testSumaVec();
}

int testSumaVec(){
		int v[size]={8,-10,-5,3,4,6,5,7,8};
		int w[size]={5,2,-1,0,9,2,1,0,2};
		int x[size+1]={0,0,0,0,0,0,0,0,0,0};
		int check[size];
		
		for(int i=0;i<size;i++)
		{
			check[i]=(v[i]+w[i])*(v[i]+w[i]);
			//check[i]=(v[i]*w[i-1])+v[i-1]-w[i];
		}
		
		printArrayInt(v,size);
		printArrayInt(w,size);
		
		sumaCuadrado(v,w,x,size);
		
		printArrayInt(x,size+1);
		
		printf("Check:\n");
		
		printArrayInt(check,size);

	return 0;
}

Ejemplo 2

Corresponde a la clase del 9/11/2006

Pseudocódigo

X[i] = V[i] * W[i-1] + V[i-1] - W[i]

for(i=j,i<n, i++)
	X[i] = V[i] * W[i-1] + V[i-j] - W[i]

El cuerpo del ciclo sería (sin rotación de registros):

a) 	ld2 R35 = V[i], 2
b)	ld2 R36 = W[i], 2
c)	pmpy2.r R37 = R35, R39
d)	add R37 = R37, R38
e)	sub R37 =	 R37 , R36
f)	st2  [x] = R37, 2 
mov R38 = R35
mov R39 = R36

Para aplicar software pipelining dividimos en etapas. Los criterios son disponibilidad de recursos y dependencias de datos. Elegimos que registros asignamos a cada etapa:

1) a y b
2) c
3) d
4) e
5) f

Notar que los MOV ya no van en la versión con las rotaciones, ya que este tipo de movimientos son justamente los que hacen las rotaciones.

¿Cuántos registros para cada cosa? "Criterio": en cuántas etapas después lo voy a necesitar.

V[i]  -> 2 "slots/registros"  R32-R33
W[i] -> 4 "slots"  R34- R37
pmpy -> 2 R38 - R39
add -> 2 R40 - R41 
sub -> 2 R42 - R43

Código con esta "propuesta":

br.wexit
(p17) 	ld2 R32 = V[i], 2
(p17)	ld2 R34 = W[i], 2
(p18)	pmpy2.r R38 = R33, R36 	// R36 porque W[i] se inicializa afuera del ciclo, por lo tanto debemos ver dónde queda luego de las tres primeras etapas
(p19)	add R40 = R39, ???
(p20)	sub R42 = R37 , R36
(p21)	st2  [x] = R43, 2

Problema: Nos equivocamos al decir que V[i] necesita 2 registros, haciendo el seguimiento salta que pisamos algo que necesitábamos, el V[i-1]. El error: Pensamos que el V[i] solo se utilizaba en pmpy, pero más adelante, en la suma, se usaba V[i-1], y lo deberíamos haber tenido en cuenta...

Reformulamos asignación de registros:

V[i]  -> 4 "slots/registros"  R32-R35
W[i] -> 4 "slots"  R36- R39
pmpy -> 2 R40 - R41
add -> 2 R42 - R43
sub -> 2 R44 - R45

Código con esta "propuesta":

br.wexit
(p17) 	ld2 R32 = V[i], 2
(p17)	ld2 R36 = W[i], 2
(p18)	pmpy2.r R40 = R33, R38
(p19)	add R42 = R41,R35
(p20)	sub R44 = R43 , R39
(p21)	st2  [x] = R45, 2

Respecto a los wexit, cuando la condición es verdadera NO SALTAN. El epílogo es normalmente #etapas -1 . Pero como en este caso corta en 1, acá seria #etapas.

Versión completa

Puede ser que el alloc sea exagerado...

.global sumaVec
.global printReg
.proc sumaVec
sumaVec:
	alloc loc0=ar.pfs,4,15,1,16
	
	mov r48=in0
	mov r49=in1
	mov r50=in2
	
	add in3=-1, in3
	mov ar.lc=in3

	mov pr.rot=0
	
	ld4 r32=[r48],4
	ld4 r36=[r49],4
		
	mov ar.ec = 5
	
	BUCLE:
	br.cexit.sptk.many FIN
		(p16) ld4 r32=[r48],4
		(p16) ld4 r36=[r49],4
		(p17) pmpy2.r r40=r33, r38
		(p18) add r42=R41, R35
		(p19) sub r44=r43, r39
		(p20) st4 [r50]=r45, 4
		br.cond.sptk.many BUCLE
	FIN:
	br.ret.sptk.many b0
.endp sumaVec

Para probar esto pueden usar el código C posteado para el ejercicio anterior y modificar los nombres de las funciones llamadas y descomentar la línea que ya crea un vector con los resultados correctos. Recuerden que este ejercicio hace todo para i=1 en adelante (por que usa V[i-1] y W[i-1].

Software pipelining para esconder latencias

Corresponde a la clase teórica del 9/11/2006

El siguiente ejercicio de software pipelining tiene como objetivo calcular las sumas acumuladas de un vector de números de punto flotante usando la instrucción "multiply and add" (fma). La idea es esconder una latencia de 9 ciclos para el LD y una latencia de 4 ciclos del FMA. Para más info sobre un ejercicio casi idéntico a este pueden remitirse al manual Intel Itanium Architecture: Software Developer's Manual: Volume 1: Application Architecture en la página 1:197

.global sumas
.proc sumas
sumas:
	alloc loc0=ar.pfs,2,5,0,0

	add in1=-1,in1
	mov ar.lc=in1
	mov pr.rot=1<<16

	mov f34=f0
	mov ar.ec=10
	BUC:
		(p16) ldfd f32=[in0], 8
		(p25) fma f42=f46,f1,f41
	br.ctop.sptk.many BUC
	fadd f8=f0,f0
	fadd f8=f8,f43
	fadd f8=f8,f44
	fadd f8=f8,f45
	fadd f8=f8,f46
	
	br.ret.sptk.many b0
.endp sumas