Branch prediction

Branch prediction são conjuntos de técnicas implementadas em hardware ou software, que têm o objetivo de reduzir os conflitos de controle em processadores de arquitetura Pipeline, através da previsão correta de que os desvios condicionais vão desviar ou não, reduzindo atrasos no fluxo de instruções posteriores aos desvios, conhecidos como bolhas no pipeline. Quando ocorre qualquer desvio, as instruções anteriores a de desvios devem ser anuladas. Tal processo recebe o nome de Flush, onde registradores entre os estágios e sinais de controle são responsáveis por enviar instruções NOPs ou adiantamento de outras.

Hierarquia conflitos de controle

Apesar dos conflitos de controle forem menores que os conflitos de dados, quase 20% das instruções são de desvio condicional, tornando-se crítico alternativas para amenizar os gargalos, principalmente quando há muitas instruções no mesmo ciclo de clock. Para isto, existem as chamadas técnicas de execução especulativa que, com base em probabilidades de ocorrência ou estratégias, permitem que haja uma previsão se haverá desvio ou não, ou até mesmo trocar de ordem algumas instruções, sem alterar o resultado final do programa, para quando surgir uma condição de desvio, a mesma seja resolvida com o mínimo possível de bolhas no Pipeline. O conjunto de técnicas dividem-se em técnicas de software ou técnicas de hardware

Técnicas de software

Em geral, neste tipo de técnica o hardware, após constatar que houve um desvio condicional, pausa a instrução de desvio e delega ao software, durante a compilação, reorganizar quais das instruções serão antecipadas à instrução de desvio. Assume-se que todas as técnicas de software são estáticas, uma vez que a estrutura não é alterada no próprio código, e sim virtualmente pelo compilador. Algumas das principais técnicas são:

1. Delayed Branch : desde que não haja Relações de dependência entre as instruções, o compilador tenta organizá-las da maneira mais adequada para reduzir as bolhas no pipeline.Consiste em antecipar as instruções que estão antes do desvio. Compiladores conseguem preencher com instruções até 50% dos espaços após o desvio.
2. Fetch Taken and Not-Taken Path: técnica difere de Delayed Branch no fato de que, em vez de adiar instruções que estão antes do desvio condicional, executar também instruções que estão após o desvio, desde que não haja problemas de dependências. Executa as duas possibilidades, do desvio acontecer ou não, os dois fluxos ao mesmo tempo. Não tem implementações pois a complexidade de hardware e custo seriam muito grandes.
3. Branch Folding(desvios de ciclo zero): usada em certas arquiteturas que possuem instruções extras chamadas flags de condição, para identificar o resultado do desvio no momento em que o mesmo é encontrado, através de comparação entre registradores ou operações aritméticas, fazendo com que o fluxo de controle seja alterado pelo compilador, caso necessário, a tempo de evitar ciclos desperdiçados. Processadores CRISP(AT&T), PowerPC 601 e IBM RISC System 6000 são exemplos de arquiteturas com branch folding.
4. In-line : quando as instruções de desvios estão dentro de chamada ou de retorno de funções torna-se difícil encontrar uma previsão eficiente, pois podem ser chamadas de diferentes pontos do programa. A técnica in-line consiste em substituir as chamadas de funções pelo conteúdo específico de cada uma, através da decodificação, onde é possível saber o conteúdo específico de cada instrução, onde o compilador, em caso de instruções redundantes, o procedimento de passagem de parâmetros não precise ser executado a cada chamada para a função, diminuindo o tempo de execução das instruções, apesar de que o código tem seu tamanho aumentado.
5. Desenrolamento de loops: técnica utilizada em instruções de desvios condicionais que estão dentro de um laço de repetição, trocando o laço quando possível pelo próprio conteúdo existente nele (código-objeto). Informações do conteúdo interno dos laços e número de repetições, fornecidos pela decodificação e unidade de controle, permitem redução de tempo de processamento, eliminando instruções de load/store para saber qual conteúdo está nos registradores.

Técnicas de hardware

O que diferenciam das técnicas de software, é que estas atuam em tempo de execução do programa enquanto as outras, em tempo de compilação. Podem ser de dois tipos, previsão estática, onde a previsão é feita na projeção da arquitetura, através de testes (benchmarks), ou previsão dinâmica, em que a previsão é feita com base em informações recentes das últimas instruções realizadas, para usá-las posteriormente. Em caso de ser a primeira instrução de desvio do pipeline, a previsão é de acordo com uma das técnicas estáticas vistas anteriormente.

