El CPI ideal de 1 es difícil de conseguir debido a:
Load stalls (1 or 2 clock cycles)
Branch stalls (2 cycles + unfilled slots)
FP result stalls: RAW data hazard (latency)
FP structural stalls: Not enough FP hardware (parallelism)
1
R4000 PRESTACIONES
ILP: Solapa la ejecución de instrucciones no relacionadas
gcc -> 17% instr. de transferencia de control
Conjuntos de 5 instrucciones + 1 branch
Ir más allá de un bloque básico para conseguir un mayor paralelismo al nivel de instrucción
Paralelismo a nivel de bucle es una oportunidad SW y HW
2
SEGMENTACIÓN AVANZADA Y PARALELISMO AL NIVEL DE INSTRUCCIONES (ILP)
ALGUNOS TIPOS DE OPTIMIZACIÓN DE CÓDIGO
Entre las posibles técnicas de optimización de código tenemos
Reordenación del código para eliminar burbujas y aprovechar la ventana de retardo.
Desenrollado de bucles.
Software pipelining.
3
Loop: LD F0,0(R1) ;F0=vector element
ADDD F4,F0,F2 ;add scalar from F2
SD 0(R1),F4 ;store result
SUBI R1,R1,8 ;decrement pointer 8 Bytes (DW)
BNEZ R1,Loop ;branch R1!=zero
NOP ;delayed branch slot
4
¿Dónde están las detenciones?
EJEMPLO: BUCLES ? DÓNDE ESTÁN LOS RIESGOS?
LD F0, 0(R1)
ADDD F4, F0,F2
SD 0(R1) ,F4
SUBI R1, R1,8
BNEZ R1, Loop
NOP
NOP
5
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) x
(Gp:) IF
IF
ID
Ex
M
(Gp:) x
(Gp:) x
(Gp:) Ex
(Gp:) Wb
(Gp:) IF
(Gp:) IF
(Gp:) ID
(Gp:) ID
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) —
(Gp:) Ex
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) M
(Gp:) x
(Gp:) x
(Gp:) x
(Gp:) IF
(Gp:) ID
(Gp:) M
(Gp:) —
Ventana de retardo
Loop:
(Gp:) Wb
1
17
(Gp:) IF
…
EJEMPLO: BUCLES ? DÓNDE ESTÁN LOS RIESGOS?
6
1 Loop: LD F0,0(R1)
2 ADDD F4,F0,F2
3 SUBI R1,R1,8
4 BNEZ R1,Loop ; salto retardado (delayed branch)
5 SD 8(R1),F4 ; movida cuando se movió la anterior SUBI
Se intercambia BNEZ y SD cambiando la dirección de SD
BUCLE: REORDENACIÓN DEL CÓDIGO
Loop: LD F0,0(R1)
ADDD F4,F0,F2
SUBI R1,R1,8
BNEZ R1,Loop
SD 8(R1),F4
NOP
7
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) —
(Gp:) x
(Gp:) IF
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) x
(Gp:) x
(Gp:) Ex
(Gp:) Wb
(Gp:) IF
(Gp:) IF
(Gp:) ID
(Gp:) ID
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) Ex
(Gp:) M
(Gp:) M
(Gp:) —
(Gp:) x
Ventana de retardo
Se suma 8 para evitar
el decremento en el subi.
(Gp:) IF
Ahorra tres ciclos
1
14
…
BUCLE: REORDENACIÓN DEL CÓDIGO
Re-escribimos el bucle para minimizar las detenciones?
8
1 Loop: LD F0 , 0 (R1)
2 ADDD F4, F0, F2
3 SD 0 (R1), F4 ;eliminado SUBI & BNEZ
4 LD F6, -8 (R1)
5 ADDD F8,F6,F2
6 SD -8 (R1),F8 ;eliminado SUBI & BNEZ
7 LD F10, -16 (R1)
8 ADDD F12, F10, F2
9 SD -16 (R1), F12 ;eliminado SUBI & BNEZ
10 LD F14, -24 (R1)
11 ADDD F16, F14, F2
12 SD -24 (R1), F16
13 SUBI R1, R1, #32 ;modificado a 4*8
14 BNEZ R1, LOOP
15 NOP
15 + 4 x (2+2) = 31 ciclos, o 7.8 por iteración. Asumimos que R1 es múltiplo de 4
DESENRROLLADO DEL BUCLE (4 VECES) (FORMA DIRECTA)
Qué suposiciones se han hecho cuando se ha movido el código?
OK a mover stores después de SUBI incluso si el registro cambia
OK a mover loads antes de stores: obtienen los datos adecuados?
Cúando es seguro para el compilador hacer estos cambios?
9
1 Loop: LD F0,0(R1)
2 LD F6,-8(R1)
3 LD F10,-16(R1)
4 LD F14,-24(R1)
5 ADDD F4,F0,F2
6 ADDD F8,F6,F2
7 ADDD F12,F10,F2
8 ADDD F16,F14,F2
9 SD 0(R1),F4
10 SD -8(R1),F8
11 SD -16(R1),F12
12 SUBI R1,R1,#32
13 BNEZ R1,LOOP
14 SD 8 (R1),F16 ; 8-32 = -24
16 ciclos de reloj, o 4 por iteración
Cúando es seguro mover instrucciones?
DESENRROLLADO DEL BUCLE QUE MINIMIZA LAS DETENCIONES
DESENRROLLADO DEL BUCLE QUE MINIMIZA LAS DETENCIONES
10
1 Loop: LD F0,0(R1)
2 LD F6,-8(R1)
3 LD F10,-16(R1)
4 LD F14,-24(R1)
5 ADDD F4,F0,F2
6 ADDD F8,F6,F2
7 ADDD F12,F10,F2
8 ADDD F16,F14,F2
9 SD 0(R1),F4
10 SD -8(R1),F8
11 SD -16(R1),F12
12 SUBI R1,R1,#32
13 BNEZ R1,LOOP
14 SD 8 (R1),F16 ; 8-32 = -24
(Gp:) IF
(Gp:) x
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb-
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) Wb
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) M
(Gp:) IF
(Gp:) ID
(Gp:) Ex
(Gp:) x
(Gp:) Wb
(Gp:) M
(Gp:) Wb
Página siguiente  |