performance - pic - delay avr assembly




Por que introduzir instruções MOV inúteis acelera um loop apertado na montagem x86_64? (3)

Fundo:

Enquanto otimizava algum código Pascal com linguagem assembly embutida, notei uma instrução MOV desnecessária e a removi.

Para minha surpresa, remover a instrução desnecessária fez com que meu programa diminuísse .

Descobri que adicionar instruções MOV arbitrárias e inúteis aumentou ainda mais o desempenho .

O efeito é errático e muda com base na ordem de execução: as mesmas instruções de lixo transpostas para cima ou para baixo por uma única linha produzem uma desaceleração .

Eu entendo que a CPU faz todos os tipos de otimizações e racionalização, mas isso parece mais com magia negra.

Os dados:

Uma versão do meu código compila condicionalmente três operações de lixo eletrônico no meio de um loop que executa 2**20==1048576 vezes. (O programa circundante calcula apenas hashes SHA-256 ).

Os resultados na minha máquina antiga (Intel (R) Core ™ 2 CPU 6400 @ 2.13 GHz):

avg time (ms) with -dJUNKOPS: 1822.84 ms
avg time (ms) without:        1836.44 ms

Os programas foram executados 25 vezes em um loop, com a ordem de execução variando aleatoriamente a cada vez.

Excerto:

{$asmmode intel}
procedure example_junkop_in_sha256;
  var s1, t2 : uint32;
  begin
    // Here are parts of the SHA-256 algorithm, in Pascal:
    // s0 {r10d} := ror(a, 2) xor ror(a, 13) xor ror(a, 22)
    // s1 {r11d} := ror(e, 6) xor ror(e, 11) xor ror(e, 25)
    // Here is how I translated them (side by side to show symmetry):
  asm
    MOV r8d, a                 ; MOV r9d, e
    ROR r8d, 2                 ; ROR r9d, 6
    MOV r10d, r8d              ; MOV r11d, r9d
    ROR r8d, 11    {13 total}  ; ROR r9d, 5     {11 total}
    XOR r10d, r8d              ; XOR r11d, r9d
    ROR r8d, 9     {22 total}  ; ROR r9d, 14    {25 total}
    XOR r10d, r8d              ; XOR r11d, r9d

    // Here is the extraneous operation that I removed, causing a speedup
    // s1 is the uint32 variable declared at the start of the Pascal code.
    //
    // I had cleaned up the code, so I no longer needed this variable, and 
    // could just leave the value sitting in the r11d register until I needed
    // it again later.
    //
    // Since copying to RAM seemed like a waste, I removed the instruction, 
    // only to discover that the code ran slower without it.
    {$IFDEF JUNKOPS}
    MOV s1,  r11d
    {$ENDIF}

    // The next part of the code just moves on to another part of SHA-256,
    // maj { r12d } := (a and b) xor (a and c) xor (b and c)
    mov r8d,  a
    mov r9d,  b
    mov r13d, r9d // Set aside a copy of b
    and r9d,  r8d

    mov r12d, c
    and r8d, r12d  { a and c }
    xor r9d, r8d

    and r12d, r13d { c and b }
    xor r12d, r9d

    // Copying the calculated value to the same s1 variable is another speedup.
    // As far as I can tell, it doesn't actually matter what register is copied,
    // but moving this line up or down makes a huge difference.
    {$IFDEF JUNKOPS}
    MOV s1,  r9d // after mov r12d, c
    {$ENDIF}

    // And here is where the two calculated values above are actually used:
    // T2 {r12d} := S0 {r10d} + Maj {r12d};
    ADD r12d, r10d
    MOV T2, r12d

  end
end;

Tente você mesmo:

O código está online no GitHub se você quiser experimentar você mesmo.

Minhas perguntas:

  • Por que copiar o conteúdo de um registrador para a RAM aumentaria o desempenho?
  • Por que a mesma instrução inútil forneceria uma aceleração em algumas linhas e uma desaceleração em outras?
  • Esse comportamento é algo que pode ser explorado de maneira previsível por um compilador?

Preparando o cache

Mover as operações para a memória pode preparar o cache e acelerar as operações de movimentação subseqüentes. Uma CPU geralmente possui duas unidades de carga e uma unidade de armazenamento. Uma unidade de carga pode ler da memória em um registrador (uma leitura por ciclo), uma unidade de armazenamento armazena de registrador para a memória. Existem também outras unidades que fazem operações entre registros. Todas as unidades funcionam em paralelo. Assim, em cada ciclo, podemos fazer várias operações ao mesmo tempo, mas não mais do que duas cargas, uma loja e várias operações de registro. Geralmente, são realizadas até 4 operações simples com registros simples, até 3 operações simples com registradores XMM / YMM e operações 1-2 complexas com qualquer tipo de registro. Seu código tem muitas operações com registros, portanto, uma operação de armazenamento de memória fictícia é livre (já que existem mais de 4 operações de registro), mas prepara o cache de memória para a operação de armazenamento subseqüente. Para descobrir como funcionam os armazenamentos de memória, consulte o Manual de Referência de Otimização de Arquiteturas Intel 64 e IA-32 .

