Hazards de Desvio em Pipelining

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Aula 9: Pipelining (parte 6 – Hazards de desvio)
Professor: Leandro Marzulo
Arquiteturas Avançadas de Computadores
Problema com desvios
Na versão atual, a decisão do desvio não ocorre até o estágio MEM – então quais instruções, se for o caso, devemos inserir no pipe seguindo as instruções de desvio?
Possível solução: causar um stall no pipe até que a decisão do desvio seja conhecida
Ineficiente
Outra solução: prever o resultado do desvio
Ex: Sempre assumir que o desvio não será tomado – continuar com a próxima instrução
Se a previsão estiver errada, devemos fazer um flush no pipe para as instruções que seguiram o branch – descartar as instruções já buscadas ou decodificadas – e continuar a execução da instrução alvo do desvio
2
O atraso de uma previsão incorreta
3
R
e
g
R
e
g
C
C
 
1
T
i
m
e
 
(
i
n
 
c
l
o
c
k
 
c
y
c
l
e
s
)
4
0
 
b
e
q
 
$
1
,
 
$
3
,
 
7
P
r
o
g
r
a
m
e
x
e
c
u
t
i
o
n
o
r
d
e
r
(
i
n
 
i
n
s
t
r
u
c
t
i
o
n
s
)
I
M
R
e
g
I
M
D
M
I
M
D
M
I
M
D
M
D
M
D
M
R
e
g
R
e
g
R
e
g
R
e
g
R
e
g
R
e
g
I
M
4
4
 
a
n
d
 
$
1
2
,
 
$
2
,
 
$
5
4
8
 
o
r
 
$
1
3
,
 
$
6
,
 
$
2
5
2
 
a
d
d
 
$
1
4
,
 
$
2
,
 
$
2
7
2
 
l
w
 
$
4
,
 
5
0
(
$
7
)
C
C
 
2
C
C
 
3
C
C
 
4
C
C
 
5
C
C
 
6
C
C
 
7
C
C
 
8
C
C
 
9
R
e
g
Otimizando o pipe para reduzir o atraso dos desvios
Mover a decisão do desvio do estágio MEM para o estágio ID
O cálculo do endereço de desvio precisa que o somador do endereço seja movido para o estágio ID – as entradas do somador (PC e imediato) já estão disponíveis no registrador IF/ID
O cálculo da decisão do desvio pode ser feita de forma eficiente sem usar a ALU (sem subtração) – basta fazer um XOR dos dois operandos, fazer um OR dos bits do resultado e um NOT no resultado final – eliminando o delay do carry
Podemos então mover este cálculo para o estágio ID sem aumentar significativamente o tamanho do estágio.
Fazer mudanças nas unidades de forwarding e de detecção de hazards para fazer o encaminhamento ou stall do desvio no estágio ID, caso a decisão do desvio dependa de um resultado que está sendo produzido por uma instrução no pipe
4
Flush em caso de previsões incorretas
Mesma estratégia do stall para instruções com dependência de dados com um load…
Zerar todos os sinais de controle (ou a instrução) nos registradores de pipe para as instruções que seguem o branch e que já estão no pipe, tranformando-as em nops
No pipe otimizado, temos que fazer o flush de apenas 1 instrução e a penalidade de uma previsão errada é de apenas 1 ciclo
5
Caminho de dados otimizado
IF.Flush zera a instrução no reg IF/ID
P
C
I
n
s
t
r
u
c
t
i
o
n
m
e
m
o
r
y
4
R
e
g
i
s
t
e
r
s
M
u
x
M
u
x
M
u
x
A
L
U
E
X
M
W
B
M
W
B
W
B
I
D
/
E
X
0
E
X
/
M
E
M
M
E
M
/
W
B
D
a
t
a
m
e
m
o
r
y
M
u
x
H
a
z
a
r
d
d
e
t
e
c
t
i
o
n
u
n
i
t
F
o
r
w
a
r
d
i
n
g
u
n
i
t
I
F
.
F
l
u
s
h
I
F
/
I
D
S
i
g
n
e
x
t
e
n
d
C
o
n
t
r
o
l
M
u
x
=
S
h
i
f
t
l
e
f
t
 
