Membros radix 2^51 superam cadeias de adição com transporte ao adiar os transportes

Somar números mais largos que 64 bits deveria ser fácil: dividir cada inteiro de 256 bits em quatro pedaços de 64 bits, somá-los e propagar qualquer estouro para cima. O problema é o estouro — sem os transportes a resposta fica errada, então a versão correta encadeia a instrução de adição com transporte do x86 (adc) do membro menos significativo para cima. Em CPUs modernas com execução fora de ordem, essa cadeia é mais lenta que o código paralelo incorreto: adc é uma instrução mais pesada, e cada uma depende da flag de transporte produzida pela anterior. Uma CPU Haswell consegue emitir até quatro adições independentes por ciclo, mas adcs encadeados executam em série.

A correção contraintuitiva, conhecida na literatura de criptografia como representação radix 2^51, é usar mais membros, cada um menor que um registrador. Onde a abordagem óbvia divide 256 bits em quatro dígitos na base 2^64, esta abordagem os divide em cinco dígitos na base 2^51; cada membro de 64 bits ainda comporta seu dígito, mas os 12–13 bits superiores ficam vazios como espaço onde os transportes podem se acumular. Por causa dessa folga, somar valores normalizados não produz transporte algum até que os bits livres se esgotem — até aproximadamente 2^13 adições —, de modo que cada adição é independente e o processador as agenda em paralelo.

Os transportes não são eliminados, apenas adiados. Quando a folga acaba, uma passada de normalização desloca o estouro de cada membro para o membro acima e zera a margem, e a subtração funciona da mesma forma ao tratar os membros como com sinal, ao custo de um bit de folga. Os benchmarks rápidos do autor em uma máquina Haswell constataram que a adição radix-2^51 já era mais rápida que a adição radix-2^64 a partir de apenas três adições, incluindo o custo de converter para a representação e dela sair, com a economia crescendo à medida que mais adições se acumulam.

O artigo constrói a intuição primeiro no papel: na base 10, ampliar a faixa de cada dígito para que ele possa contar além de 9 permite somar vários números normalizados antes que qualquer dígito estoure, e uma passada de normalização converte o resultado de volta. Transportado para registradores binários, o mesmo princípio é a razão pela qual a representação é padrão em criptografia — e pela qual, contraintuitivamente, espalhar um número por mais registradores e emitir mais instruções torna a aritmética mais rápida. Publicado originalmente em 2017, o artigo foi postado no Hacker News em maio de 2020 e atraiu 518 pontos e 83 comentários.

Encolher os membros para 51 bits para que os bits livres absorvam os transportes: as adições permanecem independentes e paralelas, e a normalização acontece uma única vez ao final

Os transportes são a dependência: instruções adc encadeadas se serializam porque cada uma espera pela flag de transporte anterior, enquanto adições simples independentes podem ser emitidas quatro por ciclo na Haswell.

A folga vazia é o truque: dígitos de 51 bits dentro de registradores de 64 bits deixam 12–13 bits livres, de modo que aproximadamente 2^13 adições ocorrem antes que qualquer transporte precise se propagar.

Uma passada adiada supera muitas imediatas: a normalização ao final é uma varredura fixa em vez de uma dependência de transporte em cada operação.

O membro extra se paga: cinco adições simples superam quatro cadeias adc a partir de apenas três adições, mesmo contabilizando o custo de conversão.

Para quebrar uma dependência serial, adicione folga que você paga depois: reserve margem para que a operação crítica rode livre, e então resolva o trabalho adiado em uma única passada.

Publicado em 2017 e postado no Hacker News em maio de 2020, atraiu 518 pontos e 83 comentários. Praticantes ancoraram o truque em código real: comentaristas observaram que a aritmética de corpo de Curve25519 opera módulo 2^255−19, de modo que os valores cabem em membros de 51 bits, com uma variante radix-2^25.5 em CPUs de 32 bits; outros debateram as instruções ADCX/ADOX da Broadwell e as paradas de registrador parcial, e um apontou um erro na explicação do artigo sobre o membro superior. A técnica permaneceu o que o artigo a chamou: uma representação radix-2^51 padrão em criptografia, usada onde a aritmética de corpo precisa ser rápida e de tempo constante.