Universidade Estadual de Campinas – Instituto de Computação

Técnicas de Predição Técnicas de Predição de Desviosde Desvios

MO401 -Arquitetura de Computadores

Jaudete DaltioRA 049240

Técnicas de Predição de Desvio

MotivaçãoMotivaçã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ãoTipos 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 Predição em SoftwareSoftware 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 Predição em SoftwareSoftware

Técnicas de Predição de Desvio

Predição em Predição em SoftwareSoftware 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 Predição em SoftwareSoftware 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 Predição em HardwareHardware 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áticaPredição Estática Sempre tomado

Implementada pelo IBM 360/91 Nunca 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âmicaPrediçã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âmicaPredição Dinâmica

Técnicas de Predição de Desvio

Predição DinâmicaPredição Dinâmica Contadores Saturados

Associa 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âmicaPrediçã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âmicaPredição Dinâmica Dois Níveis de História

1º 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âmicaPredição Dinâmica

Técnicas de Predição de Desvio

Predição DinâmicaPrediçã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âmicaPredição Dinâmica

Técnicas de Predição de Desvio

ConclusõesConclusõ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