Aula 11:
Previsão Dinâmica de Branches,
Superescalar, Speculation e
Limites de ILP
ARQUITETURA DE COMPUTADORES
DEPT. DE CIÊNCIA DA COMPUTAÇÃO - UFMG
Revisão do Algoritmo de
Tomasulo
 Registradores não são gargalo
 Evita hazards de WAR, WAW e hazards no
Scoreboard
 Não está limitado a blocos básicos (desde que
tenhamos previsão de branches)
 Permite loop unrolling em HW
 Contribuições que existem até hoje
 Escalonamento dinâmico
 Register renaming
 Separação entre Loads e Stores
Previsão Dinâmica de
Branches
 Performance = ƒ(precisão, custo de previsão
errada)
 Branch History Table é a mais simples
 LSBs do endereço dado pelo PC endereça tabela de
valores de 1 bit
 Indica se branch naquela entrada da tabela foi
tomado ou não
 Problema: em um loop, BHT de 1 bit causará
duas previsões erradas:
 Final do loop, quando o branch não é tomado
 Primeira vez da iteração seguinte, quando o branch
da última vez não foi tomado
Previsão Dinâmica de
Branches
Solução: Utilização de 2-bits, onde
mudança de previsão ocorre somente se
previsão errada ocorre duas vezes:
Precisão de BHT
Precisão de BHT
Precisão do BHT
 Previsão errada ocorre em dois casos:
 Previsão errada para esse branch
 Leu da tabela previsão para branch errado
 Tabela com 4096 entradas
 Programas variam de 1% de erro (nasa7, tomcatv)
para 18% (eqntott), com spice em 9% e gcc em 12%
 Tabela com 4096 entradas é tão boa quanto
uma com um número infinito de entradas, mas
requer muito hardware
 Contador com 2 bits é tão bom quanto um
contador com um número infinito de bits
Branches Correlacionados
 Idéia: tomado/não tomado dos branches
