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 anterior | Volver al principio del trabajo | Página siguiente  |