Técnicas de Predição de
Desvios
MO401 -Arquitetura
de Computadores
Jaudete Daltio
RA 049240
Universidade Estadual de Campinas – Instituto de Computação
Motivação
 Exploração
de paralelismo aumenta o
desempenho dos processadores
 Retardo causado pelas instruções de
desvio: “Conflitos de Controle”
 Técnicas que reduzam as penalidades
 Perda de desempenho caso a previsão
seja incorreta
Técnicas de Predição de Desvio
Tipos de Previsão
 Em
Software
 Durante
a compilação do programa de
aplicação
 Em
Hardware
 Durante
a execução do programa de
aplicação
 Estáticas e Dinâmicas
Técnicas de Predição de Desvio
Predição em Software
 Delayed
Branch
-instrução de desvio
-sucessor seqüencial
-destino de desvio
Tornar a instrução do sucessor seqüencial
válida e útil – limitação de possibilidades
 Implementada em RISC, IBM 801, RISC I de
Berkeley, i860 da Intel, MIPSStanford

Técnicas de Predição de Desvio
Predição em Software
Técnicas de Predição de Desvio
Predição em Software
 Branch
Folding
 Cada
instrução inclui o endereço de sua
sucessora
 Emprega-se uma técnica estática para
selecionar o destino
 O endereço alternativo é armazenado na
cache para o caso da previsão incorreta
 Implementada em CRISP da AT&T,
PowerPC, IBM RISC System 6000
Técnicas de Predição de Desvio
Predição em Software
 In
Line
 Substitui
chamadas de sub-rotinas pelo
código objeto
 Vantagem: elimina passagem de
parâmetros e chamadas e retornos de
procedimentos.
 Desvantagem: aumento do código
objeto gerado pelo compilador
Técnicas de Predição de Desvio
Predição em Hardware
 Estáticas
 Baseiam-se
em definições feitas na
concepção de um novo processador
 Dinâmicas
 Baseiam-se
em informações coletadas
em tempo de execução
Técnicas de Predição de Desvio
Predição Estática
 Sempre
tomado
 Implementada
 Nunca
pelo IBM 360/91
tomado
 Implementada
pelo i960CA, MC68020 e
o VAX 11/780
 Média de previsões incorretas igual à
freqüência de desvios seguidos (ou não)
 Código
do comando de desvio
Técnicas de Predição de Desvio
Predição Dinâmica
 Histórico
do Desvio
 Buffer
ou BHT (Branch History Table)
 Verificar o comportamento do desvio
nas execuções mais recentes
 Considerar o número de entradas da
BHT e tamanho do histórico
armazenado
Técnicas de Predição de Desvio
Predição Dinâmica
Técnicas de Predição de Desvio
Predição Dinâmica
 Contadores
 Associa
Saturados
aos desvios um contador de
controle
 Incrementado ao acerto e decrementado
caso contrário
 Restrição ao tamanho dos contadores
•Neutralizar o efeito de outra instrução
mapeada na mesma entrada
Técnicas de Predição de Desvio
Predição Dinâmica
 Tabela
de Alvos dos Desvios
 BTB
(Branch Target Buffer) contém os
alvos das instruções de desvio
 mais eficiente que o BHT: mais
informações sobre a instrução alvo
 A antecipação reduz a introdução de
instruções indevidamente no pipeline
 Implementada pelo microprocessador
Pentium, março/93
Técnicas de Predição de Desvio
Predição Dinâmica
 Dois
 1º
Níveis de História
nível: BHR (Branch History Register)
•Informações globais originadas por
diferentes instruções de desvio
 2º
nível: PHT (Patttern History Table)
•Associados ao comportamento de uma
instrução de desvio específica
 Implementada
no Pentium Pro
Técnicas de Predição de Desvio
Predição Dinâmica
Técnicas de Predição de Desvio
Predição Dinâmica
 Híbridos
 Combina
diferentes vantagens de outras
técnicas, operadas em paralelo
 A técnica com maior probabilidade de
acerto fornece o resultado
 Podendo atingir patamares superiores a
99%
Técnicas de Predição de Desvio
Predição Dinâmica
Técnicas de Predição de Desvio
Conclusões
 Desempenho
das técnicas relaciona-se
diretamente com a aplicação
 A eficácia não depende apenas da
previsão - custo da previsão incorreta
 Melhores desempenhos
 Combinações
de técnicas de Hardware e
Software
 Preditores híbridos
Técnicas de Predição de Desvio