Branch prediction sao conjuntos de tecnicas implementadas em hardware ou software , que tem o objetivo de reduzir os conflitos de controle em processadores de arquitetura Pipeline , atraves da previsao correta de que os desvios condicionais vao desviar ou nao, reduzindo atrasos no fluxo de instrucoes posteriores aos desvios, conhecidos como bolhas no pipeline. Quando ocorre qualquer desvio, as instrucoes anteriores a de desvios devem ser anuladas. Tal processo recebe o nome de Flush , onde registradores entre os estagios e sinais de controle sao responsaveis por enviar instrucoes NOPs ou adiantamento de outras.

Apesar dos conflitos de controle forem menores que os conflitos de dados, quase 20% das instrucoes sao de desvio condicional, tornando-se critico alternativas para amenizar os gargalos, principalmente quando ha muitas instrucoes no mesmo ciclo de clock . Para isto, existem as chamadas tecnicas de execucao especulativa que, com base em probabilidades de ocorrencia ou estrategias, permitem que haja uma previsao se havera desvio ou nao, ou ate mesmo trocar de ordem algumas instrucoes , sem alterar o resultado final do programa, para quando surgir uma condicao de desvio, a mesma seja resolvida com o minimo possivel de bolhas no Pipeline . O conjunto de tecnicas dividem-se em tecnicas de software ou tecnicas de hardware ^{[ 1 ]}

Tecnicas de software [ editar | editar codigo-fonte ]

Em geral, neste tipo de tecnica o hardware, apos constatar que houve um desvio condicional, pausa a instrucao de desvio e delega ao software, durante a compilacao, reorganizar quais das instrucoes serao antecipadas a instrucao de desvio. Assume-se que todas as tecnicas de software sao estaticas, uma vez que a estrutura nao e alterada no proprio codigo, e sim virtualmente pelo compilador. Algumas das principais tecnicas sao:

1. Delayed Branch : desde que nao haja Relacoes de dependencia entre as instrucoes, o compilador tenta organiza-las da maneira mais adequada para reduzir as bolhas no pipeline .Consiste em antecipar as instrucoes que estao antes do desvio. Compiladores conseguem preencher com instrucoes ate 50% dos espacos apos o desvio.
2. Fetch Taken and Not-Taken Path : tecnica difere de Delayed Branch no fato de que, em vez de adiar instrucoes que estao antes do desvio condicional, executar tambem instrucoes que estao apos o desvio, desde que nao haja problemas de dependencias. Executa as duas possibilidades, do desvio acontecer ou nao, os dois fluxos ao mesmo tempo. Nao tem implementacoes pois a complexidade de hardware e custo seriam muito grandes.
3. Branch Folding (desvios de ciclo zero): usada em certas arquiteturas que possuem instrucoes extras chamadas flags de condicao, para identificar o resultado do desvio no momento em que o mesmo e encontrado, atraves de comparacao entre registradores ou operacoes aritmeticas, fazendo com que o fluxo de controle seja alterado pelo compilador, caso necessario, a tempo de evitar ciclos desperdicados. Processadores CRISP( AT&T ), PowerPC 601 e IBM RISC System 6000 sao exemplos de arquiteturas com branch folding.
4. In-line  : quando as instrucoes de desvios estao dentro de chamada ou de retorno de funcoes torna-se dificil encontrar uma previsao eficiente, pois podem ser chamadas de diferentes pontos do programa. A tecnica in-line consiste em substituir as chamadas de funcoes pelo conteudo especifico de cada uma, atraves da decodificacao, onde e possivel saber o conteudo especifico de cada instrucao, onde o compilador, em caso de instrucoes redundantes, o procedimento de passagem de parametros nao precise ser executado a cada chamada para a funcao, diminuindo o tempo de execucao das instrucoes, apesar de que o codigo tem seu tamanho aumentado.
5. Desenrolamento de loops : tecnica utilizada em instrucoes de desvios condicionais que estao dentro de um laco de repeticao, trocando o laco quando possivel pelo proprio conteudo existente nele (codigo-objeto). Informacoes do conteudo interno dos lacos e numero de repeticoes, fornecidos pela decodificacao e unidade de controle , permitem reducao de tempo de processamento, eliminando instrucoes de load/store para saber qual conteudo esta nos registradores.

Tecnicas de hardware [ editar | editar codigo-fonte ]

O que diferenciam das tecnicas de software, e que estas atuam em tempo de execucao do programa enquanto as outras, em tempo de compilacao . Podem ser de dois tipos, previsao estatica, onde a previsao e feita na projecao da arquitetura, atraves de testes (benchmarks), ou previsao dinamica, em que a previsao e feita com base em informacoes recentes das ultimas instrucoes realizadas, para usa-las posteriormente. Em caso de ser a primeira instrucao de desvio do pipeline, a previsao e de acordo com uma das tecnicas estaticas vistas anteriormente.