Com tipo de previsão estática

1. Assumindo que desvio sempre ocorrerá: assume-se que o desvio sempre ocorrerá, apresentando as mesmas características de um desvio incondicional. Um computador que utiliza esta técnica é o IBM 360/91.
2. Assumindo que desvio nunca ocorrerá: assume-se que não ocorrerá qualquer desvio, como se ele não existisse. Processadores com este tipo são mais comuns do que o anterior, sendo chamados de look-ahead processors (processadores de olhar para frente), indicando que estão sempre preparados para manter os ciclos de instrução sequencialmente. Como exemplo dessa arquitetura, tem-se o VAX-11 VAX 11/780 e também as primeiras implementações de SPARC e MIPS (duas das primeiras arquiteturas RISC comerciais)
3. Desvia de acordo com o código da operação: o processo que determina se vai desviar ou não é baseado em testes (benchmarks) que determinam, para cada arquitetura, a maior probabilidade de ocorrência baseados nas frequências obtidas nos testes, ainda que cada arquitetura apresenta tamanhos de instruções e opcodes diferentes, onde é possível identificar a tendência de desvio mais provável. Uma das maneiras de implementação desta tecnologia é colocar uma memória ROM dentro do processador para determinar o tipo de previsão que será adotado. A pós constatar que é um desvio condicional, consulta esta memória (que é somente de leitura por ser ROM) para determinar, com base nas instruções que estão no pipeline, se a previsão será de desvio ou não)

Com tipo de previsão dinâmica

1. Previsão determinada pela tabela de história de desvios: este tipo de técnica consiste em armazenar os últimos resultados de desvios em uma tabela associativa chamada tabela de história dos desvios (Branch History Table ou BHT), localizada no interior do processador, que é atualizada a cada instrução de desvio, contendo dois campos, o endereço dos últimos desvios e o histórico que identifica as últimas execuções.
2. Previsão via tabela com alvos dos desvios (Branch _target Buffer ou BTB): consiste eu uma tabela mais aprimorada que a BHT permitindo, em caso de desvio não tomado, facilite a busca pela próxima instrução e diminua os ciclos de clock utilizados. Além dos 2 campos da BHT, possui um outro, que pode ser de duas maneiras:
   1. Campo extra com endereço da próxima instrução: cada linha da tabela contém o endereço do desvio, histórico que identifica as últimas execuções e o endereço da instrução sucessora, para em caso de não desviar, prosseguir fluxo sequencialmente.
   2. Campo extra com a próxima instrução: cada linha da tabela contém o endereço do desvio, histórico que identifica as últimas execuções e a própria instrução sucessora para o caso do desvio não ocorrer não precise buscar a próxima instrução, que já estará na tabela, adiantando um ciclo de instrução.
3. Previsão determinada pela história do último ou últimos 2 casos de desvio: também ocupa uma BHT, porém a mesma é utilizada para armazenar o endereço do desvio e bit ou bits extras contendo as últimas informações referentes aos desvios.
   1. Previsão com mecanismo de 1 bit: após decodificar e constatar que é uma instrução de desvio, usa-se os bits menos significativos para decidir se o desvio será tomado (bit=1) ou não (bit=0) através da busca na BHT do endereço da mesma e caso na última instrução o desvio foi executado. Se o resultado do bit da tabela é diferente do bit da instrução, atualiza a tabela. Esta técnica deixa a desejar, pois em caso de laços de repetição a previsão vai errar duas vezes, no final do laço onde o bit da tabela estará em 0, indicando que não vai desviar sendo que o desvio irá acontecer e no início do laço, quando na tabela vai conter bit=1 dizendo que vai desviar, sendo que a instrução permanecerá sequencialmente.
   2. Previsão com mecanismo de 2 bits: o processo é quase o mesmo do anterior, com a diferença que, há 2 bits na BHT, sendo o primeiro indicando o resultado da previsão, o que provavelmente irá acontecer e o segundo bit o que aconteceu na última execução (bit 1 se desviou e bit 0 se não desviou), fornece uma segunda oportunidade de acerto. A taxa média de acertos passa de 70% para 90% com esta técnica.
4. Previsão usando contador saturado: outra alternativa para aumentar a taxa de acertos é a substituição da BHT por contadores de armazenamento dos bits de história em uma tabela hash com 16 entradas. Se contador negativo, desvio será tomado e se contador positivo, desvio não será tomado. Após a instrução de desvio, contadores são atualizados (decrementados ou incrementados).

Previsão 1 bit