Capítulo 6
Hazards
1998 Morgan Kaufmann Publishers
Ch6c-1
Dependências de Dados
•
Problema: iniciar uma instrução antes da anterior ter finalizado
• dependências que “voltam no tempo” são hazards de dados
• qual instrução receberá o valor errado de $2 (velho 10, novo -20)
Time (in clock cycles)
CC 1
Value of
register $2: 10
Program
execution
order
(in instructions)
sub $2, $1, $3
and $12, $2, $5
or $13, $6, $2
add $14, $2, $2
sw $15, 100($2)
IM
CC 2
CC 3
CC 4
CC 5
CC 6
CC 7
CC 8
CC 9
10
10
10
10/– 20
– 20
– 20
– 20
– 20
DM
Reg
Reg
IM
DM
Reg
IM
DM
Reg
IM
Reg
DM
Reg
IM
Reg
Reg
1998 Morgan Kaufmann Publishers
Reg
DM
Reg
Ch6c-2
Erro devido à dependência de dados
sub
and
or
add
sw
$2, $1, $3
$12, $2, $5
$13, $6, $2
$14, $2, $2
$15, 100($2)
• and e or lêem resultado errado (velho 10)
• store está claramente à direita (depois no tempo) e lê resultado
certo (-20)
• hazard no add pode ser evitado se a escrita no banco de
registradores for feita (em CC5) na metade do ciclo (borda de
descida)
Reg WR
CC4
Reg RD
CC5
1998 Morgan Kaufmann Publishers
CC6
Ch6c-3
Solução de software
•
•
•
O compilador deve garantir a ausência de hazards: inserção de nops
Onde inserir os “nops” ?
Quantos?
sub
and
or
add
sw
•
$2, $1, $3
$12, $2, $5
$13, $6, $2
$14, $2, $2
$15, 100($2)
Problema: essa abordagem afeta o desempenho!
1998 Morgan Kaufmann Publishers
Ch6c-4
Forwarding (algumas vezes: bypassing)
•
Usar resultados temporários
• Não esperar que os resultados sejam escritos no banco de registradores
– Unidade de forwarding para manipular leitura/escrita para um mesmo
registrador
Time (in clock cycles)
– ULA forwarding
CC 1
CC 2
CC 3
CC 4
CC 5
CC 6
CC 7
CC 8
CC 9
Value of register $2 : 10
Value of EX/MEM : X
Value of MEM/WB : X
10
X
X
10
X
X
10
– 20
X
10/– 20
X
– 20
DM
Reg
– 20
X
X
– 20
X
X
– 20
X
X
– 20
X
X
Program
execution order
(in instructions)
sub $2, $1, $3
and $12, $2, $5
or $13, $6, $2
add $14, $2, $2
sw $15, 100($2)
IM
Reg
IM
Reg
IM
DM
Reg
IM
Reg
DM
Reg
IM
E se esse $2 fosse $13?
1998 Morgan Kaufmann Publishers
Reg
DM
Reg
Reg
DM
Reg
Ch6c-5
Forwarding
ID/EX
Control
PC
Instruction
memory
Instruction
IF/ID
WB
EX/MEM
M
WB
MEM/WB
EX
M
WB
M
u
x
Registers
ALU
Data
memory
M
u
x
M
u
x
IF/ID.RegisterRs
IF/ID.RegisterRt
IF/ID.RegisterRt
Rs
Rt
Rt
IF/ID.RegisterRd
Rd
M
u
x
EX/MEM.RegisterRd
Forwarding
unit
1998 Morgan Kaufmann Publishers
MEM/WB.RegisterRd
Ch6c-6
Forward não é válido para todos os casos
•
Load (lw) ainda pode causar um hazard
– Uma instrução, após um load, tenta ler um registrador que é o
alvo (destino) do load
Time (in clock cycles)
Program
CC1
CC2
execution
order
(in instructions)
Reg
lw$2, 20($1) IM
and $4, $2, $5
–
or $8, $2, $6
add $9, $4, $2
slt $1, $6, $7
•
IM
CC3
CC4
CC5
DM
Reg
Reg
IM
DM
Reg
IM
CC6
CC 8
CC9
Reg
DM
Reg
IM
CC7
Reg
DM
Reg
Reg
DM
Reg
Uma unidade de detecção de hazard é necessária para travar (stall) a
instrução de load
1998 Morgan Kaufmann Publishers
Ch6c-7
Stalling
•
A idéia de stall consiste em “congelar” instruções em seus
respectivos estágios
Program
Time (in clock cycles)
execution
CC 1
CC 2
order
(in instructions)
lw $2, 20($1)
and $4, $2, $5
or $8, $2, $6
IM
CC 3
Reg
IM
Reg
IM
CC 4
CC 5
DM
Reg
Reg
IM
CC 6
CC 7
DM
Reg
Reg
DM
CC 8
CC 9
CC 10
Reg
bubble
add $9, $4, $2
slt $1, $6, $7
IM
DM
Reg
IM
Reg
1998 Morgan Kaufmann Publishers
Reg
DM
Reg
Ch6c-8
Unidade de detecção de hazards
ID/EX.MemRead
IF/IDWrite
Hazard
detection
unit
ID/EX
Control
0
M
u
x
PC
Instruction
memory
Instruction
PCWrite
IF/ID
WB
EX/MEM
M
WB
MEM/WB
EX
M
WB
M
u
x
Registers
ALU
Data
memory
M
u
x
IF/ID.RegisterRs
IF/ID.RegisterRt
IF/ID.RegisterRt
IF/ID.RegisterRd
ID/EX.RegisterRt
Rt
Rd
Rs
Rt
M
u
x
M
u
x
EX/MEM.RegisterRd
Forwarding
unit
1998 Morgan Kaufmann Publishers
MEM/WB.RegisterRd
Ch6c-9
a n d $ 4, $2 , $ 5
lw $ 2 , 20 ($ 1 )
1
X
IF/IDWrite
Exemplo
pag 493
b efo re < 1 >
Hazard
detection
unit
ID/EX.MemRead
ID/EX
11
WB
Control
0
M
u
x
PCWrite
IF/ID
PC
Instruction
1
Instruction
memory
b efo re < 2>
b e fo re <3 >
EX/MEM
M
WB
MEM/WB
EX
M
WB
$1
M
u
x
X
Registers
Data
memory
ALU
$X
M
u
x
M
u
x
1
X
2
M
u
x
ID/EX.RegisterRt
Forwarding
unit
C l oc k 2
o r $ 4, $4 , $ 2
lw $ 2 , 2 0 ($ 1 )
a nd $4 , $ 2, $ 5
Hazard
detection
unit
IF/IDWrite
2
5
ID/EX.MemRead
ID/EX
11
00
WB
Control
0
M
u
x
PCWrite
IF/ID
PC
$2
Instruction
2
Instruction
memory
b e fore < 1 >
EX/MEM
M
WB
MEM/WB
EX
M
WB
$1
M
u
x
5
Registers
$5
ALU
$X
M
u
x
2
5
4
ID/EX.RegisterRt
C l oc k 3
be fore < 2>
1
X
2
M
u
x
Forwarding
unit
Data
memory
M
u
x
or $ 4 , $ 4, $2
a nd $ 4, $2 , $ 5
2
5
Control
0
M
u
x
PCWrite
IF/ID
PC
Instruction
2
Instruction
memory
lw $ 2 , . . .
ID/EX.MemRead
ID/EX
10
00
WB
IF/IDWrite
Exemplo
pag 493
bu b b le
Hazard
detection
unit
EX/MEM
M
WB
EX
M
$2
b e fo re < 1>
11
MEM/WB
WB
$2
M
u
x
5
Registers
$5
Data
memory
ALU
$5
M
u
x
M
u
x
2
5
2
5
4
4
2
M
u
x
ID/EX.RegisterRt
Forwarding
unit
C lo ck 4
a d d $ 9, $ 4 , $ 2
o r $ 4, $4 , $ 2
an d $ 4, $2 , $ 5
Hazard
detection
unit
ID/EX.MemRead
ID/EX
10
10
WB
IF/IDWrite
4
2
Control
0
M
u
x
PCWrite
IF/ID
PC
Instruction
4
Instruction
memory
b u b ble
$4
lw $2 , . . .
M
EX/MEM
0
WB
MEM/WB
EX
M
WB
11
$2
M
u
x
2
2
Registers
ALU
$2
$5
Data
memory
M
u
x
M
u
x
ID/EX.RegisterRt
C lo ck 5
4
2
2
5
4
4
M
u
x
2
Forwarding
unit
Hazards de desvio
•
Quando o desvio é decidido, outras instruções estão no pipeline
Time (in clock cycles)
Program
execution
CC 1
CC2
order
(in instructions)
40 beq $1, $3, 7
44 and $12, $2, $5
48 or $13, $6, $2
52 add $14, $2, $2
72 lw $4, 50($7)
•
•
IM
CC 3
Reg
IM
CC 4
CC 5
DM
Reg
Reg
IM
DM
Reg
IM
CC 6
CC 8
CC 9
Reg
DM
Reg
IM
CC 7
Reg
DM
Reg
Reg
DM
Reg
Nesse caso, considera-se que o desvio não será tomado (branch not
taken) uma vez que o stall afeta o desempenho consideravelmente
É necessário mais um hardware para limpar (flush) as instruções,
caso elas não sejam as instruções corretas (alvos do desvio)
Ch6c-12
1998 Morgan Kaufmann Publishers
Diminuindo a penalidade do “branch taken”
•
•
•
no esquema anterior
– decisão só é tomada no estágio MEM
– caso “branch taken” é necessário limpar (flush) os estágios IF, ID
e EX
– 3 ciclos de clock perdidos
para diminuir a penalidade:
– antecipar a decisão do estágio MEM para o estágio ID
– economia de dois ciclos clocks
– Limpar somente instrução sendo lida da memória (fetched)
mudanças no hardware:
– cálculo do endereço do desvio (PC + offset<<2)
– comparação dos registradores
• 32 XORs com or na saída
• mais rápido do que a ALU
1998 Morgan Kaufmann Publishers
Ch6c-13
Limpando instruções
IF.Flush
Hazard
detection
unit
ID/EX
M
u
x
Control
0
M
u
x
IF/ID
4
EX/MEM
M
WB
MEM/WB
EX
M
WB
Shift
left 2
=
PC
WB
M
u
x
Registers
Instruction
memory
ALU
Data
memory
M
u
x
M
u
x
Sign
extend
M
u
x
Forwarding
unit
1998 Morgan Kaufmann Publishers
Ch6c-14
and $12, $2, $5
beq $1, $3, 7
sub $10, $4, $8
before<1>
before<2>
IF.Flush
Hazard
detection
unit
72
48
ID /EX
M
u
x
WB
Control
Funcionamento do
branch taken com
mudança na decisão
28
0
M
u
x
IF/ID
48
44
EX/MEM
M
WB
EX
M
MEM/WB
WB
72
4
$1
Shift
left 2
Registers
72
PC
In struc tion
memory
44
M
u
x
=
$4
Data
memory
ALU
$3
M
u
x
7
MEM -->ID
M
u
x
$8
Sign
extend
(fig 6.52)
10
Forwarding
unit
Clock 3
lw $4, 50($7)
bubble(nop)
beq $1, $3, 7
sub $10, . . .
before<1>
IF.Flush
40 beq $1, $3, 7
Hazard
detection
unit
ID /EX
76
M
u
x
WB
M
u
x
Control
44 and $12, $2, $5
EX/MEM
M
WB
EX
M
MEM/WB
0
IF/ID
76
WB
72
4
Shift
left 2
48 or $13, $6, $2
Registers
PC
76
72
=
M
u
x
In struc tion
memory
Data
memory
ALU
M
u
x
52 add $14, $2, $2
$1
$3
Sign
extend
10
72 lw $4, 50($7)
Forwarding
unit
Clock 4
M
u
x
Melhorando o desempenho...
•
Tente evitar os stalls! Ex: reordene as instruções a seguir:
lw
lw
sw
sw
•
•
•
$t0,
$t2,
$t2,
$t0,
0($t1)
4($t1)
0($t1)
4($t1)
Adicione um slot de atraso do desvio “branch delay slot”
– A próxima instrução depois do desvio é sempre executada
– Depende do compilador preencher “fill” o slot com alguma
instrução útil
Previsão de desvios (Branch Prediction)
– tentar acertar se o desvio será tomado ou não
– em loops, desvio é tomado a maior parte das vezes
– Necessidade de uma branch history table
Em máquinas superscalarers: mais de uma instrução é iniciada no
mesmo ciclo
1998 Morgan Kaufmann Publishers
Ch6c-16
Delay slot
a. From before
add $s1, $s2, $s3
if $s2 = 0 then
Delay slot
b. From target
sub $t4, $t5, $t6
…
c. From fall through
add $s1, $s2, $s3
if $s1 = 0 then
add $s1, $s2, $s3
Delay slot
if $s1 = 0 then
Delay slot
Becomes
Becomes
sub $t4, $t5, $t6
Becomes
add $s1, $s2, $s3
if $s1 = 0 then
if $s2 = 0 then
add $s1, $s2, $s3
sub $t4, $t5, $t6
add $s1, $s2, $s3
if $s1 = 0 then
sub $t4, $t5, $t6
1998 Morgan Kaufmann Publishers
Ch6c-17
Escalonamento Dinâmico
•
O hardware realiza o escalonamento (“scheduling”)
– Hardware tenta encontrar instruções para executar
– Execução fora-de-ordem é possível
– Execução especulativa e previsão dinâmica de desvios
– TODOS os processadores modernos possuem algum(ns) desse(s)
recurso(s) e, por isso, são bastante complicados!
– DEC Alpha 21264: 9 estágios de pipeline, 6 instruções podem ser
despachadas simultaneamente
– PowerPC e Pentium: possuem uma branch history table
– A tecnologia existente no compilador está cada vez mais importante
1998 Morgan Kaufmann Publishers
Ch6c-18
Comparação de desempenho
•
•
•
•
para monociclo, multiciclo e pipeline
gcc: lw (23%), sw (13%), beq (19%), j (2%), resto (43%)
pipeline:
– 2ns (memória e ALU) e 1ns para o registrador (RD ou WR)
– 1/2 dos lw seguidos por instruções que usam o resultado
– 1/4 dos beq são errados (1 clock perdido)
– jumps perdem um ciclo
pipeline:
– lw: 1 clock sem hazard e 2 clock com hazard; média = 1.5
– beq: 1 clock se OK (3/4) e 2 clocks se não OK (1/4); média = 1.25
– jump: 2 clocks
– demais instruções: 1 clock
•
•
•
•
CPI = 1.5*0.23+1*0.13+1*0.43+1.25*0.19+2*0.02 = 1.18
clock = 2ns; tempo médio de execução = 2*1.18=2.36ns
multiciclo; 4.02*2=8.08ns; monociclo = 8ns
pipeline é 3.4 vezes mais rápido do que monociclo ou multiciclo
1998 Morgan Kaufmann Publishers
Ch6c-19
Circuito completo
Branch
IF.Flush
EX.Flush
ID.Flush
Hazard
detection
unit
WB
Control
IF/ID
4
Instruction
memory
PC
Address
Read
data
Instruction
Shift
left 2
0
0
16 Sign
extend
Except
PC
=
ALUSrc
WB
Data
memory
ALU
M
u
x
MEM/WB
M
M
u
x
32
Instruction [25– 21]
Instruction [20– 16]
Instruction [20– 16]
Instruction [15– 11]
WB
Cause
EX
Read
Read
register 1data 1
Read
register 2
Registers
Write
register Read
data 2
Write
data
EX/MEM
M
u
x
M
RegWrite
0
M
u
x
M
u
x
M
u
x
ALU
control
ALUOp
RegDst
M
u
x
Forwarding
unit
Address
Read
data
Write
data
MemRead
MemtoReg
ID/EX
M
u
x
MemWrite
40000040
M
u
x