O truque da base 2^51 (2017)

 (chosenplaintext.ca)
1 pontos por GN⁺ 2025-05-31 | 1 comentários | Compartilhar no WhatsApp
  • A adição de inteiros grandes normalmente é processada dividindo-os em limbs de 64 bits, mas quando há propagação de carry fica difícil aproveitar de fato as vantagens de execução paralela das CPUs modernas
  • O adc do x86 depende do carry flag da operação anterior e, por isso, serializa a cadeia de instruções, tornando-se um gargalo mesmo em arquiteturas como a Intel Haswell, que conseguem executar vários add em paralelo
  • A representação em base 2^51 divide um valor de 256 bits em cinco dígitos de 2^51 em vez de quatro dígitos de 2^64, usando os bits superiores que sobram em cada limb como espaço para armazenar carries intermediários
  • Isso não elimina o carry; em vez disso, atrasa a propagação ao longo de várias somas e depois processa tudo de uma vez na etapa final de normalização
  • Em um benchmark simples no Haswell, mesmo incluindo o custo de conversão, a abordagem em base 2^51 já era mais rápida a partir de três somas, e a vantagem aumentava conforme o número de repetições crescia

Por que o carry vira gargalo na adição de inteiros grandes

  • A soma longa feita no papel normalmente vai da direita para a esquerda, começando pela casa das unidades
    • Isso acontece porque o resultado de cada casa depende do carry que vem da casa à direita
    • Se somarmos da esquerda para a direita, um carry gerado depois pode obrigar a corrigir resultados já calculados nas casas anteriores
  • A adição de inteiros grandes tem a mesma limitação
    • Se dividirmos os inteiros de 256 bits x e y em quatro limbs de 64 bits, podemos somar os limbs na mesma posição
    • Se houver overflow em um limb mais baixo, esse 1 precisa ser repassado para o limb mais alto
  • O adc do x86 é a instrução que trata essa propagação
    • Ela verifica se houve overflow na operação anterior e, se necessário, soma mais 1
    • Uma soma correta de 256 bits encadeia as instruções na ordem add, adc, adc, adc, começando pelo limb menos significativo

Por que o adc fica lento nas CPUs modernas

  • Em geral, o adc custa mais para executar do que um add comum
    • O adc é mais complexo porque usa um terceiro operando implícito, o carry flag
    • Como ele é usado com menos frequência que add, os projetistas de CPU têm menos incentivo para gastar área de chip otimizando o desempenho do adc
  • O problema maior é a dependência entre instruções
    • Na Intel Haswell, um único add leva 1 ciclo para executar
    • Em condições ideais, a Haswell consegue executar até 4 instruções add por ciclo
    • A Haswell tem 8 portas de execução, das quais 4 conseguem executar add inteiro
  • Quatro add independentes são fáceis de paralelizar
    • Já uma cadeia de adc faz cada instrução depender da saída do carry flag da instrução anterior
    • A CPU não consegue paralelizar essas instruções e precisa executá-las em sequência
  • Em SIMD, a perda é ainda maior
    • vpaddq executa quatro somas de 64 bits ao mesmo tempo
    • A Haswell consegue executar dois vpaddq por ciclo
    • Se essa paralelização for abandonada para tratar carry, a vantagem de desempenho diminui

Atrasando o carry com uma soma no papel

  • Dá para atrasar o carry mantendo o valor posicional decimal, mas ampliando o conjunto de símbolos que cada casa pode usar
    • Em vez de usar apenas 0-9, usamos também A-Z e *, totalizando 37 símbolos
    • Mas a base em si não vira 37; o sistema continua usando valores posicionais decimais
  • Assim, uma casa não precisa gerar carry imediatamente ao passar de 9
    • 29 + 1 pode ser escrito como 30, mas também como 2A, 1K ou U
    • Se os dígitos de cada operando estiverem normalizados e forem todos no máximo 9, o carry pode ser adiado durante a soma
  • Isso não vale sempre para qualquer entrada
    • Se já houver um dígito grande, como em 9 + W, o carry passa a ser necessário
    • Entre números normalizados, é possível somar até quatro deles sem precisar de carry
  • No fim, é preciso normalizar de volta para a representação decimal comum
    • A partir da direita, calcula-se quantos grupos de 10 existem em cada casa
    • Esse valor é subtraído da casa atual e repassado para a próxima
  • A ideia central não é eliminar a propagação de carry, mas armazená-la durante os cálculos intermediários e propagá-la uma única vez no final

A representação em base 2^51 no computador

  • Se um valor de 256 bits for dividido em quatro limbs de 2^64, cada limb pode assumir valores de 0 até 2^64−1
    • É uma forma de tratar cada limb como um dígito em base 2^64
  • Como não dá para ampliar a largura do inteiro de 64 bits no hardware, o tamanho da base é reduzido
    • Em vez de quatro dígitos de 2^64, o valor de 256 bits é dividido em cinco dígitos de 2^51
    • Cada limb continua armazenado como inteiro de 64 bits, mas só usa de fato 51 ou 52 bits de valor
  • Os bits superiores que sobram viram espaço para carries intermediários
    • Cada limb guarda 51 ou 52 bits do número original
    • Os 12 ou 13 bits restantes armazenam carries gerados durante os cálculos
  • Na literatura de criptografia, essa técnica é chamada de radix 2^51 representation
  • Se os números estiverem normalizados, dentro dos 2^64 valores possíveis de um limb dá para somar até 2^13 termos antes de precisar se preocupar com overflow nos 13 bits superiores

