Software pipelining (Organización del Computador II)

De Cuba-Wiki

Clase de 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:

Clase 9/11/2006 - Otro ejemplo de software pipelining

Lo que hay que hacer: 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.