Previsão de Desvio, Superescalar,
VLIW e Software Pipelining
DAP.F96 1
Revisão: Tomasulo
• Evita conflitos WAR, WAW sem espera
• Permite desenrolamento de loop em HW
• Não limitado a blocos básicos (provê
previsão de desvio)
• Contribuições
– Escalação Dinâmica
– Renomeação de Registradores
– Tratamento separado de Load e Store
• Descendentes do 360/91 são PowerPC 604,
620; MIPS R10000; HP-PA 8000; Intel Pentium
Pro, II, III, IV
DAP.F96 2
Previsão estática de desvio
• Análise de desvios pelo software (compilador), e
tomada de medidas para melhoria do
desempenho
• Exemplo: desenrolamento de loops, para
diminuir a quantidade de desvios.
DAP.F96 3
Previsão Dinâmica de Desvio (hardware)
Previsão Local: uma instrução de desvio
Global: várias instruções de desvio
• Previsão Local Simples: usa apenas um bit
Usa-se a tabela – Branch History Table – BHT - de um bit,
onde o índice de entrada é a parte menos significativa da
instrução de branch
BNEZ R1, Loop
• O bit diz se o desvio aconteceu ou não da última vez
• Em um loop, causa dois erros de previsões:
– Início: a previsão é não fazer loop
– Fim: a previsão é fazer loop
DAP.F96 4
Exemplo
Loop: LD
MULTD
SD
SUBI
BNEZ
F0
F4
F4
R1
R1
0
F0
0
R1
Loop
R1
F2
R1
#8
Considerando-se que no início R1 é igual a 80, e bit de previsão igual a 0
(não desvia).
INÍCIO: Primeira execução de BNEZ:
como R1 = 80, desvia, ocorre erro de previsão,
muda a previsão na BHT para 1 (desvia).
Execução de BNEZ subseqüentes:
enquanto R1 > 0, desvia, previsão é correta
a previsão na BHT continua 1 (desvia).
FIM: Última execução de BNEZ:
como R1 = 0, não desvia, ocorre erro de previsão,
muda a previsão na BHT para 0 (não desvia).
DAP.F96 5
Previsão Local usando 2 bits
• a previsão muda somente quando ocorrerem dois erros:
desvia
Não-desvia
Previsãode
desvio
11
Previsãode
desvio
10
desvia
desvia
Previsãode
não-desvio
01
Não-desvia
Nãodesvia
início
Previsãode
não-desvio
00
desvia
Nãodesvia
• Incrementa quando ocorre desvio
• Decrementa quando não ocorre desvio
DAP.F96 6
Loop:
Exemplo
.................................................................
SUBI
R1
R1
#8
BNEZ
R1
Loop
No início R1 é igual a 80, e bit de previsão igual a 00(não desvia).
INÍCIO:
Primeira execução de BNEZ:
como R1 = 80, desvia, ocorre erro de previsão,
muda a previsão na BHT para 01 (não desvia).
Segunda execução de BNEZ:
como R1 = 72, desvia, ocorre erro de previsão,
muda a previsão na BHT para 11 (desvia).
Execução de BNEZ subseqüentes:
enquanto R1 > 0, desvia, previsão é correta
a previsão na BHT continua 11 (desvia).
FIM: Última execução de BNEZ:
como R1 = 0, não desvia, ocorre erro de previsão,
muda a previsão na BHT para 10 (desvia).
Na primeira execução do programa ocorrem 2 erros de previsão,
porém, a partir da próxima vez ocorre apenas 1 erro.
DAP.F96 7
Previsão com correlação entre loops
If (aa == 2)
If (bb == 2)
If (aa!=bb)
DSUBUI
BNEZ
DADD
L1: DSUBUI
BNEZ
DADD
L2: DSUBU
BEQZ
aa = 0;
bb = 0;
aa
R3,R1,#2
0
R3,L1
R1,R0,R0
bb
R3,R2,#2
R3,L2
R2,R0,R0
R3,R1,R2
R3,L3
; desvio b1 (aa!=2)
; aa = 0
; desvio b2 (bb !=2)
; bb=0
; R3 = aa-bb
; desvio b3 (aa==bb)
Se não ocorrem desvios b1 e b2 então ocorre desvio b3
O previsor faz a correlação entre loops!!
DAP.F96 8
Outro exemplo desvio com
correlação
if (d ==0) d = 1;
if (d ==1)
Código MIPS:
BNEZ
DADDIU
L1: DADDIU
BNEZ
...
L2:
d
0
R1,L1
R1,R0,#1
R3,R1,#-1
R3,L2
; desvio b1 (d!=0)
; d==0 , então d =1
; R3 = d -1
; desvio b2 (d!=1)
DAP.F96 9
Possível seqüência de execução
L1:
BNEZ
DADDIU
DADDIU
BNEZ
R1,L1
R1,R0,#1
R3,R1,#-1
R3,L2
; desvio b1 (d!= 0)
; d==0 , então d =1
; R3 = d - 1
; desvio b2 (d!=1)
...
L2:
d antes
do desvio b1
d==0?
b1
d antes
do desvio b2
d==1?
b2
0
sim
not taken
1
sim
not taken
1
não
taken
1
sim
not taken
2
não
taken
2
não
taken
DAP.F96 10
Comportamento de um previsor de 1 bit
BNEZ
DADDIU
DADDIU
BNEZ
L1:
Sequência
dada
d=?
R1,L1
R1,R0,#1
R3,R1,#-1
R3,L2
; desvio b1 (d!= 0)
; d==0 , então d =1
; R3 = d - 1
; desvio b2 (d!=1)
...
L2:
nova
previsão ação previsão
de b1 de b1 para b1
previsão ação
de b2 de b2
nova
previsão
para b2
2
NT
T
T
NT
T
T
0
T
NT
NT
T
NT
NT
2
NT
T
T
NT
T
T
0
T
NT
NT
T
NT
NT
Resultado: todas as previsões foram incorretas.
DAP.F96 11
Previsor de 1 bit com correlação
• Para cada desvio tem duas previsões (a/b), sendo que para um
determinado momento vale uma das previsões: a ou b
a - se o último desvio do programa é NT
b - se o último desvio do programa é T
notando-se que o último desvio do programa
normalmente não é o desvio que está sendo previsto, e sim, o
que está sendo correlacionado.
bits de
previsão
(a/b)
se o último desvio
do programa
foi NT usa-se o lado
(a )
se o último desvio
do programa
foi T usa-se o lado
( b)
NT/NT
previsão = NT
previsão = NT
NT/T
previsão = NT
previsão = T
T/NT
previsão = T
previsão = NT
T/T
previsão = T
previsão = T
DAP.F96 12
Sequência
dada
d=?
Aplicação no exemplo
nova
previsão ação previsão
de b1 de b1 para b1
previsão ação
de b2 de b2
nova
previsão
para b2
2
NT/NT
T
T/NT
NT/NT
T
NT/T
0
T/NT
NT
T/NT
NT/T
NT
NT/T
2
T/NT
T
T/NT
NT/T
T
NT/T
0
T/NT
NT
T/NT
NT/T
NT
NT/T
a/b – usa previsão a
a/b – usa previsão b
Resultado – apenas 2 erros de previsão iniciais.
DAP.F96 13
Previsão por torneio (Tournament predictor)
A forma mais comum para previsão multi-nível
LOCAL
GLOBAL
O contador é incrementado sempre que o previsor usado é correto
e outro incorreto, e decrementado caso contrário.
DAP.F96
Quando ambos estão corretos ou incorretos, mantém o estado.
14
Comparação entre os previsores
DAP.F96 15
Endereço de desvio junto com previsão
(Branch Target Buffer – BTB)
• Endereço da instrução (PC) é usado como índice do BTB
para obter a previsão e endereço de desvio
PC
Previsão de desvio
Previsão de PC para desvio
(endereço)
Não: previsão não-desvio
Desvio Previsto
(certo ou errado)
=
Sim: desvio, usar o PC
previsto
• Retorna o endereço da instrução prevista
DAP.F96 16
Suporte de HW para mais ILP
(Instruction Level Parallelism)
• Evita desvio em programas incluindo
operações (predicados) dentro das
instruções condicionais:
if (x) then A = B op C else NOP
– se (x) falso, então não ocorre nenhuma operação
– IA-64: tem campos de condição de 1-bit para
execução condicional de instruções
• Vantagem
x
A=
B op C
– Evita desvio
• Desvantagens
– Toma tempo (clock) mesmo que anulada
– Espera enquanto a condição é avaliada
– Condições complexas reduzem a eficiência,
implicam em atraso de pipeline
DAP.F96 17
Previsão Dinâmica de Desvio
Sumário
• Correlação: Desvios executados recentemente
correlacionados com o desvio seguinte
• Branch Target Buffer: inclui endereço de desvio &
previsão
• Execução com predicado pode reduzir o número de
desvios, número de erros em previsões
DAP.F96 18
Tornando CPI < 1: Emitindo
Múltiplas Instruções/Ciclo
• Duas variações
• Superscalar: variando número de instruções/ciclo (1 a 8),
escalados pelo compilador ou por HW (Tomasulo)
– IBM PowerPC, Sun UltraSparc, DEC Alpha, HP 8000
• Very Long Instruction Words - VLIW:
• instruções paralelizáveis (4 a16) escalados pelo
compilador;
• coloca as instruções dispostas como uma única
instrução longa
DAP.F96 19
Tornando CPI < 1: Emitindo
Múltiplas Instruções/Ciclo
• Superscalar MIPS: 2 instruções, 1 FP & 1 outra qualquer
– Busca (fetch) 64-bits/ciclo de clock (Int. e FP)
Tipo
Int. instruction
FP instruction
Int. instruction
FP instruction
Int. instruction
FP instruction
Estágios de Pipeline
IF
ID
EX MEM
IF
ID
EX MEM
IF
ID
EX
IF
ID
EX
IF
ID
IF
ID
WB
WB
MEM
MEM
EX
EX
WB
WB
MEM WB
MEM WB
DAP.F96 20
Revisão: desenrolamento de loops para
minimizar paradas em MIPS pipeline
1 Loop:
2
3
4
5
6
7
8
9
10
11
12
13
14
LD
LD
LD
LD
ADDD
ADDD
ADDD
ADDD
SD
SD
SD
SUBI
BNEZ
SD
F0,0(R1)
F6,-8(R1)
F10,-16(R1)
F14,-24(R1)
F4,F0,F2
F8,F6,F2
F12,F10,F2
F16,F14,F2
F4,0(R1)
F8,-8(R1)
F12,-16(R1)
R1,R1,#32
R1,LOOP
F16,8(R1)
; 8-32 = -24
14 ciclos de clock, ou 3.5 por iteração
CPI = 1
DAP.F96 21
Desenrolamento em
Superscalar
Integer instruction
Loop:
LD F0,0(R1)
LD F6,-8(R1)
LD F10,-16(R1)
LD F14,-24(R1)
LD F18,-32(R1)
SD F4,0(R1)
SD F8,-8(R1)
SD F12,-16(R1)
SD F16,-24(R1)
SUBI R1,R1,#40
BNEZ R1,LOOP
SD F20,-32(R1)
LD para ADDD: 2 Ciclos
ADDD para SD: 2 Ciclos
FP instruction
ADDD F4,F0,F2
ADDD F8,F6,F2
ADDD F12,F10,F2
ADDD F16,F14,F2
ADDD F20,F18,F2
• Desenrola 5 vezes para evitar atrasos
• 12 clocks, ou 2.4 clocks por iteração
• CPI = 12 / 17 = ~0.7
Clock cycle
1
2
3
4
5
6
7
8
9
10
11
12
DAP.F96 22
Desafio de Múltipla Emissão
para superescalar
• Enquanto a separação em Inteiros e FPs seja simples em HW, o CPI de
0.5 é possível somente para programas com:
– Exatamente 50% de operações FP
– Sem conflitos
• É difícil: emitir ao mesmo tempo, mais que duas instruções
• É também difícil decidir se 2 instruções escalares podem ser emitidas
ao mesmo tempo => examinar 2 opcodes, 6 especificadores de
registradores,...
DAP.F96 23
VLIW (Very Large Instruction Word)
– A palavra de instrução longa tem espaço para muitas
operações
– Todas as operações que o compilador coloca na palavra de
instrução longa são independentes => execução em paralelo
– Ex.: 2 operações inteiras, 2 operações FP, 2 refer. memória, 1
desvio
» 16 a 24 bits por campo => 7*16 ou 112 bits a 7*24 ou 168
bits
Necessita de técnicas de compilação que faz a
escalação passando por vários desvios
DAP.F96 24
Desenrolamento em VLIW
Memory
reference 1
Memory
reference 2
FP
operation 1
FP
op. 2
Int. op/
branch
Clock
LD F0,0(R1)
LD F6,-8(R1)
LD F10,-16(R1) LD F14,-24(R1)
LD F18,-32(R1) LD F22,-40(R1) ADDD F4,F0,F2
ADDD F8,F6,F2
LD F26,-48(R1)
ADDD F12,F10,F2 ADDD F16,F14,F2
ADDD F20,F18,F2 ADDD F24,F22,F2
SD F4,0(R1)
SD F8,-8(R1) ADDD F28,F26,F2
SD F12,-16(R1) SD F16,-24(R1)
SD F20,-32(R1) SD F24,-40(R1)
SUBI R1,R1,#48
SD F28,-0(R1)
BNEZ R1,LOOP
1
2
3
4
5
6
7
8
9
Desenrola 7 vezes para evitar atrasos
7 resultados em 9 clocks, ou 1.3 clocks por iteração
CPI = 23/9 = ~0.39
Nota: Necessita mais registradores em VLIW (15 vs. 6 em
Superescalar)
DAP.F96 25
Geração de código para VLIW Trace Scheduling
• Dois passos:
– Seleção de Traço (Trace)
» Encontrar uma sequência provável de blocos
básicos, traço, de uma longa sequência de
códigos
– Compactação de Traço
» Espremer o traço em algumas instruções VLIW
» Necessita de código alternativo no caso de erro
de previsão de código
DAP.F96 26
Superscalar
• Tamanho de código
menor
• Compatibilidade
através de gerações
de hardware
vs.
VLIW
• Hardware Simplificado
para decodificação e
emissão de instruções
• Sem conflito entre as
instruções
• Mais registradores
DAP.F96 27
Software Pipelining
• Observação: se iterações de loops são independentes,
pode-se obter mais ILP tomando instruções de
diferentes iterações
• Software pipelining: reorganiza loops tal que cada
iteração seja composta de instruções de diferentes
iterações do loop original
Iteration
0
Iteration
Iteration
1
2
Iteration
3
Iteration
4
Softwarepipelined
iteration
DAP.F96 28
Exemplo de Software Pipelining
ITERAÇÃO 0
ITERAÇÃO 1
1
2
3
4
5
LD
ADDD
SD
SUBI
BNEZ
F0,0(R1)
F4,F0,F2
F0,0(R1)
R1,R1,#8
R1,LOOP
ITERAÇÃO 2
1
2
3
4
5
LD
ADDD
SD
SUBI
BNEZ
F0,0(R1)
F4,F0,F2
F0,0(R1)
R1,R1,#8
R1,LOOP
1
2
3
4
5
LD
ADDD
SD
SUBI
BNEZ
F0,0(R1)
F4,F0,F2
F0,0(R1)
R1,R1,#8
R1,LOOP
Iteration
0
Iteration
Iteration
1
2
Iteration
3
Iteration
4
Softwarepipelined
iteration
DAP.F96 29
Exemplo de Software Pipelining
Ops. sobrepostas
Antes: desenrolado 3 vezes Após: Software Pipeline
1 LD
F0,0(R1)
1 SD
F4,0(R1); Stores M[i]
2 ADDD F4,F0,F2
2 ADDD F4,F0,F2 ; Adds to M[i-1]
3 SD
F4,0(R1)
3 LD
F0,-16(R1); Loads M[i-2]
4 LD
F6,-8(R1)
4 SUBI R1,R1,#8
5 ADDD F8,F6,F2
5 BNEZ R1,LOOP
6 SD
F8,-8(R1)
7 LD
F10,-16(R1)
SW Pipeline
8 ADDD F12,F10,F2
9 SD
F12,-16(R1)
10 SUBI R1,R1,#24
Tempo
11 BNEZ R1,LOOP
Loop Unrolled
Tempo
DAP.F96 30
Intel/HP-IA-64 (ITANIUM )
“Explicitly Parallel Instruction
Computer (EPIC)”
• Explora a arquitetura VLIW, deixando a detecção do ILP(Instruction Level
Parallelism) para os compiladores
• 3 Instruções em “grupos” de 128 bits; campos determinam se as
instruções são dependentes ou independentes
• 64 registradores inteiros + 64 registradores ponto flutuante
• Hardware checa dependências
• Execução com Predicado => 40% menos previsões errôneas
• IA-64 : nome da arquitetura do conjunto de instruções
• Itanium - implementação
• Suporte para instruções IA-32, porém com desempenho menor que as
últimas versões do Pentium, por explorarem mais o desempenho nas
instruções EPIC (VLIW) e não terem suportes de ILP por hardware.
DAP.F96 31
Pentium 4 640 na tecnologia de
90 nm (2004)
recursos
tamanho
comentários
BTB de front-end
4K
Trace Cache
12K uops
Previsão de desvio para
instr. IA32
Cache de rastreio
BTB de trace cache
2K
Registradores para
renomear
128
Unidades funcionais
2 ALUs simples, ALU
complexa, load, store,
move de PF, aritm.PF
Cache de dados L1
16 Kb, associativo de 8
vias, blocos de 64 bytes
Cache L2
2Mb, associativo de 8
bias, blocos de 128
Previsão de desvio para
uops
128 uops podem estar
em execução com até 48
loads e 32 stores
ALU simples executam
no dobro da taxa de
clock, aceitando até 2
uops a cada ciclo
Write through
Write back
DAP.F96 32
Pentium 4
DAP.F96 33
resumo
DAP.F96 34
SPEC benchmark - INTEGER
DAP.F96 35
SPEC benchmark – Ponto
Flutuante
DAP.F96 36
Análise de desempenho do
Pentium 4
inteiros
Ponto flutuante
DAP.F96 37
Erro de especulação em
instruções uop
inteiros
Ponto flutuante
DAP.F96 38
Falta em caches L1 e L2 por
1000 instruções
inteiros
Cache L1
Cache L2
Ponto flutuante
DAP.F96 39
CPI
inteiros
Ponto flutuante
DAP.F96 40
Pentium 4 x AMD Opteron
inteiros
Ponto flutuante
DAP.F96 41
Desempenho do AMD Opteron x
Pentium 4
inteiros
Ponto flutuante
DAP.F96 42
IBM Power5 x Pentium 4
Ponto flutuante
inteiros
DAP.F96 43
Processador ideal
• Todas as restrições de ILP são removidas
• 1- renomeação de registrador – um número infinito de
registradores virtuais à disposição, por isso todos os WAW e
WAR são evitados e um número infinito de instruções pode iniciar
simultaneamente
• 2- previsão de desvio – a previsão é perfeita
• 3- previsão de salto – todos os saltos são previstos
• 4- análise de alias de endereço de memória - todos os endereços
de memória são conhecidos, e um load pode ser feito antes de um
store, desde que os endereços não sejam iguais.
• 5- caches perfeitos – todos os endereços de memória usam 1
ciclo.
DAP.F96 44
ILP num processador ideal
inteiros
Ponto flututante
DAP.F96 45
O que um processador ideal precisa fazer
• 1- olhar muito adiante para encontrar um conjunto de instruções a
despachar (emitir), prevendo todos os desvios perfeitamente
• 2- renomear todos os usos de registrador para evitar WAR e WAW
• 3- determinar se existem dependências de dados entre as
instruções no pacote de emissão; se houver renomear
adequadamente
• 4- determinar se existe alguma dependência de memória entre as
instruções sendo emitidas e tratar delas adequadamente
• 5- oferecer unidades funcionais replicadas suficientes para que
todas as instruções prontas sejam emitidas
DAP.F96 46
Efeitos da limitação da janela
inteiros
Ponto flutuante
DAP.F96 47
Efeitos dos tipos de previsão de desvios
DAP.F96 48
Redução do paralelismo pelo número de registradores
para renomeação
Fig.3.5
DAP.F96 49
Efeito de níveis variados de análise
de alias sobre programas
DAP.F96 50