Limb mais significativo com 52 bits e normalização

  • Ao limb mais significativo são atribuídos 52 bits
    • Os demais limbs usam 51 bits
    • O carry que sai do limb mais significativo é ignorado, fazendo valores acima de 2^256−1 sofrerem wraparound
    • Isso é igual ao comportamento da soma de inteiros unsigned de tamanho fixo em C quando ocorre overflow
  • O código de soma em base 2^51 executa cinco add independentes, sem usar uma cadeia de adc
    • Em relação à abordagem com quatro limbs de 2^64, o número de add sobe de 4 para 5
    • Em compensação, não há dependência do carry flag, então a execução paralela se torna possível
  • Na etapa de normalização, os bits altos de cada limb são extraídos e somados ao limb seguinte
    • shr 51 extrai a parte de carry
    • and 0x0007FFFFFFFFFFFF preserva apenas os 51 bits inferiores
    • O limb mais significativo é ajustado com and 0x000FFFFFFFFFFFFF
  • A normalização é a etapa final que propaga os carries atrasados
    • As somas intermediárias não criam dependência do carry flag
    • No fim, cada limb volta a ficar dentro da faixa permitida

Resultados de desempenho e extensão para subtração

  • Em um benchmark simples, a soma em base 2^51 foi mais rápida em uma CPU Haswell
    • Isso já incluindo o custo de conversão para e da representação em base 2^51
    • Com apenas três somas, ela já superava a soma em base 2^64
    • Quanto maior o número de somas, maior também era a economia
  • A mesma ideia pode ser estendida para subtração
    • Na subtração, o carry se torna um carry negativo
  • Para suportar subtração, os limbs passam a ser tratados como inteiros com sinal, e não unsigned
    • Cada dígito pode assumir valor positivo ou negativo
    • Cada limb pode armazenar tanto carry positivo quanto carry negativo
  • Essa mudança tem um custo
    • O bit mais alto de cada limb fica reservado como bit de sinal
    • O número de operações possíveis entre normalizações cai de 2^13 para 2^12
  • Mesmo distribuindo os dados por mais registradores e aumentando o número de operações, reduzir a dependência de carry ainda pode melhorar o desempenho total

Leituras relacionadas