Quebrando as dependências falsas

Embora isso não se refira exatamente ao seu caso, mas às vezes usando operações mov de 32 bits sob o processador de 64 bits (como no seu caso) são usadas para limpar os bits mais altos (32-63) e quebrar as cadeias de dependências.

É bem conhecido que sob x86-64, o uso de operandos de 32 bits limpa os bits mais altos do registrador de 64 bits. Por favor, leia a seção relevante - 3.4.1.1 - do Manual do Desenvolvedor de Software de Arquiteturas Intel® 64 e IA-32 Volume 1 :

Operandos de 32 bits geram um resultado de 32 bits, estendido de zero a um resultado de 64 bits no registro de finalidade geral de destino

Assim, as instruções mov, que podem parecer inúteis à primeira vista, limpam os bits mais altos dos registros apropriados. O que nos dá? Ele quebra as cadeias de dependências e permite que as instruções sejam executadas em paralelo, em ordem aleatória, pelo algoritmo Out-of-Order implementado internamente pelas CPUs desde o Pentium Pro em 1995.

Uma cotação do Manual de Referência de Otimização de Arquiteturas Intel® 64 e IA-32 , Seção 3.5.1.8:

Sequências de código que modificam o registro parcial podem sofrer algum atraso em sua cadeia de dependência, mas podem ser evitadas usando expressões de quebra de dependência. Em processadores baseados na microarquitetura Intel Core, várias instruções podem ajudar a limpar a dependência de execução quando o software usa essas instruções para limpar o conteúdo do registro para zero. Quebre as dependências de partes dos registradores entre as instruções, operando em registradores de 32 bits em vez de registradores parciais. Para movimentos, isso pode ser feito com movimentos de 32 bits ou usando o MOVZX.

Codificação de Assembly / Compiler Regra 37. (impacto M, generalidade MH) : interrompe as dependências de partes dos registradores entre as instruções, operando em registradores de 32 bits em vez de registradores parciais. Para movimentos, isso pode ser feito com movimentos de 32 bits ou usando o MOVZX.

Os MOVZX e MOV com operandos de 32 bits para x64 são equivalentes - todos eles quebram cadeias de dependências.

É por isso que seu código é executado mais rapidamente. Se não houver dependências, a CPU pode renomear internamente os registradores, mesmo que à primeira vista possa parecer que a segunda instrução modifica um registrador usado pela primeira instrução, e os dois não podem executar em paralelo. Mas devido a registrar a renomeação, eles podem.

Registrar renomear é uma técnica usada internamente por uma CPU que elimina as dependências de dados falsas decorrentes da reutilização de registros por instruções sucessivas que não têm nenhuma dependência de dados real entre elas.

Eu acho que você agora vê que é óbvio demais.


A causa mais provável da melhoria da velocidade é que:

  • inserir um MOV muda as instruções subseqüentes para endereços de memória diferentes
  • uma daquelas instruções movidas era um importante ramo condicional
  • esse ramo estava sendo incorretamente previsto devido ao aliasing na tabela de previsão de ramificação
  • mover o ramo eliminou o alias e permitiu que o ramo fosse previsto corretamente

Seu Core2 não mantém um registro de histórico separado para cada salto condicional. Em vez disso, mantém um histórico compartilhado de todos os saltos condicionais. Uma desvantagem da previsão de ramificação global é que a história é diluída por informações irrelevantes se os diferentes saltos condicionais não estiverem correlacionados.

Este pequeno tutorial de previsão de ramificação mostra como os buffers de previsão de ramificação funcionam. O buffer de cache é indexado pela parte inferior do endereço da instrução de ramificação. Isso funciona bem, a menos que duas ramificações não correlacionadas importantes compartilhem os mesmos bits inferiores. Nesse caso, você acaba com o aliasing, o que causa muitas ramificações incorretas (o que paralisa o pipeline de instruções e reduz a velocidade do seu programa).

Se você quiser entender como as interpretações das agências afetam o desempenho, dê uma olhada nesta excelente resposta: https://.com/a/11227902/1001643

Os compiladores normalmente não têm informações suficientes para saber quais ramificações serão alias e se esses aliases serão significativos. No entanto, essas informações podem ser determinadas em tempo de execução com ferramentas como Cachegrind e VTune .


Você pode querer ler http://research.google.com/pubs/pub37077.html

TL; DR: inserir aleatoriamente instruções nop em programas pode facilmente aumentar o desempenho em 5% ou mais, e não, compiladores não podem facilmente explorar isso. Geralmente, é uma combinação de preditor de ramificação e comportamento de cache, mas também pode ser, por exemplo, uma paralisação de estação de reserva (mesmo no caso de não haver cadeias de dependência quebradas ou assinaturas excessivas de recursos óbvios).