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
