Infra-estrutura de Hardware
Melhorando o desempenho da
CPU
Infra-estrutura de Hardware
Roteiro da Aula
• Melhorando desempenho
– Mais recursos
– Lavanderia
• Técnica de Pipeline
– Comparando desempenho
• Entendendo o funcionamento do pipeline
• Resolvendo conflitos no pipeline
– Conflito dado
– Conflito controle
• Resolvendo situações de exceção
• Resumo
Infra-estrutura de Hardware
Como um documento é processado?
1- Busca
documento
2 - Identifica tipo
de transação
3 - Verifica se saldo
é positivo
4 - Efetiva transação e
atualiza saldo
Infra-estrutura de Hardware
Ciclo de Instrução
Busca instrução
Incrementa PC
Decodifica instrução
Busca operando
Executa instrução
Armazena resultado
Infra-estrutura de Hardware
O hardware está sendo bem utilizado?
• Numa implementação serial de instruções
partes do hardware ficam ociosas durante a
execução de uma instrução
• Se várias instruções fossem processadas ao
mesmo tempo com cada parte do hardware
atuando numa instrução distinta teríamos
melhor utilização do hardware.
• Pipeline
Infra-estrutura de Hardware
Melhorando a eficiência
Busca
documento
Identifica tipo
de transação
Verifica se saldo
é positivo
Infra-estrutura de Hardware
Efetiva transação e atualiza
saldo
Outro Exemplo
• Exemplo: Lavanderia
– Lavagem: 30 min
– Secagem: 30 min
– Passar a ferro: 30 min
– guardar : 30 min
Infra-estrutura de Hardware
Lavanderia
6 PM
7
8
9
10
11
T im e
Task
o rd e r
A
B
C
D
• Lavagem sequencial
• Duração: 8 horas
Infra-estrutura de Hardware
12
1
2 AM
Lavanderia
6 PM
7
8
9
10
11
12
1
2 AM
T im e
Task
o rd e r
A
B
Lavagem em pipeline
 Duração: 3.5 horas

C
D
Infra-estrutura de Hardware
Lavanderia pipeline
 Pipelining
não diminui o tempo de
execução de uma tarefa, ele
melhora a taxa de execução de
um conjunto de tarefas
 Tarefas múltiplas simultâneas
usando diferentes recursos
 Aumento no desempenho=
Número de estágios
 Taxa é limitada pelo estágio mais
lento
 Tempo para “encher” e “esvaziar”
o pipeline reduz o desempenho
 Espera quando houver Infra-estrutura de Hardware
dependências
6 PM
T im e
Ta sk
o rd e r
A
B
C
D
7
8
9
10
Os 5 estágios de uma instrução LOAD
Load
Cycle 1
Cycle 2
Cycle 3
Ifetch
Reg/Dec
Exec
Cycle 4
 Ifetch:
Mem
Cycle 5
Wr
Busca de instrução da memória de instrução
 Reg/Dec: Carregamento de registradores e
decodificação da instrução
 Exec: Cálculo do endereço de memória
 Mem: Leitura da memória de dados
 Wr: Escrita no banco de registradores
