El compilador se ve afectado por las dependencias en el programa, incluso si un riesgo HW no depende de un cauce dado Planificar el código evita riesgos Dependencias de datos (verdadera) (RAW, si hay un riesgo por recursos HW) Instrucción i produce un resultado usado por la instrucción j, o Instrucción j depende de datos de la instrucción k, y la instrucción k depende de un dato de la instrucción i. Si son dependientes, no pueden ejecutarse en paralelo Fácil de determinar para los registros (nombres fijos) Difícil en el caso de la memoria: Son iguales 100(R4) = 20(R6)? En iteraciones diferentes de un bucle, son iguales 20(R6) = 20(R6)? Se requiere que el compilador conozca que si R1 no cambia entonces: 0(R1) ? -8(R1) ? -16(R1) ? -24(R1) 11 PUNTO DE VISTA DEL COMPILADOR RESPECTO A LA REORDENACIÓN DEL CÓDIGO
Otro tipo de dependencia denominado dependencia de nombre: dos instrucciones que usan el mismo nombre (registro o dirección de memoria) pero que no intercambian datos Antidependencia (WAR, si hay un riesgo por HW) La instrucción j escribe en un registro o posición de memoria de la que otra instrucción i lee y la instrucción i se ejecuta primero Dependencia de Salida (WAW, si hay un riesgo por HW ) La instrucción i y la instrucción j escriben en el mismo registro o posición de memoria; el orden de las instrucciones debe de ser conservado. 12 PUNTO DE VISTA DEL COMPILADOR RESPECTO A LA REORDENACIÓN DEL CÓDIGO
13 1 Loop: LD F0, 0 (R1) 2 ADDD F4, F0, F2 3 SD 0 (R1), F4 ;eliminadas SUBI & BNEZ 4 LD F0, -8 (R1) 2 ADDD F4, F0, F2 3 SD -8 (R1) ,F4 ;eliminadas SUBI & BNEZ 7 LD F0, -16 (R1) 8 ADDD F4, F0, F2 9 SD -16 (R1), F4 ;eliminadas SUBI & BNEZ 10 LD F0, -24 (R1) 11 ADDD F4, F0, F2 12 SD -24 (R1), F4 13 SUBI R1, R1, #32 ;cambiado a 4*8 14 BNEZ R1, LOOP 15 NOP Cómo eliminarlas? DÓNDE ESTÁN LAS DEPENDENCIAS DE NOMBRE?
14 1 Loop: LD F0, 0 (R1) 2 ADDD F4, F0, F2 3 SD 0 (R1), F4 ;eliminadas SUBI & BNEZ 4 LD F6, -8 (R1) 5 ADDD F8, F6, F2 6 SD -8 (R1), F8 ; eliminadas SUBI & BNEZ 7 LD F10, -16 (R1) 8 ADDD F12, F10, F2 9 SD -16 (R1), F12 ; eliminadas SUBI & BNEZ 10 LD F14, -24 (R1) 11 ADDD F16, F14, F2 12 SD -24 (R1), F16 13 SUBI R1, R1, #32 ;cambiado a 4*8 14 BNEZ R1, LOOP 15 NOP
Haciendo un “renombrado de registros” ( “register renaming”) DÓNDE ESTÁN LAS DEPENDENCIAS DE NOMBRE?
Ejemplo: Dónde están las dependencias de datos? (A,B,C distintas y no se solapan) for (i=1; i<=100; i=i+1) { A[i] = A[i-1] + C[i-1]; /* S1 */ B[i] = B[i-1] + A[i];} /* S2 */ S1 utiliza un valor calculado por S1 en una iteración anterior, dado que la iteración i calcula A[i] el cual es leído en la iteración i+1(A[i-1]). Lo mismo le ocurre a S2 para B[i] y B[i-1]. Esto es una dependencia acarreada (loop-carried dependence): entre iteraciones Esto implica que las iteraciones son dependientes, y no pueden ser ejecutadas en paralelo No es el caso del ejemplo anterior: cada iteración era independiente Por otro lado S2 utiliza el valor A[i] calculado por S1 en la misma iteración. No es acarreada Se pueden ejecutar en paralelo varias iteraciones del bucle siempre que las dos instrucciones se ejecuten juntas 15 DEPENDENCIAS ACARREADAS
Verificar si se puede mover S.D después de DSUBI y BNEZ, y encontrar la cantidad para ajustar el offset del S.D Determinar si el desenrollado del bucle será útil: se determina qué iteraciones del bucle son independientes Renombrar los registros para evitar dependencias de nombre Eliminar los tests extras e instrucciones de salto, y ajustar la terminación del bucle y el código que se itera Determinar los loads y stores en el bucle desenrollado que pueden ser intercambiados, para lo que se observa qué loads y stores de diferentes iteraciones son independientes requiere analizar las direcciones de memoria y buscar para que no haya referencias a la misma dirección de memoria. Planificar el código, preservando cualquier dependencia que sea necesaria para obtener el mismo resultado que el código original 16 PASOS DEL COMPILADOR PARA DESENRROLLAR
17 Ejemplo if p1 {S1;}; if p2 {S2;}; S1 es dependiente de control respecto a p1 S2 es dependiente de control respecto a p2 pero no respecto a p1.
Dos restricciones (obvias) en las dependencias de control: Una instrucción que es dependiente de control respecto a un branch no puede moverse antes (fuera) del branch para que su ejecución no este controlada por el branch. Una instrucción que no es dependiente de control respecto a un branch no puede ser movida después (dentro) del branch ya que su ejecución entonces es controlada por el branch. DEPENDENCIAS DE CONTROL
Observación: si las iteraciones de los bucles son independientes, entonces es posible conseguir un mayor ILP tomando instrucciones de diferentes iteraciones Software pipelining: reorganiza los bucles de forma que cada iteración está formada por instrucciones elegidas de diferentes iteraciones del bucle original (~ Tomasulo in SW) 18 OTRA POSIBILIDAD: SOFTWARE PIPELINING
19 Desenrollado simbólico del bucle Maximiza resultado Código más pequeño que con desenrollado convencional Llena y vacía el cauce sólo una vez por bucle, en vez de una vez por iteración desenrollada en el caso de desenrollado del bucle SOFTWARE PIPELINING
20 Partimos de un código ensamblador con dependencias de flujo
ADDI R6, R0, #40 Loop: ADD R1, R2, R3 SUBI R4, R1, R0 SD R4, 0(R6) SUBI R6, R6, #8 BNEZ R6, loop SOFTWARE PIPELINING: EJEMPLO 1
21 Primero identificamos qué instrucciones se van a repetir (como al desenrollar) Estas instrucciones se tienen que ejecutar secuencialmente por las dependencias
ADDI R6, R0, #40 Loop: ADD R1, R2, R3 SUBI R4, R1, R0 SD R4, 0(R6) SUBI R6, R6, #8 BNEZ R6, loop SOFTWARE PIPELINING: EJEMPLO 1
22 Es posible simular una segmentación a nivel software, dado que no existe dependencia entre instrucciones de distintas iteraciones
SOFTWARE PIPELINING: EJEMPLO 1
23 De aquí podemos sacar un nuevo patrón de instrucciones que se repiten, aparte de un prólogo y epílogo.
SOFTWARE PIPELINING: EJEMPLO 1
24 Nuevamente podemos reordenar el código, aún sin ser un bucle ADD R1, R2, R3 SUBI R4, R1, R0 ADD R1, R2, R3
SD R4, 0(R6) SUBI R4, R1, R0 ADD R1, R2, R3
SD R4, -8(R6) SUBI R4, R1, R0 SD R4, -16(R6) SOFTWARE PIPELINING: EJEMPLO 1
25 Si añadimos el bucle, quedaría así (cuidado con los índices en los accesos a memoria) ADDI R6, R0, #40 ADD R1, R2, R3 SUBI R4, R1, R0 ADD R1, R2, R3 loop: SD R4, 0(R6) SUBI R4, R1, R0 ADD R1, R2, R3 SUBI R6, R6, #8 BNEZ R6, loop SD R4, -8(R6) SUBI R4, R1, R0 SD R4, -16(R6) SOFTWARE PIPELINING: EJEMPLO 1
Antes: Desenrollando 3 veces 1 L.D F0,0(R1) 2 ADD.D F4,F0,F2 3 S.D 0(R1),F4 4 L.D F6,-8(R1) 5 ADD.D F8,F6,F2 6 S.D -8(R1),F8 7 L.D F10,-16(R1) 8 ADD.D F12,F10,F2 9 S.D -16(R1),F12 10 DSUBUI R1,R1,#24 11 BNEZ R1,LOOP 26 Después: Software Pipelined
1 S.D 0(R1),F4 ; Stores X[i] 2 ADD.D F4,F0,F2 ; Adds to X[i-1] 3 L.D F0,-16(R1); Loads X[i-2] 4 DSUBUI R1,R1,#8 5 BNEZ R1,LOOP 5 cycles per iteration SOFTWARE PIPELINING : EJEMPLO 2
Falta el código de comienzo y finalización (start-up & finish-up code) Comienzo: instrucciones que corresponden a las iteraciones 1 y 2 que no se han ejecutado L.D iteraciones 1 y 2 ADD.D iteración 1 Finalización: instrucciones que corresponden a las dos últimas iteraciones que no se han ejecutado ADD.D última iteración S.D dos últimas iteraciones 27 SOFTWARE PIPELINING : EJEMPLO
Por qué en HW y en run time? Porque funciona bien cuando no se conocen las dependencias reales en tiempo de compilación El compilador es más simple El código para una máquina funciona bien en otra Idea clave: permitir que instrucciones situadas después de una detención prosigan su ejecución DIVD F0,F2,F4 ADDD F10,F0,F8 SUBD F12,F8,F14 Permitir la ejecución out-of-order execution => finalización out-of-order Aparece en el Scoreboard de la máquina CDC 6600 en 1963 28 ESQUEMAS HW: PARALELISMO DE INSTRUCCIÓN
| Página siguiente |