Com tipo de previsao estatica [ editar | editar codigo-fonte ]

1. Assumindo que desvio sempre ocorrera : assume-se que o desvio sempre ocorrera, apresentando as mesmas caracteristicas de um desvio incondicional. Um computador que utiliza esta tecnica e o IBM 360/91. ^{[ 2 ] [ 3 ]}
2. Assumindo que desvio nunca ocorrera : assume-se que nao ocorrera qualquer desvio, como se ele nao existisse. Processadores com este tipo sao mais comuns do que o anterior, sendo chamados de look-ahead processors (processadores de olhar para frente), indicando que estao sempre preparados para manter os ciclos de instrucao sequencialmente. Como exemplo dessa arquitetura, tem-se o VAX-11 VAX 11/780 e tambem as primeiras implementacoes de SPARC e MIPS (duas das primeiras arquiteturas RISC comerciais)
3. Desvia de acordo com o codigo da operacao : o processo que determina se vai desviar ou nao e baseado em testes ( benchmarks ) que determinam, para cada arquitetura, a maior probabilidade de ocorrencia baseados nas frequencias obtidas nos testes, ainda que cada arquitetura apresenta tamanhos de instrucoes e opcodes diferentes, onde e possivel identificar a tendencia de desvio mais provavel. Uma das maneiras de implementacao desta tecnologia e colocar uma memoria ROM dentro do processador para determinar o tipo de previsao que sera adotado. A pos constatar que e um desvio condicional, consulta esta memoria (que e somente de leitura por ser ROM) para determinar, com base nas instrucoes que estao no pipeline, se a previsao sera de desvio ou nao)

Com tipo de previsao dinamica [ editar | editar codigo-fonte ]

1. Previsao determinada pela tabela de historia de desvios : este tipo de tecnica consiste em armazenar os ultimos resultados de desvios em uma tabela associativa chamada tabela de historia dos desvios ( Branch History Table ou BHT), localizada no interior do processador, que e atualizada a cada instrucao de desvio, contendo dois campos, o endereco dos ultimos desvios e o historico que identifica as ultimas execucoes. ^{[ 4 ]}
2. Previsao 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 nao tomado, facilite a busca pela proxima instrucao e diminua os ciclos de clock utilizados. Alem dos 2 campos da BHT, possui um outro, que pode ser de duas maneiras:
   1. Campo extra com endereco da proxima instrucao : cada linha da tabela contem o endereco do desvio, historico que identifica as ultimas execucoes e o endereco da instrucao sucessora, para em caso de nao desviar, prosseguir fluxo sequencialmente.
   2. Campo extra com a proxima instrucao : cada linha da tabela contem o endereco do desvio, historico que identifica as ultimas execucoes e a propria instrucao sucessora para o caso do desvio nao ocorrer nao precise buscar a proxima instrucao, que ja estara na tabela, adiantando um ciclo de instrucao.
3. Previsao determinada pela historia do ultimo ou ultimos 2 casos de desvio : tambem ocupa uma BHT, porem a mesma e utilizada para armazenar o endereco do desvio e bit ou bits extras contendo as ultimas informacoes referentes aos desvios.
   1. Previsao com mecanismo de 1 bit : apos decodificar e constatar que e uma instrucao de desvio, usa-se os bits menos significativos para decidir se o desvio sera tomado (bit=1) ou nao (bit=0) atraves da busca na BHT do endereco da mesma e caso na ultima instrucao o desvio foi executado. Se o resultado do bit da tabela e diferente do bit da instrucao, atualiza a tabela. Esta tecnica deixa a desejar, pois em caso de lacos de repeticao a previsao vai errar duas vezes, no final do laco onde o bit da tabela estara em 0, indicando que nao vai desviar sendo que o desvio ira acontecer e no inicio do laco, quando na tabela vai conter bit=1 dizendo que vai desviar, sendo que a instrucao permanecera sequencialmente.
   2. Previsao com mecanismo de 2 bits : o processo e quase o mesmo do anterior, com a diferenca que, ha 2 bits na BHT, sendo o primeiro indicando o resultado da previsao, o que provavelmente ira acontecer e o segundo bit o que aconteceu na ultima execucao (bit 1 se desviou e bit 0 se nao desviou), fornece uma segunda oportunidade de acerto. A taxa media de acertos passa de 70% para 90% com esta tecnica.
4. Previsao usando contador saturado : outra alternativa para aumentar a taxa de acertos e a substituicao da BHT por contadores de armazenamento dos bits de historia em uma tabela hash com 16 entradas. Se contador negativo, desvio sera tomado e se contador positivo, desvio nao sera tomado. Apos a instrucao de desvio, contadores sao atualizados (decrementados ou incrementados). ^{[ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ]}

Referencias