Infra-estrutura de Hardware
Pipeline vs. Mono-ciclo
Program
execution
Time
order
(in instructions)
lw $1, 100($0)
2
Instruction
Reg
fetch
lw $2, 200($0)
4
6
8
ALU
Data
access
10
12
14
ALU
Data
access
16
18
Reg
Instruction
Reg
fetch
8 ns
lw $3, 300($0)
Reg
Instruction
fetch
8 ns
...
8 ns
Program
execution
Time
order
(in instructions)
2
lw $1, 100($0)
Instruction
fetch
lw $2, 200($0)
2 ns
lw $3, 300($0)
4
Reg
Instruction
fetch
2 ns
6
ALU
Reg
Instruction
fetch
8
Data
access
ALU
Reg
10
14
12
Reg
Data
access
ALU
Reg
Data
access
Reg
Infra-estrutura de Hardware
2 ns
2 ns
2 ns
2 ns
2 ns
Mono, multi-ciclo e Pipeline
Cycle 1
Cycle 2
Clk
Single Cycle Implementation:
Load
Store
Waste
Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Cycle 10
Clk
Multiple Cycle Implementation:
Load
Ifetch
Store
Reg
Exec
Mem
Wr
Exec
Mem
Wr
Reg
Exec
Mem
Ifetch
R-type
Reg
Pipeline Implementation:
Load Ifetch
Reg
Store Ifetch
R-type Ifetch
Wr
Infra-estrutura de Hardware
Reg
Exec
Mem
Wr
Exec
Mem
Ifetch
Implementando o pipeline
IF: Instruction fetch
ID: Instruction decode/
register file read
EX: Execute/
address calculation
MEM: Memory access
WB: Write back
0
M
u
x
1
Add
Add
Add result
4
Shift
left 2
PC
Read
register 1
Address
Instruction
Instruction
memory
Read
data 1
Read
register 2
Registers Read
Write
data 2
register
Write
data
0
M
u
x
1
Zero
ALU ALU
result
Address
Data
memory
Write
data
16
Sign
extend
32
Infra-estrutura de Hardware
Read
data
1
M
u
x
0
Implementando o pipeline
Registradores do Pipeline
0
M
u
x
1
IF/ID
ID/EX
EX/MEM
MEM/WB
Add
Add
Add result
4
PC
Address
Instruction
memory
Instruction
Shift
left 2
Read
register 1
Read
data 1
Read
register 2
Registers Read
Write
data 2
register
Write
data
0
M
u
x
1
Zero
ALU ALU
result
Address
Data
memory
Write
data
16
Sign
extend
32
Infra-estrutura de Hardware
Read
data
1
M
u
x
0
Operação de um pipeline: lw (1)
lw
Instruction fetch
0
M
u
x
1
IF/ID
ID/EX
EX/MEM
MEM/WB
80000004
PC
Address
Instruction
memory
Add
Add result
Shift
left 2
Instruction
4
8D28 04B0 80000008
Add
Read
register 1
Read
data 1
Read
register 2
Registers Read
Write
data 2
register
Write
data
0
M
u
x
1
Zero
ALU ALU
result
Address
Data
memory
Write
data
16
Sign
extend
32
Infra-estrutura de Hardware
Read
data
1
M
u
x
0
Operação de um pipeline : lw (2)
lw
0
M
u
x
1
Instruction decode
ID/EX
PC
Address
Instruction
memory
Instruction
4
8D28 04B0 80000008
Add
9
8
Read
register 1
Read
data 1
Read
register 2
Registers Read
00000002
Write
data 2
80000004
register
Write
data
16
Sign
extend
32
00000008 80000004 80000008
IF/ID
EX/MEM
MEM/WB
Add
Add result
Shift
left 2
0
M
u
x
1
Zero
ALU ALU
result
Infra-estrutura de Hardware
Address
Data
memory
Write
data
Read
data
1
M
u
x
0
Operação de um pipeline : lw (3)
lw
0
M
u
x
1
Execution
Add
PC
Address
Instruction
memory
Instruction
4
Read
register 1
Read
data 1
Read
register 2
Registers Read
Write
data 2
register
Write
data
16
Sign
extend
32
00000008 80000004 80000008
ID/EX
EX/MEM
Add
MEM/WB
Add
result
Shift
left 2
0
M
u
x
1
Zero
ALU ALU
result
Infra-estrutura de Hardware
8000000C
IF/ID
Address
Data
memory
Write
data
Read
data
1
M
u
x
0
Operação de um pipeline : lw (4)
lw
0
M
u
x
1
Memory
IF/ID
ID/EX
EX/MEM
MEM/WB
Add
Add
Add result
4
Instruction
memory
Read
register 1
Read
data 1
Read
register 2
Registers Read
Write
data 2
register
Write
data
16
Sign
extend
0
M
u
x
1
32
Infra-estrutura de Hardware
Zero
ALU ALU
result
Address
Data
memory
Read
data
Write
data00000005
00000005
Address
8000000C
PC
Instruction
Shift
left 2
1
M
u
x
0
Operação de um pipeline : lw (5)
lw
01000
0
M
u
x
1
Write back
IF/ID
ID/EX
EX/MEM
MEM/WB
Add
Add Add
result
4
Address
Instruction
memory
Read
register 1
Instruction
PC
?
Read
data 1
Read
register 2
Registers Read
Write
data 2
register
Write
data
0
M
u
x
1
Zero
ALU ALU
result
Address
Data
memory
Write
data
16
Sign
extend
32
Infra-estrutura de Hardware
00000005
Read
data
00000005
Shift
left 2
1
M
u
x
0
Operação de um pipeline : lw (5)
0
M
u
x
1
IF/ID
ID/EX
EX/MEM
MEM/WB
Add
4
Add
Add
result
0
M
u
x
1
Write
data
Zero
ALU ALU
result
Address
Data
memory
Read
data
00000005
Read
data 1
Read
register 2
00000005
Registers Read
Write80000004
data 2
register
Write
data
16
Sign
extend
32
Infra-estrutura de Hardware
01000
Instruction
memory
Read
register 1
01000
Address
01000
PC
Instruction
Shift
left 2
1
M
u
x
0
Operação de um Pipeline: sw (3)
sw
0
M
u
x
1
Execution
PC
Address
Instruction
memory
Read
register 1
Read
data 1
Read
register 2
00000002
Registers Read
Write
data 2
80000004
register
Write
data
16
Sign
extend
32
Add
Add result
Shift
left 2
0
M
u
x
1
Zero
ALU ALU
result
Infra-estrutura de Hardware
MEM/WB
00000002
Instruction
4
00000008 80000004
Add
EX/MEM
8000000C
ID/EX
00000002
IF/ID
Address
Data
memory
Write
data
Read
data
1
M
u
x
0
Operação de um Pipeline: sw (4)
sw
0
M
u
x
1
Memory
ID/EX
EX/MEM
Add
Add
Add result
4
Address
Instruction
memory
Read
register 1
Read
data 1
Read
register 2
Registers Read
Write
data 2
register
Write
data
0
M
u
x
1
Zero
ALU ALU
result
i
16
Sign
extend
32
Infra-estrutura de Hardware
8000000C
PC
Instruction
Shift
left 2
MEM/WB
00000002
IF/ID
Read
data
Address
Data
memory
00000002
Write
data
1
M
u
x
0
Operação de um Pipeline: sw (5)
sw
0
M
u
x
1
Write back
IF/ID
ID/EX
EX/MEM
MEM/WB
Add
Add Add
result
4
PC
Address
Instruct on
memory
Instruction
Shift
left 2
Read
register 1
Read
data 1
Read
register 2
Registers Read
Write
data 2
register
Write
data
0
M
u
x
1
Zero
ALU ALU
result
i
16
Sign
extend
Address
Data
memory
Write
data
32
Infra-estrutura de Hardware
Read
data
1
M
u
x
0
Representação de um pipeline
Time (in clock cycles)
Program
execution
order
(in instructions)
lw $1, 100($0)
lw $2, 200($0)
lw $3, 300($0)
CC 1
CC 2
IM
Reg
IM
CC 3
ALU
Reg
IM
CC 4
CC 5
DM
Reg
ALU
Reg
Infra-estrutura de Hardware
DM
ALU
CC 6
CC 7
Reg
DM
Reg
Representando o pipeline
Time (in clock cycles)
Program
execution
order
(in instructions)
lw $10, 20($1)
sub $11, $2, $3
CC 1
CC 2
CC 3
IM
Reg
ALU
IM
Reg
Infra-estrutura de Hardware
CC 4
CC 5
DM
Reg
ALU
DM
CC 6
Reg
Representando o pipeline
Program
execution
order
(in instructions)
lw $10, $20($1)
sub $11, $2, $3
Time ( in clock cycles)
CC 1
CC 2
CC 3
CC 4
CC 5
Instruction
fetch
Instruction
decode
Execution
Data
access
Write back
Instruction
fetch
Instruction
decode
Execution
Data
access
Infra-estrutura de Hardware
CC 6
Write back
Implementando o Pipeline: processamento
PCSrc
0
M
u
x
1
IF/ID
ID/EX
EX/MEM
MEM/WB
Add
Add
result
Add
4
Branch
Shift
left 2
PC
Address
Instruction
memory
Instruction
RegWrite
Read
register 1
MemWrite
Read
data 1
Read
register 2
Registers Read
Write
data 2
register
Write
data
ALUSrc
Zero
Zero
ALU ALU
result
0
M
u
x
1
MemtoReg
Address
Data
memory
Write
data
Instruction
16
[15– 0]
Sign
extend
32
6
ALU
control
Instruction
[20– 16]
Instruction
[15– 11]
0
M
u
x
1
ALUOp
Infra-estrutura de Hardware
RegDst
MemRead
Read
data
1
M
u
x
0
Implementando o Pipeline:controle
WB
Instruction
IF/ID
Control
M
WB
EX
M
WB
ID/EX
EX/MEM
MEM/WB
Infra-estrutura de Hardware
Implementando o Pipeline:controle
PCSrc
ID/EX
0
M
u
x
1
WB
Control
IF/ID
EX/MEM
M
WB
EX
M
MEM/WB
WB
Add
ALUSrc
Read
register 1
Read
data 1
Read
register 2
Registers Read
Write
data 2
register
Write
data
Zero
ALU ALU
result
0
M
u
x
1
MemtoReg
Instruction
memory
Branch
Shift
left 2
MemWrite
Address
Instruction
PC
Add
Add result
RegWrite
4
Address
Data
memory
Read
data
Write
data
Instruction 16
[15– 0]
Instruction
[20– 16]
Instruction
[15– 11]
Sign
extend
32
6
ALU
control
0
M
u
x
1
ALUOp
Infra-estrutura de Hardware
RegDst
MemRead
1
M
u
x
0
O pipeline é sempre eficiente???
• Eficiência do pipeline:
– estágios com a mesma duração
– instruções independentes de resultados
calculados em instrução anterior
– execução sequencial das instruções
... mas as características acima quase sempre não
são satisfeitas:
•dependência de dados
•instruções de desvio
Infra-estrutura de Hardware
Conflitos
• Impedem a execução da próxima
instrução no ciclo previsto
• Tipos:
– estrutural
• conflito no uso dos recursos
– controle
• alteração do fluxo do programa por instruções de
desvio e chamada de funções
– dado
• dependência de dados
Infra-estrutura de Hardware
Conflito Estrutural
-Algum recurso não suficientemente replicado
-Mesma memória (cache) para dados e instruções
O conflito estrutural pode ser eliminado
replicando-se o recurso
Infra-estrutura de Hardware
Conflito estrutural: memória única
Time (clock cycles)
Instr 4
Reg
Mem
Reg
Mem
Reg
Mem
Reg
Mem
Reg
Mem
Reg
Mem
Reg
ALU
Instr 3
Reg
ALU
Instr 2
Mem
Mem
ALU
Instr 1
Reg
ALU
O
r
d
e
r
Load
Mem
ALU
I
n
s
t
r.
Mem
Infra-estrutura de Hardware
Reg
r1: Problema
Time (clock cycles)
IF
Im
Reg
Im
Reg
Im
Reg
ALU
Dm
Im
Reg
ALU
or r8,r1,r9
Dm
ALU
and r6,r1,r7
Reg
ALU
O
r
d
e
r
sub r4,r1,r3
Im
MEM WB
ALU
I
n
s
t
r.
add r1,r2,r3
ID/RF EX
xor r10,r1,r11
Infra-estrutura de Hardware
Reg
Dm
Reg
Dm
Reg
Reg
Dm
Reg
Conflito de Dado em R1:
Funcionamento Correto
Time (clock cycles)
ME
M
Dm
W
B
Reg
Im
Reg
Dm
Im
Reg
ALU
Dm
Im
Reg
ALU
O and r6,r1,r7
r
d
e or r8,r1,r9
r
E
X
ALU
sub r4,r1,r3
ID/R
FReg
ALU
I
n
s
t
r.
I
add r1,r2,r3 F
Im
Im
Reg
Infra-estrutura de Hardware
Reg
Dm
ALU
xor r10,r1,r11
Reg
Reg
Dm
Reg
Resolvendo o conflito de dado
- Software : inserir NOP’s
Infra-estrutura de Hardware
Inserindo NOP´s
Im
Reg
Reg
Dm
Reg
Dm
Im
Reg
Dm
Im
Reg
ALU
Dm
ALU
Im
Reg
Infra-estrutura de Hardware
Reg
Reg
Reg
Dm
ALU
xor r10,r1,r11
Reg
Im
W
B
Reg
ALU
or r8,r1,r9
ME
M
Dm
ALU
O sub r4,r1,r3
r
d
e and r6,r1,r7
r
Im
E
X
ALU
I
n nop
s
t
nop
r.
ID/R
FReg
ALU
• Inserir NOP’s
I
add r1,r2,r3 F
Im
Reg
Dm
Reg
Resolvendo o conflito de dado
- Software : inserir NOP’s
degradação do desempenho
trocar a ordem das instruções.
Infra-estrutura de Hardware
Rearrumando código
Im
Reg
Reg
Dm
Reg
Dm
Im
Reg
Dm
Im
Reg
ALU
Dm
ALU
Im
Reg
Infra-estrutura de Hardware
Reg
Reg
Reg
Dm
ALU
xor r10,r1,r11
Reg
Im
W
B
Reg
ALU
or r8,r1,r9
ME
M
Dm
ALU
O sub r4,r1,r3
r
d
e and r6,r1,r7
r
Im
E
X
ALU
I
n and r12, r12, r13
s
t
or r14, r14, r15
r.
ID/R
FReg
ALU
• Inserir NOP’s
I
add r1,r2,r3 F
Im
Reg
Dm
Reg
Resolvendo o Conflito de Dados
- Software : inserir NOP’s
degradação do desempenho
trocar a ordem das instruções
compilador “inteligente”
- Hardware : método do curto circuito
Infra-estrutura de Hardware
Método do Curto Circuito
P ro g ra m
e x e c u tio n
o rd e r
2
4
6
8
10
T im e
(in in s tru c tio n s )
a d d $ s 0 , $ t0 , $ t1
s ub $ t2, $ s 0 , $ t3
IF
ID
EX
IF
ID
Infra-estrutura de Hardware
M EM
EX
WB
M EM
WB
Curto Circuito - Forwarding
Dm
Reg
Reg
Im
Reg
Dm
Im
Reg
Dm
Im
Reg
Dm
Im
Reg
ALU
or r8,r1,r9
W
B
ALU
and r6,r1,r7
ME
M
ALU
O
r
d
e
r
sub r4,r1,r3
Im
E
X
ALU
I
n
s
t
r.
add r1,r2,r3
ID/R
F
ALU
Time (clock cycles)
I
F
xor r10,r1,r11
Infra-estrutura de Hardware
Reg
Reg
Reg
Dm
Reg
ID/EX
EX/MEM
Registers
MEM/WB
ALU
Data
memory
Curto
Circuito
M
u
x
a. No forwarding
ID/EX
EX/MEM
MEM/WB
M
u
x
Registers
ForwardA
ALU
M
u
x
Rs
Rt
Rt
Rd
Data
memory
ForwardB
M
u
x
EX/MEM.RegisterRd
Forwarding
unit
Infra-estrutura de Hardware
b. With forwarding
MEM/WB.RegisterRd
M
u
x
Resolvendo o Conflito de Dados
- Software : inserir NOP’s
degradação do desempenho
trocar a ordem das instruções
compilador “inteligente”
- Hardware : método do curto circuito
operações entre registradores
inserir retardo (reg/mem)
Infra-estrutura de Hardware
Inserindo retardos
lw r1,0(r2)
Im
ID/R
F
Reg
E
X
ALU
Time (clock cycles)
I
F
bubble
W
B
Dm
Reg
bubble
Im
Reg
Infra-estrutura de Hardware
bubble
ALU
sub r4,r1,r3
ME
M
Dm
bubble
Reg
Inserindo retardos
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
Infra-estrutura de Hardware
Reg
Reg
DM
Reg
Detectando e Resolvendo Conflitos
ID/EX.MemRead
IF/IDWrite
Hazard
detection
unit
ID/EX
WB
M
u
x
Control
0
PC
Instruction
memory
Instruction
PCWrite
IF/ID
EX/MEM
M
WB
EX
M
MEM/WB
WB
M
u
x
Registers
ALU
Data
memory
M
u
x
IF/ID.RegisterRs
IF/ID.RegisterRt
IF/ID.RegisterRt
Rt
IF/ID.RegisterRd
Rd
ID/EX.RegisterRt
Rs
Rt
M
u
x
Infra-estrutura de Hardware
EX/MEM.RegisterRd
Forwarding
unit
MEM/WB.RegisterRd
M
u
x
Conflito de Controle
• Necessidade da alteração no fluxo:
– desvios condicionais e incondicionais
– chamadas e retornos de subrotinas
– interrupções
• Como resolver o conflito minimizando a
perda de desempenho?
Infra-estrutura de Hardware
Conflito de Controle
Time (in clock cycles)
Program
execution
CC 1
CC 2
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
Infra-estrutura de Hardware
IM
CC 7
Reg
DM
Reg
Reg
DM
Reg
Conflito de Controle
• Reduzindo o retardo devido a
desvios....
Infra-estrutura de Hardware
Antecipando desvio
IF.Flush
Hazard
detection
unit
ID/EX
M
u
x
WB
Control
0
M
u
x
IF/ID
4
M
WB
EX
M
MEM/WB
WB
Shift
left 2
Registers
PC
EX/MEM
=
M
u
x
Instruction
memory
ALU
M
u
x
Sign
extend
M
u
x
Forwarding
unit
Infra-estrutura de Hardware
Data
memory
M
u
x
Resolvendo o Conflito de Controle
– Esperar para buscar próxima instrução até
que o desvio seja executado
Congelamento do pipeline
Infra-estrutura de Hardware
Congelamento do pipeline
• Descoberta de instrução de desvio no
pipeline
• Suspensão da busca de instruções
+ Simplicidade
– Degradação do desempenho do pipeline
Infra-estrutura de Hardware
Resolvendo o Conflito de Controle
– Esperar para buscar próxima instrução até
que o desvio seja executado
Congelamento do pipeline
– Predizer o comportamento do desvio
Execução especulativa
Infra-estrutura de Hardware
Execução especulativa
• O estado da máquina antes do desvio
deve ser guardado
• Perda de desempenho
– técnicas de compilação p/ aumento dos
acertos
– capacidade de recuperação do estado
rapidamente
Infra-estrutura de Hardware
Execução especulativa
• Previsão do desvio:
– a ocorrência de todos/nenhum desvio
• 68020, VAX 11/780
– com base no opcode
– análise da direção do desvio
– dinâmica:
• Chave desvio/ não desvio
Infra-estrutura de Hardware
Estratégias de Previsão de Desvio
• Estáticas
– As previsões não mudam
– Exemplos:
• Always-Not Taken
• Always-Taken
• Backwards Taken, Forward Not Taken (BTFNT)
• Dinâmicas
– Previsão pode mudar durante a execução do
programa
59
Previsão de Desvio Dinâmica
• Porque previsão dinâmica funciona?
– Algoritmos possuem regularidades
– Dados tem regularidades
Arquitetura Não
Convencional de
60
Previsão de Desvio Dinâmica
• Tabela da História de Branch (BHT):
– bits menos significativos do PC endereça
tabela com entradas de dois bits
– Cada entrada informa a previsão do desvio
branch PC
BHT
01
Arquitetura Não
Convencional de
61
Tabela da História dos Desvios
• Solução: esquema de 2-bits onde a
previsão é mudada somente em caso de
erro, (2 vezes)
T
NT
11
Predict Taken
T
NT
T
Predict Not
Taken
10
01
T
00
Predict Taken
NT
Predict Not
Taken
NT
• Red: stop, not taken
• Blue: go, taken
62
Tabela da História dos Desvios
• Tem tamanho limitado
• 2 bits por N (por exemplo N = 4K entradas)
• Usa bits menos significativos do PC para endereçar
tabela
branch PC
T
BHT
01
NT
Predict Taken 11
T
NT
T
Predict Not
Taken
10
01
NT
00
T
Predict Taken
Predict Not
Taken
NT
63
Nov. 9, 2004
Branch History Table: Exemplo 1
• Loop simples com 1 desvio, 4 iterações
• BHT inicialmente 00
• Primeira iteração:
branch PC
BHT
– previsão NT, corrente T
– Atualiza BHT : 00 para 01
01
00
T
NT
11
Predict Taken
T
NT
T
Predict Not
Taken
10
01
Predict Taken
NT
Predict Not
Taken
00
T
NT
64
Branch History Table: Exemplo 1
• Loop simples com 1 desvio, 4 iterações
• BHT inicialmente 00
• Primeira iteração:
branch PC
BHT
– previsão NT, corrente T
– Atualiza BHT : 00 para 01
11
01
• Segunda iteração:
– previsão NT, corrente T
– Atualiza BHT : 01
11
T
NT
11
Predict Taken
T
NT
T
Predict Not
Taken
10
01
Predict Taken
NT
Predict Not
Taken
00
T
NT
65
Branch History Table: Exemplo 1
• Loop simples com 1 desvio, 4 iterações
• BHT inicialmente 00
•
–
–
•
branch PC
Primeira iteração:
previsão NT, corrente T
Atualiza BHT : 00 para 01
11
01
Segunda iteração:
–
–
BHT
previsão NT, corrente T
Atualiza BHT : 01
11
• Terceira iteração:
– previsão T, corrente T
– Sem mudança na BHT
T
NT
11
Predict Taken
T
NT
T
Predict Not
Taken
10
01
Predict Taken
NT
Predict Not
Taken
00
T
NT
66
Branch History Table: Exemplo 1
• Loop simples com 1 desvio, 4 iterações
• BHT inicialmente 00
•
–
–
•
previsão NT, corrente T
11
10
Segunda iteração:
–
previsão NT, corrente T
Atualiza BHT : 01
11
Terceira iteração:
–
–
•
BHT
Atualiza BHT : 00 para 01
–
•
branch PC
Primeira iteração:
previsão T, corrente T
Sem mudança na BHT
Quarta iteração: previsão T, corrente NT
–
Atualiza BHT : 11
10
T
NT
11
Predict Taken
T
NT
T
Predict Not
Taken
10
01
Predict Taken
NT
Predict Not
Taken
00
T
67
NT
BHT: Exemplo 1
•
•
•
•
•
Parece sem eficácia
4 instancias de desvio executadas e 3 previsões erradas.
branch PC
E se o loop fosse executado mais vezes?
BHT igual a 10
Primeira iteração:
– previsão T, corrente T
BHT
11
10
– Atualiza BHT: 10 para 11
T
NT
11
Predict Taken
T
NT
T
Predict Not
Taken
10
01
Predict Taken
NT
Predict Not
Taken
00
T
NT
68
BHT: Exemplo 1
•
•
•
•
•
Parece sem eficácia
4 instancias de desvio executadas e 3 previsões erradas.
branch PC
E se o loop fosse executado mais vezes?
BHT igual a 10
Primeira iteração:
– previsão T, corrente T
BHT
11
– Não atualiza BHT
• Segunda iteração:
– previsão T, corrente T
– Não atualiza BHT
T
• Terceira iteração:
– previsão T, corrente T
– Não atualiza BHT
NT
11
Predict Taken
T
NT
T
Predict Not
Taken
10
01
Predict Taken
NT
Predict Not
Taken
00
T
NT
69
BHT: Exemplo 1
•
•
•
•
Parece sem eficácia
4 instancias de desvio executadas e 3 previsões erradas.
branch PC
E se o loop fosse executado mais vezes?
BHT igual a 10
•
Primeira iteração:
–
–
•
11
10
previsão T, corrente T
Não atualiza BHT
Segunda iteração:
–
–
•
BHT
previsão T, corrente T
Não atualiza BHT
Terceira iteração:
–
T
previsão T, corrente T
execuções:
11
Predict Taken
de previsão
• Quarta somente
iteração: 1 erro
–
Não atualiza
BHT
Próximas
T
– previsão T, corrente NT
– Atualiza BHT
•
Predict Not
Taken
NT
10
T
NT
01
Predict Taken
NT
Predict Not
Taken
00
T
11 para 10
NT
70
Execução especulativa
• branch target
buffer (BTB)
• Profiling
• Pentium e
Power-PC
Infra-estrutura de Hardware
Resolvendo o Conflito de Controle
– Esperar para buscar próxima instrução até
que o desvio seja executado
Congelamento do pipeline
– Predizer o comportamento do desvio
Execução especulativa
– Buscar sempre a instrução seguinte ao
desvio
Desvio com efeito retardado
Infra-estrutura de Hardware
Desvio com efeito retardado
• Instruções seguintes ao desvio devem ser
independentes do desvio
Ling. alto nível
If a=b then
a:= a+1
else
a: a-1
end if;
Linguagem máquina
lw $1,a
lw $2,b
beq $1,$2, end
addi $1,$1, -1
j end2
end1: addi $1, $1, 1
end2: sw $1,a
Infra-estrutura de Hardware
Desvio com efeito retardado
Linguagem máquina
lw $1,a
lw $2,b
beq $1,$2, end1
Linguagem máquina
lw $1,a
lw $2,b
beq $1,$2, end1
addi $1, $1, -1
j end2
end1: addi $1,$1, 1
end2: sw $1, a
addi $6, $6,$7
lw $8, z
lw $9,w
addi $1,$1, -1
j end2
Slots de
retardo
end1: addi $1, $1, 1
end2: sw $1,a
Infra-estrutura de Hardware
Desvios condicionais
• Comparação e desvios
– Comparação
• flags são alterados
– Desvios condicionais:
• análise de um ou mais flags
• desvio caso condição seja verdade
• Suporte da arquitetura:
• Alteração dos flags deve ser feita explicitamente
– Sparc, RS/6000 e Power: Indicado no opcode
Infra-estrutura de Hardware
Anulação de instrução
• instrução do slot de retardo é anulada
quando previsão não se confirma
Endereço
L1
....
Instrução
Add $1 $1,, $2
Sub $3, $3, $4
Lw $5, x
.....
Beq $4,$5, L1
Add $1,$1, $5
Endereço
L1
L2
...
Se desvio não ocorrer,
instruções são anuladas
Infra-estrutura de Hardware
Instrução
Add $1, $1, $2
Sub $3, $3, $4
lw $5, x
lw $3,y
.....
Beq $4, $5, L2
Add $1,$1, $2
Sub $3, $3, $4
Lw $5,x
Add $1,$1, $5
E se ocorrer uma exceção???
Qual o comportamento do
pipeline???
Infra-estrutura de Hardware
Exceções
• Sequência de execução é alterada devido
a eventos não esperados:
– internos:
• opcode inexistente
• overflow
• divisão por zero
– externos:
• dispositivo de entrada/saída
Infra-estrutura de Hardware
Exceções
• Execução do programa é interrompida e
uma rotina de tratamento é executada
– Valor do PC deve ser guardado
– O endereço da rotina de tratamento deve ser
carregado em PC
Infra-estrutura de Hardware
Exceções
• Onde guardar o endereço do PC?
– Registrador
• MIPS: EPC
– Pilha
• Onde o endereço da sua subrotina deve ser
guardado?
– Valor fixo
• precisa-se saber a causa da exceção
– Vetor de endereços na memória
Infra-estrutura de Hardware
Exceções - MIPS
• Tipos de Exceções:
– Instrução Indefinida
• endereço: C0 00 00 00
– Overflow aritmético
• endereço: C0 00 00 20
• Registrador EPC
– guarda endereço da instrução afetada
• Registrador de Causa
– identifica o tipo de evento que causou a exceção
Infra-estrutura de Hardware
Exceções
• Comportamento do pipeline:
– Instruções antes da que causou exceção
devem ser terminadas
– Instruções após a que causou exceção
devem ser anuladas
Infra-estrutura de Hardware
Exceções Exemplo
Exceções Exemplo
Tipos de Exceções
•
•
•
•
•
Opcode não válido
Overflow
Mal funcionamento do hardware
Chamada do S.O
Requisição de Dispositivo de E/S
• Como salvar o endereço correto em EPC?
Infra-estrutura de Hardware
Tipos de Exceções
• Duas formas de tratamento
– Exceção precisa:
• O endereço correto é salvo em EPC
– Exceção imprecisa:
• O valor corrente do PC (não da instrução que
causou a exceção) é salvo em EPC
Infra-estrutura de Hardware
Resumo
• Melhor utilização do hardware durante execução
das instruções
– Pipeline
• Conflitos: estrutural, de dado e de controle
• Estrutural: duplicação de recurso
• Dado:
– hardware: curto-circuito
– software: rearrumação
Infra-estrutura de Hardware
Resumo
• Controle:
– Congelamento
– Execução especulativa:
• estática
• dinâmica
– Desvio com efeito retardado
• Rearrumação do código
Infra-estrutura de Hardware
Resumo
– Exceções:
• Hardware para anular instruções subsequentes a
que causou a exceção
• Que valor salvar em EPC?
– Tipos de exceções
• Exceção precisa:
– Salva em PC endereço da instrução que causou
exceção
• Exceção imprecisa:
– Salva em EPC valor corrente do PC
Infra-estrutura de Hardware