Os processadores modernos são superescalares, ou seja, são capazes de executar várias instruções simultaneamente. Por exemplo, alguns processadores podem processar de quatro a seis instruções por ciclo. Além disso, muitos desses processadores são capazes de iniciar instruções fora de ordem: eles podem começar a trabalhar com comandos localizados no código muito mais tarde.
Ao mesmo tempo, o código geralmente contém ramificações (
if–then ). Tais ramificações são frequentemente implementadas como "transições", nas quais o processador continua executando instruções abaixo do código ou continua o caminho atual.
Com a execução superescalar de comandos fora de ordem, a ramificação é difícil. Para isso, os processadores possuem sofisticados blocos de previsão de ramificação. Ou seja, o processador está tentando prever o futuro. Quando ele vê um ramo e, portanto, uma transição, ele tenta adivinhar para que lado o programa irá.
Muitas vezes isso funciona muito bem. Por exemplo, a maioria dos loops é implementada como ramificação. No final de cada iteração do loop, o processador deve prever se a próxima iteração será executada. Muitas vezes, é mais seguro para o processador prever que o ciclo continuará (para sempre). Nesse caso, o processador prevê erroneamente apenas uma ramificação por ciclo.
Existem outros exemplos comuns. Se você acessar o conteúdo de uma matriz, muitas linguagens de programação adicionam "verificação vinculada" - uma verificação oculta da correção do índice antes de acessar o valor da matriz. Se o índice estiver incorreto, um erro será gerado; caso contrário, o código continuará sendo executado da maneira usual. As verificações de fronteira são previsíveis, porque em uma situação normal todas as operações de acesso devem estar corretas. Consequentemente, a maioria dos processadores deve prever quase perfeitamente o resultado.
O que acontece se for difícil prever ramificações?
Dentro do processador, todas as instruções executadas, mas localizadas na ramificação prevista incorretamente, devem ser canceladas e os cálculos devem ser iniciados novamente. É de se esperar que, para cada erro de previsão de ramificação, pagemos mais de 10 ciclos. Por esse motivo, o tempo de execução do programa pode aumentar significativamente.
Vejamos um código simples no qual escrevemos números aleatórios em uma matriz de saída:
while (howmany != 0) { out[index] = random(); index += 1; howmany--; }
Podemos gerar um número aleatório adequado, em média, por 3 ciclos. Ou seja, o atraso total do gerador de números aleatórios pode ser igual a 10 ciclos. Mas nosso processador é superescalar, ou seja, podemos executar vários cálculos de números aleatórios simultaneamente. Portanto, seremos capazes de gerar um novo número aleatório aproximadamente a cada 3 ciclos.
Vamos mudar um pouco a função para que apenas números ímpares sejam gravados na matriz:
while (howmany != 0) { val = random(); if( val is an odd integer ) { out[index] = val; index += 1; } howmany--; }
Você pode pensar ingenuamente que esse novo recurso pode ser mais rápido. E, de fato, porque precisamos gravar em média apenas um dos dois números inteiros. Existe uma ramificação no código, mas para verificar a paridade de um número inteiro, basta verificar um bit.
Comparei essas duas funções em C ++ em um processador Skylake:
A segunda função funciona cerca de cinco vezes mais!
Alguma coisa pode ser consertada aqui? Sim, podemos simplesmente eliminar a ramificação. Um número inteiro ímpar pode ser caracterizado de forma que seja um AND lógico bit a bit com um valor de 1 igual a um. O truque é incrementar o índice da matriz em um somente se o valor aleatório for ímpar.
while (howmany != 0) { val = random(); out[index] = val; index += (val bitand 1); howmany--; }
Nesta nova versão, sempre escrevemos um valor aleatório na matriz de saída, mesmo que não seja necessário. À primeira vista, isso é um desperdício de recursos. No entanto, ele nos salva de ramos preditos por engano. Na prática, o desempenho é quase o mesmo que o código original e muito melhor que a versão com ramificações:
O compilador poderia resolver esse problema sozinho? Em geral, a resposta é não. Às vezes, os compiladores têm opções para eliminar completamente a ramificação, mesmo se houver uma
if-then no código-fonte. Por exemplo, as ramificações podem às vezes ser substituídas por "movimento condicional" ou outros truques aritméticos. No entanto, esses truques não são seguros para uso em compiladores.
Uma conclusão importante: a ramificação prevista erroneamente não é um problema insignificante, tem uma grande influência.
Meu código fonte está no Github .
Criar benchmarks é uma tarefa difícil: os processadores aprendem a prever ramificações
[Nota transl.: esta parte era um
artigo separado do autor, mas eu o combinei com o anterior, porque eles têm um tema comum.]
Na parte anterior, mostrei que a maior parte do tempo de execução de um programa pode ser causada por previsão incorreta de ramificação. Meu benchmark foi escrever 64 milhões de valores inteiros aleatórios em uma matriz. Quando tentei gravar apenas números aleatórios ímpares, o desempenho devido a previsões errôneas diminuiu bastante.
Por que usei 64 milhões de números inteiros, em vez de, digamos, 2000? Se você executar apenas um teste, isso não importará. No entanto, o que acontecerá se fizermos muitas tentativas? O número de ramificações previstas erroneamente cairá rapidamente para zero. O desempenho do processador Intel Skylake fala por si:
Como pode ser visto nos gráficos abaixo, o "treinamento" continua ainda mais. Gradualmente, a proporção de ramos erroneamente previstos cai para cerca de 2%.
Ou seja, se continuarmos medindo o tempo gasto pela mesma tarefa, ele se tornará cada vez menos, porque o processador aprende a prever melhor o resultado. A qualidade do "treinamento" depende do modelo de processador específico, mas espera-se que os processadores mais novos aprendam melhor.
Os mais recentes processadores de servidor AMD aprendem a prever quase perfeitamente ramificações (dentro de 0,1%) em menos de 10 tentativas.
Essa previsão ideal no AMD Rome desaparece quando o número de valores no problema aumenta de 2000 para 10.000: a melhor previsão muda de uma fração de erros de 0,1% a 33%.
Você provavelmente deve evitar o código de benchmarking com ramificação para pequenas tarefas.
Meu código do github .
Agradecimento : Valores da AMD Rome fornecidos por Vel Erwan.
Leitura adicional :
Um caso para (parcialmente) a previsão de ramificação do comprimento da história GEométrica (parcialmente) (Seznec et al.)