Predição de saltos

Um beq ainda está em ID e a pipeline precisa de escolher a próxima instrução. O salto decide entre PC+4 e o destino. Enquanto a condição não está resolvida, o processador pode esperar ou seguir um caminho previsto. Se errar, descarta as instruções mais novas desse caminho.

Onde se resolve o salto

Fixa a fase em que o PC pode mudar, não apenas a que calcula a condição; a tabela usa cinco fases e conta apenas a penalidade de uma previsão errada, sem conflitos de operandos:

Modelo	Redirecionar em	Penalidade
Decisão básica	MEM	3 ciclos
Decisão antecipada	ID	1 ciclo

No modelo MEM, um branch em IF 1, ID 2, EX 3, MEM 4 deixa três instruções mais novas em EX, ID, IF no ciclo 4. Se a previsão falha, a primeira instrução correta só é obtida no ciclo 5. Se se espera sempre pelo branch, paga-se essa espera em todos os branches; se se prevê, paga-se só nos erros.

Calcular o CPI de controlo

Com fração de branches $b$, probabilidade de erro $e$ e penalidade $p$:

$$CPI=CPI_{\rm sem\ erros}+bep.$$

Se 20% das instruções são branches, 60% são tomados e a previsão é sempre não tomado, $e=0,60$. Para base 1 e resolução MEM: $CPI=1+0,20\times0,60\times3=1,36$. Se esperasse sem predição, seria $1+0,20\times3=1,60$.

Um preditor com 90% de acertos dá $e=0,10$, não 0,90. Os casos devem contar também saltos incondicionais se o modelo lhes atribuir uma penalidade; não mistures as suas frequências com a dos condicionais sem indicação.

Decisão em ID e dependências

Antecipar a comparação exige comparar registos e calcular o alvo em ID. Pode reduzir a penalidade de controlo e aumentar paragens de dados.

add t0,t1,t2
beq t0,zero,L

O add calcula em EX 3. O branch está em ID 3 e precisa do valor antes de terminar esse ciclo. Com um atalho de EX/MEM para o comparador ID, espera um ciclo e compara em ID 4. Um atalho apenas para EX não resolve esse uso.

Se a primeira instrução for lw, o dado chega no fim de MEM 4. Com o caminho adequado de MEM/WB para ID e a regra WB-primeiro/ID-depois, o branch compara em ID 5: duas paragens. A penalidade de erro de 1 ciclo acrescenta-se à dependência, se ambas ocorrerem.

Um bit de história

Uma BHT guarda estado associado ao endereço de cada branch, normalmente indexado por bits baixos do PC, excluindo os bits de alinhamento. Endereços diferentes podem partilhar uma entrada e interferir. A BHT prevê a direção; obter rapidamente o endereço do alvo pode exigir uma estrutura distinta, como uma BTB.

O preditor de 1 bit prevê o último resultado: T para tomado, N para não tomado. Depois do branch, substitui o bit pelo resultado real.

Para dois percursos do mesmo ciclo, resultados T T T N T T T N, e estado inicial T: erra na saída do primeiro ciclo, na reentrada do segundo e na segunda saída. São 3 erros em 8 branches. Em regime repetido são 2 erros por percurso, por isso o arranque escolhido pode mudar a primeira contagem.

Dois bits com histerese

A máquina da apresentação e o contador saturante têm quatro estados, mas transições diferentes. Neste primeiro modelo, 01 + T leva a 11 e 10 + N leva a 00. A previsão usa o estado anterior; só depois do resultado se atualiza o estado.

Usa dois estados que preveem T e dois que preveem N. 00 e 11 são previsões fortes; 01 e 10 são fracas. Um resultado contrário a uma previsão forte muda-a para fraca, mas conserva a direção prevista para a próxima ocorrência. Se o resultado contrário se repetir no estado fraco, muda a direção:

Estado	Prevê	Se N	Se T
00	N	00	01
01	N	00	11
10	T	00	11
11	T	10	11

Para T T T N T T T N, partindo de 11, os estados após cada branch são 11 11 11 10 11 11 11 10. Só as duas saídas são mal previstas: 2 erros em 8.

O contador saturante é outro modelo

Um contador de 0 a 3 prevê N abaixo de 2 e T a partir de 2; incrementa por T e decrementa por N, sem passar os extremos. Difere da tabela anterior em 01+T→10 e 10+N→01. Esta é a forma do preditor de 2 bits mais comum nos manuais; a máquina anterior, com outra transição nesses dois casos, é a da apresentação. Nunca substituas uma máquina de estados pela outra só porque ambas têm 2 bits. Nunca substituas uma máquina de estados pela outra só porque ambas têm 2 bits.

Para resultados alternados e alguns estados iniciais, as contagens podem divergir. Nunca substituas uma máquina de estados pela outra só porque ambas têm 2 bits.

Partindo de 01, compara a sequência alternada T N T N T N. Em cada célula, aparece estado anterior, previsão e estado seguinte.

Resultado real	Histerese	Saturante
T	01, N, erro, 11	01, N, erro, 10
N	11, T, erro, 10	10, T, erro, 01
T	10, T, acerto, 11	01, N, erro, 10
N	11, T, erro, 10	10, T, erro, 01
T	10, T, acerto, 11	01, N, erro, 10
N	11, T, erro, 10	10, T, erro, 01

A histerese erra 4 das 6 previsões, incluindo os dois erros iniciais. Depois do arranque, erra metade neste padrão. O saturante oscila entre 01 e 10 e erra as seis previsões. Uma taxa de regime não substitui a contagem da janela finita.

Ao resolver um traço, escreve estado anterior, previsão, resultado, erro e estado seguinte em colunas. Só depois calcula a taxa de erro e o CPI; isso evita atualizar o estado antes de prever.