Descargar

La optimización de código

Enviado por Pablo Turmero

Partes: 1, 2

    edu.red 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

    edu.red 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)

    edu.red 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

    edu.red 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?

    edu.red 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?

    edu.red 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

    edu.red 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

    edu.red 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)

    edu.red 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

    edu.red 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

    Partes: 1, 2
    Página siguiente