31 RIESGO PROVOCADO POR UN SALTO CONDICIONAL: CICLO 3
32 RIESGO PROVOCADO POR UN SALTO CONDICIONAL: CICLO 4
33 RIESGO PROVOCADO POR UN SALTO CONDICIONAL: CICLO 5
34 RIESGO PROVOCADO POR UN SALTO CONDICIONAL: CICLO 6
35 RIESGO PROVOCADO POR UN SALTO CONDICIONAL: CICLO 7
IMPACTO DE UN SALTO EN LAS DETENCIONES Si el número de instr de salto es un 30%, detener 2 o 3 ciclos en cada uno tiene un impacto significativo en las prestaciones
La solución tiene dos partes: Determinar si el salto debe o no efectuarse tan pronto como sea posible , y Calcular la dirección efectiva de salto antes 36
Se produce debido a que la dirección objetivo del salto (branch y jmp) y la condición de salto (branch) se calulan en la fase Ex de la arquitectura DLX, y se reemplaza el PC en la fase MEM. Es posible reducir el tamaño de la ventana de retardo. Para ello es necesario calcular la dirección efectiva de salto y evaluar la condición de salto lo antes posible. Esto implica modificar el diseño de la arquitectura del cauce. MIPS: Solución utilizada: Mover el test de Zero a la etapa ID/RF Situar el sumador para calcular el nuevo PC en la etapa ID/RF Se consigue 1 ciclo de reloj de penalización en los saltos en vez de 2 o 3 37 RIESGOS DE CONTROL: REDUCCIÓN DE LA VENTANA DE RETARDO
ESQUEMA MODIFICADO 38 (Gp:) Memory Access (Gp:) Write Back (Gp:) Instruction Fetch (Gp:) Instr. Decode Reg. Fetch (Gp:) Execute Addr. Calc (Gp:) ALU (Gp:) MUX (Gp:) Instr. Memory (Gp:) Reg File (Gp:) MUX (Gp:) Data Memory (Gp:) MUX (Gp:) Sign Extend (Gp:) 4 (Gp:) Add (Gp:) Zero? (Gp:) PC (Gp:) WB Data (Gp:) Rs1 (Gp:) Rs2 (Gp:) Imm (Gp:) PC (Gp:) Instr (Gp:) PC (Gp:) PC (Gp:) PC (Gp:) AOR (Gp:) SVR (Gp:) ImR (Gp:) AIR 2 (Gp:) AIR 1 (Gp:) CR (Gp:) ARR (Gp:) LMDR (Gp:) RD (Gp:) RD (Gp:) RD (Gp:) Rd (Gp:) Add
Aunque sabemos que en estos tipos de instrucciones tenemos que cambiar el PC, aún es necesario un delay slot (ventana de retardo de 1 ciclo) ya que: Descodificación de la instrucción Cálculo del PC Básicamente, es una decisión que hay que realizar, lo cual toma su tiempo. Esto sugiere un único delay slot: Es decir la siguiente instrucción después de un salto incondicional se ejecuta siempre. 39 JUMPS AND CALLS (JAL) (SALTOS INCONDICIONALES)
RIESGOS DE CONTROL: SOLUCIONES Un rediseño de cauce, como el que se ha comentado antes reduce el retardo a un ciclo, pero puede producir nuevos riesgos. Son necesarias técnicas específicas: Hardware: una es el interbloqueo. utilizar una cache predescodificada. predicción dinámica de salto (a esta le dedicaremos un tema entero por lo que no lo veremos aquí). Software: la técnica de saltos retardados. predicción estática de saltos (dirigida por el compilador). 40
El Hw interbloquea la siguiente instrucción a ejecutar ? hasta que se calcula la dirección efectiva y el sentido del salto. 41 SOLUCIONES HARDWARE A RIESGOS DE CONTROL: INTERBLOQUEO
Que es lo que realmente hay que hacer en run time? Una vez que se ha detectado que una instr es un jump o JAL, es posible recodificarla en la cache interna. Esto es una forma muy limitada de compilación dinámica
Uso de una cache de instr “Pre-descodificadas” Llamado “branch folding” en el CRISP processor de los Bell-Labs. Nota: el JAL introduce un riesgo estructural sobre las escrituras 42 (Gp:) and r3,r1,r5 addi r2,r3,#4 sub r4,r2,r1 jal doit subi r1,r1,#1 (Gp:) A: (Gp:) doit (Gp:) addi r2,r3,#4 (Gp:) A+8 (Gp:) N (Gp:) sub r4,r2,r1 (Gp:) L (Gp:) — (Gp:) — (Gp:) — (Gp:) and r3,r1,r5 (Gp:) A+4 (Gp:) N (Gp:) subi r1,r1,#1 (Gp:) A+20 (Gp:) N (Gp:) Internal Cache state:
COMO CONSEGUIR UN JUMP CON “RETARDO CERO”
43 SOLUCIONES SOFTWARE RIESGOS DE CONTROL:ESQUEMA MODIFICADO (CACHE PREDESCODIFICADA) (Gp:) Memory Access (Gp:) Write Back (Gp:) Instruction Fetch (Gp:) Instr. Decode Reg. Fetch (Gp:) Execute Addr. Calc (Gp:) ALU (Gp:) Reg File (Gp:) MUX (Gp:) MUX (Gp:) Data Memory (Gp:) MUX (Gp:) Sign Extend (Gp:) Branch? (Gp:) RD (Gp:) RD (Gp:) RD (Gp:) WB Data (Gp:) RS2 (Gp:) Imm (Gp:) MUX (Gp:) ID/EX (Gp:) MEM/WB (Gp:) EX/MEM (Gp:) IF/ID (Gp:) Adder (Gp:) RS1 (Gp:) Return PC (Addr + 4) (Gp:) Imm (Gp:) Opcode (Gp:) Decoded Cache (Gp:) Address
Incrementa el ciclo de reloj en no menos de un retardo por el MUX Si embargo introduce un riesgo estructural sobre las escrituras debido al JAL
Se elimina el delay slot (bueno) El branch ha sido solapado con la instrucción sub (bueno). Incrementa el tamaño de la cache de instrucciones (no tan bueno) Requiere otro puerto de lectura en el banco de registros (MALO) Dobla potencialmente el periodo de reloj (REALMENTE MALO) 44 (Gp:) and r3,r1,r5 addi r2,r3,#4 sub r4,r2,r1 bne r4,loop subi r1,r1,#1 (Gp:) Internal Cache state: (Gp:) A: (Gp:) sub r4,r2,r1 (Gp:) addi r2,r3,#4 (Gp:) sub r4,r2,r1 (Gp:) — (Gp:) and r3,r1,r5 (Gp:) subi r1,r1,#1 (Gp:) N (Gp:) BnR4 (Gp:) — (Gp:) N (Gp:) N (Gp:) A+16 (Gp:) A+8 (Gp:) — (Gp:) A+4 (Gp:) A+20 (Gp:) N/A (Gp:) loop (Gp:) — (Gp:) N/A (Gp:) N/A (Gp:) Next (Gp:) Branch (Gp:) A+16:
POR QUÉ NO USARLO CON LOS SALTOS CONDICIONALES?
45 Puede doblar el periodo de reloj – debe acceder a la cache y a los reg ESQUEMA MODIFICADO (Gp:) Memory Access (Gp:) Write Back (Gp:) Instruction Fetch (Gp:) “Instr. Decode Reg. Fetch” (Gp:) Execute Addr. Calc (Gp:) ALU (Gp:) MUX (Gp:) MUX (Gp:) Data Memory (Gp:) MUX (Gp:) Sign Extend (Gp:) Branch? (Gp:) RD (Gp:) RD (Gp:) RD (Gp:) WB Data (Gp:) RS2 (Gp:) Imm (Gp:) MUX (Gp:) ID/EX (Gp:) MEM/WB (Gp:) EX/MEM (Gp:) IF/ID (Gp:) RS1 (Gp:) Return PC (Addr + 4) (Gp:) Decoded Cache (Gp:) Address (Gp:) Next PC (Gp:) Branch PC (Gp:) Reg File (Gp:)
TEMPORIZACIÓN 46 El tiempo de acceso al banco de registros debe ser cercano al periodo de reloj original (Gp:) Instruction Cache Access
(Gp:) Branch Register Lookup
(Gp:) Mux
Clock: Ready to latch new PC Comienzo de If
Esto causa que la siguiente instrucción se busque inmediatamente en los destinos de los saltos (predict taken) Si el salto finalmente no es realizado, entonces se elimina la instrucción de destino y se continua por la dirección A+16 47 (Gp:) and r3,r1,r5 addi r2,r3,#4 sub r4,r2,r1 bne r4,loop subi r1,r1,#1 (Gp:) Internal Cache state: (Gp:) A: (Gp:) sub r4,r2,r1 (Gp:) addi r2,r3,#4 (Gp:) sub r4,r2,r1 (Gp:) bne r4 (Gp:) and r3,r1,r5 (Gp:) subi r1,r1,#1 (Gp:) N (Gp:) N (Gp:) N (Gp:) N (Gp:) N (Gp:) A+12 (Gp:) A+8 (Gp:) loop (Gp:) A+4 (Gp:) A+20 (Gp:) Next (Gp:) A+16:
SIN EMBARGO, PODEMOS USAR LA PRIMERA TÉCNICA PARA REFLEJAR PREDICCIONES Y ELIMINAR DELAY SLOTS
SOLUCIONES SOFTWARE RIESGOS DE CONTROL:TÉCNICA DE SALTOS RETARDADOS Idea básica: El compilador rellena el delay slot con instrucciones que no tengan dependencias con la de salto, y que estén situadas antes del jump o branch (según orden de programa). Si no hay suficientes instrucciones para mover al delay slot este se rellena con instrucciones no-op. Estas instrucciones se ejecutarán siempre. Se usó por vez primera en las primeras generaciones de proc RISC escalares: IBM 801, Berkeley RISC I y el MIPS de Stanford. Observación: La probabilidad de encontrar una instrucción que mover a la ventana de retardo es 0.6. La probabilidad de encontrar 2 instrucción es 0.2. La probabilidad de encontrar 3 instrucción es 0.1 . 48
Bucle sin usar salto retardado Existen instrucciones independientes que no afectan a la de salto. 49 SALTO RETARDADO: EJEMPLO ld f2, -8(r1) ld f4, 0(r1) multd f8, f0, f2 sd 0(r2), f8 addi r2, r2, 8 addi r1, r1, 8 slt r4, r4, r3 bnez r4, loop yyy1 (Gp:) IF (Gp:) ID (Gp:) Ex (Gp:) M (Gp:) Wb
Escritura: f2 Escritura: f4 Escritura: f8 F8 Mem (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
M (Gp:) x (Gp:) IF (Gp:) ID (Gp:) Ex (Gp:) M (Gp:) Wb
(Gp:) x
IF Ex – (Gp:) x
ID IF ID M (Gp:) x
IF Ex Wb (Gp:) x
ID Escritura: r2 (Gp:) x
(Gp:) x
(Gp:) IF (Gp:) ID (Gp:) Ex (Gp:) M (Gp:) Wb
loop:
Bucle usando la técnica de salto retardado La ventana de retardo se ha completado con instrucciones independientes que no afectan a la de de salto 50 SALTO RETARDADO: EJEMPLO loop: ld f2, -8(r1) ld f4, 0(r1) multd f8, f0, f2 addi r1, r1, 8 slt r4, r4, r3 bnez r4, loop sd 0(r2), f8 addi r2, r2, 8 yyy1 (Gp:) IF (Gp:) ID (Gp:) Ex (Gp:) M (Gp:) Wb
Escritura: f2 Escritura: f4 Escritura: f8 (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
M (Gp:) x (Gp:) IF (Gp:) ID (Gp:) Ex (Gp:) M (Gp:) Wb
Ex (Gp:) M (Gp:) x (Gp:) IF (Gp:) Ex (Gp:) Wb (Gp:) x (Gp:) ID
IF ID (Gp:) IF (Gp:) ID (Gp:) Ex (Gp:) M (Gp:) Wb
(Gp:) IF (Gp:) ID (Gp:) Ex (Gp:) M (Gp:) Wb
Wb
Todos los saltos como tomados. Los saltos “hacia atrás” predecirlos como tomados y los saltos “hacia adelante” predecirlos como no tomados. Hacer una predicción sobre la dirección del salto: La predicción es realizada por el compilador y se incluye en el formato de la instrucción branch. Las instrucciones se comienzan a buscar en la dirección objetiva del salto predicha por este bit. Si la predicción es errónea, las instrucciones que se han comenzado a ejecutar según ese path se eliminan del cauce y se busca en la dirección correcta. La predicción es estática por lo que no puede ser alterada, salvo en la compilación. 51 SOLUCIONES SOFTWARE RIESGOS DE CONTROL:PREDICCIÓN ESTÁTICA DEL SALTO
IDEAS PARA REDUCIR LAS DETENCIONES 52
| Página siguiente |