executados recentemente está relacionado com
o comportamento do branch (tão relacionado
quanto o histórico deste branch)
Eqntott
if (aa
aa =
if (bb
bb =
if (aa
…
}
== 2)
0;
== 2)
0;
!= bb) {
Branches Correlacionados
Precisão dos Esquemas
Diferentes
Tournament Predictors
Mistura informação global com informação
local dos branches
Multi-nível
Alcança melhor resultado para BHTs de
tamanhos médios (8K-32K bits) e utiliza
melhor um número maior de bits de
correlação
Tournament Predictors
MIPS Precisa do Endereço
ao Mesmo Tempo que Previsão
 Branch Target Buffer (BTB): Endereço do índice
de branch busca previsão E endereço (se
branch for tomado) ao mesmo tempo
 Nota: Precisamos checar agora se o branch é
realmente aquele na tabela, porque não podemos
usar o endereço errado. Portanto, precisamos checar
o endereço
 O que acontece com endereços indiretos, por
exemplo, em retorno de procedimentos com
BTB?
Branch Target Buffers
Branch Target Buffer
Conseguindo CPI<1: Disparando
Múltiplas Instruções/Ciclo
 Duas Variações
 Superescalar: variando o número de
instruções/ciclo (1 a 8), escalonadas pelo
compilador ou por hardware (Tomasulo)
 IBM PowerPC, Sun SuperSparc, DEC Alpha, HP
7100
 Very Long Instruction Words (VLIW) ou EPIC
(explicitly parallel instruction computers) :
número de instruções fixas (16) escalonadas
pelo compilador
 Itanium (EPIC)
Conseguindo CPI < 1:Disparando
Múltiplas Instruções/Ciclo
 MIPS superescalar: 2 instruções, 1 FP & 1 inteira, load ou
store
– Busca de 64-bits/clock
– Mais portos para registradores FP para fazer load/store FP
Tipo
instr. Int
instr. FP
instr. Int
instr. FP
instr. Int
instr. FP
Estágios
IF
IF
ID
ID
IF
IF
EX MEM WB
EX MEM WB
ID
EX MEM WB
ID
EX MEM WB
IF
ID
EX MEM WB
IF
ID
EX MEM WB
 1 ciclo de load delay expande para 3 instruções em SS
 instrução à direita não pode usá-la, nem podem instrs. no próx. slot
Escalonamento Estático em
Superescalar
1 Loop:
2
3
4
5
6
7
8
9
10
11
12
13
14
L.D
L.D
L.D
L.D
ADD.D
ADD.D
ADD.D
ADD.D
S.D
S.D
S.D
DADDIU
BNE
S.D
F0,0(R1)
F6,-8(R1)
F10,-16(R1)
F14,-24(R1)
F4,F0,F2
F8,F6,F2
F12,F10,F2
F16,F14,F2
0(R1),F4
-8(R1),F8
-16(R1),F12
R1,R1,-32
R1,R2,LOOP
8(R1),F16
L.D to ADD.D: 1 Ciclo
ADD.D to S.D: 2 Ciclos
Escalonamento Estático
em Superescalar
Instr. Inteira
Loop:
L.D F0,0(R1)
L.D F6,-8(R1)
L.D F10,-16(R1)
L.D F14,-24(R1)
L.D F18,-32(R1)
S.D 0(R1),F4
S.D -8(R1),F8
S.D -16(R1),F12
S.D -24(R1),F16
DADDIU R1,R1,-40
BNE R1,R2,LOOP
S.D -32(R1),F20
Instr. FP
ADD.D F4,F0,F2
ADD.D F8,F6,F2
ADD.D F12,F10,F2
ADD.D F16,F14,F2
ADD.D F20,F18,F2
Ciclos
1
2
3
4
5
6
7
8
9
10
11
12
Limites de Processadores
Superescalares
 Enquanto quebra de unidades Inteiras/FP é
simples em HW, só conseguimos CPI de 0,5
para programas com:
 50% de operações Inteiras de FP
 Nenhum hazard
 Se mais instruções disparam ao mesmo tempo,
é mais difícil fazer decodificação e issue
 Até para 2-scalar => exame de 2 opcodes, 6
registradores, & decidir se 1 ou 2 instruções podem
ser disparadas
Escalonamento Dinâmico em
Superescalares
Dependências para o disparo
Código compilado para versão escalar
executa inadequadamente em SS
Precisamos manter compatibilidade
Idéia simples: separar controle de
Tomasulo para reservation stations das
unidades Inteira e de FP
Escalonamento Dinâmico em
Superescalares
 Como disparar 2 instruções e manter disparo
em ordem para Tomasulo?
 Issue executa 2X mais rápido que o resto da
máquina, portanto, issue é mantido em ordem
 Somente loads FP podem causar dependência entre
issue de unidade inteira e FP:
 Troca reservation station de load por fila;
operandos tem que ser lidos na ordem em que são buscados
 Verifique endereços de Loads com endereços de Store na
fila de Store para evitar violação de RAW
 Verifique endereços de Store na fila de Loads e Stores para
evitar WAR e WAW
Performance de Escalonamento
Dinâmico em SS
Iteração
no.
1
1
1
1
1
2
2
2
2
2
Instrs.
L.D F0,0(R1)
ADD.D F4,F0,F2
S.D 0(R1),F4
DADDIU R1,R1,-8
BNE R1,R2,LOOP
L.D F0,0(R1)
ADD.D F4,F0,F2
S.D 0(R1),F4
DADDIU R1,R1,-8
BNE R1,R2,LOOP
Issues
1
1
2
3
4
5
5
6
7
8
Executa
ciclo
2
5
9
4
5
6
9
13
8
9
Escreve
4
8
5
8
12
9
Speculation
 Permite uma instrução executar sem nenhuma
consequência, mesmo se branch não for
tomado (“HW undo”)
 Geralmente combinado com escalonamento
dinâmico
 Tomasulo: separa bypass especulativo dos
resultados do bypass real dos resultados
 Quando instr. não for mais especulativa, escreva os
resultados (instruction commit)
 Executa fora de ordem, mas commit em ordem
Speculation
Speculation
Necessita de buffer em HW para
resultados de instruções uncommitted:
reorder buffer
Reorder buffer pode ser fonte de operandos
Quando instr. commit, resultado pode ser
encontrado nos registradores
3 campos: tipo instr, destino, valor
Use número do reorder buffer ao invés do
número da reservation station
Quatro Passos do Algoritmo de
Tomasulo com Especulação
1. Issue—carrega instrução da fila de instruções de FP
Se reservation station ou reorder buffer slot livre, issue instr
& envie operandos & num. reorder buffer para destino.
2. Execução—(EX)
Quando ambos operandos estiverem na reservation station,
execute;
3. Escrita de Resultado—término da execução(WB)
Escreva no CDB para todas as FUs & reorder buffer
aguardando resultado; marque reservation station livre.
4. Commit—grave resultado com resultado de reorder
Quando instr. no topo do reorder buffer & resultado estiver
presente, grave resultado em registrador ou memória
Limites para ILP
Modelo inicial de hardware; compiladores MIPS
1. Register renaming–número infinito de registradores
virtuais para evitar todos os hazards de WAW & WAR
2. Branch prediction–perfeito; sem previsões erradas
3. Jump prediction–previsões perfeitas => máquina com
especulação perfeita & buffer de instruções ilimitado
4. Análise de sinônimos de memória–endereços são
conhecidos e stores podem ser movidos antes de loads
se os endereços não forem iguais
1 ciclo de latência para todas as instruções
Limite Superior para ILP
Impacto da Janela
Impacto da Janela
Efeito da Previsão de
Branches
Efeito do Número de
Registradores
Impacto de Alias
Resumo do Cap. 3
Previsão de Branches
Processadores Superescalares
Speculation
Limites de ILP