2
M
u
x
6
Exemplo
7
36 sub $10, $4, $8
40 beq $1, $3, 7
44 and $12 $2, $5
48 or $13 $2, $6
52 add $14, $4, $2
56 slt $15, $6, $7
…
72 lw $4, 50($7)
7*4 + 44 = 72
Exemplo
8
P
C
I
n
s
t
r
u
c
t
i
o
n
m
e
m
o
r
y
4
R
e
g
i
s
t
e
r
s
S
i
g
n
e
x
t
e
n
d
M
u
x
M
u
x
C
o
n
t
r
o
l
E
X
M
W
B
M
W
B
W
B
M
u
x
H
a
z
a
r
d
d
e
t
e
c
t
i
o
n
u
n
i
t
F
o
r
w
a
r
d
i
n
g
u
n
i
t
M
u
x
I
F
.
F
l
u
s
h
I
F
/
I
D
a
n
d
 
$
1
2
,
 
$
2
,
 
$
5
b
e
q
 
 
$
1
,
 
$
3
,
 
7
s
u
b
 
$
1
0
,
 
$
4
,
 
$
8
M
E
M
/
W
B
E
X
/
M
E
M
I
D
/
E
X
C
l
o
c
k
 
3
7
2
4
4
4
8
4
4
2
8
7
$
1
$
3
1
0
4
8
7
2
7
2
0
$
4
$
8
A
L
U
D
a
t
a
m
e
m
o
r
y
M
u
x
S
h
i
f
t
l
e
f
t
 
2
b
e
f
o
r
e
<
1
>
b
e
f
o
r
e
<
2
>
=
Exemplo
9
M
u
x
0
b
u
b
b
l
e
 
(
n
o
p
)
l
w
 
$
4
,
 
5
0
(
$
7
)
C
l
o
c
k
 
4
b
e
q
 
 
$
1
,
 
$
3
,
 
7
s
u
b
 
$
1
0
,
 
.
 
.
 
.
b
e
f
o
r
e
<
1
>
P
C
I
n
s
t
r
u
c
t
i
o
n
m
e
m
o
r
y
4
R
e
g
i
s
t
e
r
s
S
i
g
n
e
x
t
e
n
d
M
u
x
M
u
x
C
o
n
t
r
o
l
E
X
M
W
B
M
W
B
W
B
M
u
x
H
a
z
a
r
d
d
e
t
e
c
t
i
o
n
u
n
i
t
F
o
r
w
a
r
d
i
n
g
u
n
i
t
I
F
.
F
l
u
s
h
I
F
/
I
D
M
E
M
/
W
B
E
X
/
M
E
M
I
D
/
E
X
7
6
7
2
7
6
7
2
$
1
$
3
1
0
7
6
A
L
U
D
a
t
a
m
e
m
o
r
y
M
u
x
S
h
i
f
t
l
e
f
t
 
2
=
Previsão dinâmica de desvio
Baseado no PC
Buffer de previsão de desvios ou tabela de histórico de desvios
Tabela indexada pelos N bits menos significativos de PC – 2^N linhas
Uma previsão em cada linha (PC % (2^N))
Se acerta a previsão o bit é mantido
Se errar, o bit é invertido
Ex: Loop – 9 desvios tomados e 1 não tomado
Executando o loop pela segunda vez – 2 erros (na entrada e na saida).
10
Pevisão de 2 bits
Precisa estar errado 2 vezes
Prevê tomado
Prevê tomado
Não tomado
Tomado
Tomado
Prevê não tomado
Prevê não tomado
Não tomado
Tomado
Não tomado
Tomado
Não tomado
11
01
10
00
Delay Slot