1 comentários

 
GN⁺ 2025-05-31
Opiniões no Hacker News

  • Fico me perguntando se não daria para deixar o limb mais significativo com 64 bits e os outros quatro limbs com 48 bits cada
    Seria possível acumular mais somas antes da normalização; se o conjunto de instruções tiver recursos úteis, também daria para aproveitar o alinhamento de palavras na hora de dividir e normalizar; e as características de overflow parecem iguais

    • Se um dos objetivos é fazer operações de 256 bits com cinco registradores de 64 bits, então isso equivale a usar 256/5 = 51,2 bits por palavra, o que parece uma disposição até certo ponto ideal
      Para uma biblioteca genérica de inteiros grandes talvez não seja o ideal; antigamente, como não havia barrel shifters eficientes para deslocamentos arbitrários de bits, provavelmente era melhor usar 56 dos 64 bits, deixando exatamente 1 byte para o carry
      Como RISC-V não tem flags, essa discussão é bastante relevante
    • Se você somar o limb mais significativo de dois números codificados, dá overflow rápido demais
      Por exemplo, se ambos forem 2^63, já estoura imediatamente; pode servir para aritmética com wraparound, mas não funciona no caso geral
    • Fazendo isso, seriam necessárias 6 palavras para armazenar um valor de 256 bits, não as 5 palavras do método original, e portanto também seriam necessárias mais instruções de soma

  • Com AVX512, e até certo ponto também com AVX2, dá para implementar soma de 256 bits de forma bastante eficiente, com a vantagem de caberem mais números nos registradores
    É uma combinação de _mm256_add_epi64, máscara de comparação e máscara de carry, e o throughput também parece melhor: https://godbolt.org/z/e7zETe8xY
    Transformar isso em soma de 512 bits também é simples, e nesse caso a melhoria deve ser maior

  • Em CPUs x86 suficientemente recentes, por exemplo Intel Broadwell ou AMD Ryzen, também é possível usar ADX, e hoje isso pode ser mais rápido até em situações como Curve25519, nas quais a representação em radix 2^51 tradicionalmente tinha vantagem
    [1] https://en.wikipedia.org/wiki/Intel_ADX

  • Como leitura relacionada, há threads antigas sobre o radix 2^51 trick
    The radix 2^51 trick - https://news.ycombinator.com/item?id=33706153 - novembro de 2022
    The radix 2^51 trick (2017) - https://news.ycombinator.com/item?id=23351007 - maio de 2020

  • O ponto central é que, mesmo havendo mais operações, se elas forem em grande parte independentes, podem ser executadas em paralelo e acabar sendo mais rápidas
    Inversamente, mesmo com menos operações, se elas precisarem rodar em série por dependências de dados, podem ser mais lentas; essa ideia se aplica de forma muito mais ampla do que só a operações com inteiros longos

    • Outra abordagem é usar os pedaços normais de 64 bits, mas executar em paralelo, de forma especulativa, cada soma nos casos com carry e sem carry, e depois escolher o lado correto de acordo com o resultado do carry da soma dos dígitos menos significativos
      O número de somas dobra, mas o tempo de propagação do carry pode ser reduzido de linear para log(bits)
    • A parte que eu não tinha entendido bem é que a técnica mostrada aqui parece focar em fazer o ripple carry acontecer apenas uma vez ao somar N valores, em vez de N-1 vezes
      A operação de carry é mais complexa, mas as somas em si podem ser paralelizadas
      Só que, como para começo de conversa é preciso dividir os números de entrada em grupos de 5 registradores, parece que essa divisão também teria de ser paralelizável para haver ganho no todo
    • A Nvidia está explorando essa ideia geral, e em algumas áreas parece estar obtendo resultados bem promissores
    • Essa regra se estende até supercomputadores multinó ou à nuvem
      Se você puder usar 10.000 núcleos, o overhead se torna desprezível

  • Mostra muito bem, para quem só trabalhou com x86_64, que o RISC-V não estava errado ao omitir o carry flag

    • Ainda dá para fazer de outro jeito mantendo limbs de 64 bits
      A percepção central é que, a menos que a soma em uma determinada posição de limb seja toda composta de 1s, o carry que sai dessa posição não depende do carry que entra, mas apenas de se a soma original naquela posição gerou carry
      Se a soma for toda de 1s, o carry de saída é igual ao carry de entrada
      Expressando isso como um desvio condicional quase sempre previsto como not-taken, cada bloco de instruções pode executar totalmente em paralelo, partindo da premissa de que vários desvios condicionais podem ser previstos como not-taken no mesmo ciclo de clock
      Uma vez a cada 2^64 execuções, isso roda muito devagar
      Em uma máquina 4-wide com números de 4 limbs, não há vantagem sobre adc; mas em uma máquina 8-wide com números de 8 limbs, a vantagem começa a ficar grande
      Talvez isso não ajude muito no x86_64 atual, mas há potencial na série Apple M, já que o M1 também é 8-wide, embora o ISA Arm possa tornar o contorno mais complicado
      Quando o Ascalon RISC-V 8-wide da Tenstorrent sair no fim deste ano ou no começo de 2026, poderemos verificar isso na prática, junto com Ventana, Rivos, XiangShan e outros
      Com um shift rápido de 1 lane, isso também funciona melhor em SIMD largo; no RISC-V, isso é chamado de slideup
    • Ainda há muitos casos comuns em que carry-save addition é pior do que add-with-carry
      Os dois algoritmos de soma multipalavra não substituem um ao outro e têm usos diferentes; por isso, um ISA decente inclui instruções ADC/SBB, e o custo adicional é mínimo
      Também não é obrigatório ter um registrador de flags dedicado; alguns ISAs armazenam flags de carry e borrow em registradores de uso geral quando necessário
      A ausência de carry no RISC-V não é sua pior característica; pior é a falta de uma flag de overflow de inteiros
      Para programas que se dizem escritos de forma segura, detectar overflow de inteiros é essencial, e contornar isso em software reduz muito mais o desempenho alcançável do que contornar a ausência de carry
    • Essa linha de acontecimentos é, no fim das contas, consequência de C ter omitido o carry flag, e na prática ele quase não acabou sendo usado para carry
    • Se o carry flag é lento de qualquer forma, eu não fui o único a pensar “afinal, qual era mesmo a polêmica sobre RISC-V e GMP?”

  • Esse radix trick também se aplica a estruturas de dados
    Há bons exemplos no livro de Okasaki, 『Purely Functional Data Structures』

  • Eu gostaria de ter visto este texto alguns meses atrás
    Ao tentar codificar e decodificar um buffer em uma base arbitrária, cheguei tarde demais à conclusão de que o carry podia se propagar até o fim do buffer e que isso deixava o algoritmo muito mais lento
    No fim, a solução também tinha algo parecido com este truque: dividi o buffer em chunks e deixei espaço de folga para lidar com o carry
    Não é exatamente a mesma coisa; deixei alguns bits desperdiçados, usando um pouquinho mais de armazenamento ou largura de banda de rede em troca de reduzir a computação
    Fico me perguntando se acumular carries assim e resolvê-los em uma etapa posterior permitiria ter o melhor dos dois mundos, mas talvez isso seja só desejo meu

  • Eu sei que as diretrizes do HN dizem para não editar títulos, mas não gosto de títulos caça-cliques que inflam uma afirmação pequena para algo amplo demais
    O título deste texto deveria ter sido algo como “O truque radix 2^51 para somar inteiros de 64 bits em paralelo sem atrasar o pipeline por dependência de carry em algumas arquiteturas x86”