O truque da base 2^51 (2017)

(chosenplaintext.ca)

1 pontos por GN⁺ 2025-05-31 | 1 comentários | Compartilhar no WhatsApp

O problema de carry (vai-um) que ocorre em operações com inteiros grandes é um dos principais fatores que dificultam a paralelização das operações
Na arquitetura x86, a instrução adc para tratar carry é mais lenta que a instrução add comum, e o tratamento contínuo de carry limita a execução em paralelo
Ao usar a representação radix 2^51, é possível adiar a propagação de carry e realizar mais somas rapidamente
Cada limb (valor parcial) recebe apenas 51 ou 52 bits, usando o espaço restante dos bits superiores como armazenamento temporário para carry
Essa técnica, apesar do uso adicional de registradores e do custo de conversão, na prática oferece desempenho melhor do que a base 2^64

Soma e subtração rápidas: o problema do carry

Em adição de inteiros grandes, assim como uma pessoa ao calcular à mão trata o carry dígito por dígito, o computador também tem dificuldade para paralelizar o algoritmo por causa do carry
Basicamente, somamos começando pela direita (dígitos menos significativos), um por um, e o carry gerado em cada posição é levado para a esquerda (dígitos mais significativos)
Se começarmos a soma pela esquerda, o carry anterior afeta a operação da próxima posição, então não é possível paralelizar a ordem das operações

Tratamento de carry no computador

O computador processa somas em unidades de inteiros de 64 bits
Pode parecer que dá para dividir um inteiro de 256 bits em 4 limbs de 64 bits e processar a soma em paralelo, mas na prática é necessário tratar o overflow (carry) para obter o resultado correto
No x86, existe a instrução adc (add with carry), que faz o tratamento de carry automaticamente

Causa da perda de desempenho

A instrução adc precisa de um valor de entrada adicional, a carry flag, então tem desempenho inferior em comparação com um add simples
Na arquitetura Haswell, add pode ser executada em paralelo em várias portas, enquanto adc inevitavelmente exige execução serial (sequencial)
Especialmente ao usar instruções SIMD (vpaddq etc.), a soma paralela sem carry é muito mais rápida

A ideia de adiar o carry (exemplo no papel)

Para reduzir o carry, é possível ampliar o intervalo dos dígitos (por exemplo, de 0-9 para 0-9, A-Z e * — total de 37 símbolos) e, temporariamente, somar vários números sem carry
Assim, várias somas podem ser feitas sem propagação de carry, e no fim o carry pode ser ajustado de uma vez só (normalization)
Esse conceito separa o acúmulo e a propagação de carry, fazendo com que o tratamento de carry ocorra apenas na etapa final
Na operação real, se surgir um valor acima da base da posição, o carry é acumulado e refletido em sequência a partir da direita

Aplicação do adiamento de carry no computador (truque radix 2^51)

Para reduzir a propagação de carry no computador, usa-se a representação radix 2^51
Em vez de 4 limbs de 64 bits para 256 bits, o valor é dividido em 5 limbs de 51~52 bits
- Os 12~13 bits superiores de cada limb funcionam como armazenamento temporário para carry
Nesse método, cada limb mantém a faixa de valores de 2^64 e, durante a operação real, o carry não ocorre com facilidade, permitindo executar várias operações em paralelo sem carry
Após cerca de 2^13 operações consecutivas, é necessário fazer uma normalization (normalização) de uma vez
Em CPUs Haswell, após aplicar radix 2^51, ao repetir apenas somas simples sem carry, o desempenho melhora muito em relação ao radix 2^64 comum
A carry propagation para normalization é feita apenas uma vez, no final

Exemplo de código

Dividindo o valor em 5 registradores, é possível somar sem carry
A normalization é feita extraindo os bits superiores de cada limb, somando-os ao limb vizinho e zerando o valor de carry do próprio limb, repetindo esse processo

Extensão para subtração

A subtração também pode ser aplicada de forma semelhante
Nesse caso, o carry também pode ser negativo, então o limb é tratado como signed integer
O bit mais alto do limb é usado como bit de sinal, então o número de operações que podem ser processadas de uma vez diminui um pouco em comparação com a adição

Conclusão

A técnica de resistência/adiamento de carry, apesar de aumentar o número de limbs e adicionar trabalho de conversão, de fato melhora bastante o desempenho geral das operações
O truque radix 2^51 é amplamente usado em áreas que exigem alto desempenho, como aritmética de grandes inteiros e criptografia
Essa técnica é uma ideia importante para otimizar o desempenho real de hardware/algoritmos

1 comentários

GN⁺ 2025-05-31

Comentários do Hacker News

Ao ver o número 2^51, no começo achei que fosse sobre armazenar inteiros em double, mas percebi que, na verdade, o maior valor inteiro que pode ser representado exatamente em double é 2^53-1
O AVX512 (e, até certo ponto, o AVX2) oferece um ambiente em que é possível implementar adição de 256 bits com bastante eficiência, além da vantagem de caber mais números nos registradores
Um exemplo direto funciona como no código abaixo

__m256i s = _mm256_add_epi64(a, b);
const __m256i all_ones = _mm256_set1_epi64x(~0);
int g = _mm256_cmpgt_epu64_mask(a, s);
int p = _mm256_cmpeq_epu64_mask(s, all_ones);
int carries = ((g << 1) + p) ^ p;

__m256i ret = _mm256_mask_sub_epi64(s, carries, s, all_ones);

Chega a mostrar melhora de throughput, e o exemplo de código real pode ser visto no godbolt.org
Também é muito simples estender essa lógica para adição de 512 bits

Em especial, foi apontado que, em certas arquiteturas de CPU da Intel, apenas usar instruções AVX512 já pode reduzir o clock do processador como um todo, levando a desempenho inconsistente ou até pior
A referência relacionada pode ser vista neste link do Stack Overflow
Sobre a dúvida “por que não usar 12 bits em vez de 13?”, aqui a ideia é ignorar o tratamento de carry do bit mais alto (limb), fazendo com que, em caso de overflow, o comportamento seja de wraparound
Como resultado, o limb mais alto recebe 52 bits, o que tem a desvantagem de ficar sem espaço antes dos outros limbs, mas funciona de forma parecida com a soma de inteiros sem sinal em C
A partir daí, foi sugerido usar 64 bits no limb mais alto e 48 bits em cada um dos outros quatro limbs
Isso permitiria acumular mais operações antes da normalização e ainda teria vantagens como alinhamento por palavra
As características de tratamento de overflow também seriam as mesmas
- Se apenas o limb mais alto receber 64 bits, o overflow ao somar os limbs de dois números acontece rápido demais
  Por exemplo, se ambos tiverem valor 2^63, já ocorre overflow imediatamente
  Em aritmética com wraparound isso não importa, mas em casos gerais é inviável
- Com essa estrutura, seriam necessárias 6 palavras, e não 5 como no OP
  Também seriam necessárias mais instruções
- O objetivo é resolver matemática de 256 bits com 5 registradores de 64 bits
  Ou seja, o ideal seria distribuir 256/5 = 51,2 bits por palavra
  Isso funciona bem se for algo restrito a 256 bits, mas não é o ideal para uma biblioteca big-int de uso geral
  No passado, havia o contexto de querer usar exatamente 1 byte por carry, e, na era anterior aos barrel shifters, preferia-se usar só 56 dos 64 bits para facilitar alinhamento
  No RISC-V, como não há flags em hardware, essa discussão se torna ainda mais importante
Em CPUs x86 modernas (por exemplo, Intel Broadwell e AMD Ryzen), usar instruções Intel ADX pode ser mais rápido até em cenários em que a representação em radix 2^51 tradicionalmente era forte, como no Curve25519
Como material de discussão relacionado
- The radix 2^51 trick (novembro de 2022)
- The radix 2^51 trick (2017)
A principal lição é que, quando as operações são independentes entre si, executar mais delas em paralelo pode acabar sendo mais rápido
Por outro lado, se a dependência obriga execução sequencial, então até um número menor de operações pode ser mais lento
Essa ideia pode ser aplicada não só a aritmética de inteiros longos, mas a várias outras áreas
- Foi proposta uma forma de dividir em chunks de 64 bits e executar previamente, em paralelo, os dois casos possíveis dependendo de haver carry ou não, escolhendo depois a operação correta conforme o carry real
  Esse método dobra o número de somas, mas acelera a propagação para algo na ordem de log(bits), em vez de linear
- A parte que eu não tinha entendido bem nessa técnica é que ela essencialmente faz com que o ripple carry, que ao somar N valores seria executado N-1 vezes, seja executado apenas uma vez
  O tratamento de carry em si fica mais complexo, mas as somas podem ser paralelizadas
  Ainda assim, para a eficiência total fazer sentido, a própria divisão do número de entrada em blocos de 5 registradores também precisa ser paralelizável
- Essa regra pode ser estendida até o nível de supercomputadores ou nuvens com dezenas de milhares de nós
  Se houver muitos núcleos disponíveis, o overhead se torna desprezível
- A NVidia também se interessa por essa ideia e vem obtendo bons resultados em várias áreas
Embora as diretrizes do HN digam que não se deve acrescentar opinião ao título, não gosto de títulos exagerados e caça-cliques
Algo como “truque de radix 2^51 para adição paralela de inteiros de 64 bits sem dependência de carry em algumas arquiteturas x86” me parece mais preciso
Dá um certo pesar pensar que esse texto teria me ajudado se eu o tivesse lido alguns meses antes
Ao codificar/decodificar um buffer em uma base arbitrária, tive a experiência de o carry se propagar pelo buffer inteiro e deixar o algoritmo muito mais lento
No fim, deixei uma “folga” e dividi em chunks para tratar o carry, o que parece ter alguma semelhança com esse truque
Na prática, optei por desperdiçar alguns bits em troca de economizar operações ou largura de banda de rede
Fico curioso se esse mesmo tratamento de carry também poderia ser agrupado como pós-processamento
Seria ideal se desse para ficar com praticamente todas as vantagens
Pela experiência de ter usado apenas ambientes x86_64, isso mostra claramente que não ter carry flag no RISC-V não é necessariamente uma má abordagem
- Além desse método, foi explicado também como manter limbs de 64 bits e fazer somas seguras quanto a carry usando apenas variáveis uint64_t
  O fluxo é o seguinte
```
s0 += a0;
s1 += a1;
s2 += a2;
s3 += a3;
c0 = s0 < a0; // RISC-V sltu
c1 = s1 < a1;
c2 = s2 < a2;
if (s1 == -1) goto propagate0;
check_s2:
if (s2 == -1) goto propagate1;
add_carries:
s1 += c0;
s2 += c1;
s3 += c2;
goto done;
propagate0: c1 = c0; goto check_s2;
propagate1: c2 = c1; goto add_carries;
done:
```
O ponto-chave é que, quando o resultado da soma (limb) não é todo 1s, o carry-out desse limb não depende do carry-in, mas apenas do resultado de somar os valores originais
Já quando o valor é todo 1s, então carry-out = carry-in
Se a estrutura de branches quase não exigir predição, tudo pode ser executado em paralelo
Em termos probabilísticos, só fica mais lento em 1 caso a cada 2^64, mas em máquinas 4-wide isso não traz grande vantagem
Já em máquinas 8-wide, ou em uma estrutura com 8 limbs, pode haver ganho de desempenho relevante
Não se encaixa bem em x86_64, mas pode ter utilidade em máquinas 8-wide como a série Apple M*
Há expectativa para processadores como o Ascalon RISC-V 8-wide da Tenstorrent, além de Ventana, Rivos e XiangShan
Em arquiteturas SIMD e em arquiteturas com instrução rápida de shift/sliding de 1 lane (slideup), o efeito é maximizado
- Carry-save addition nem sempre é superior a add-with-carry
  Os dois tipos de algoritmo de adição multi-word não são substitutos diretos e cada um tem vantagens e desvantagens
  Por isso, instruções ADC/SBB deveriam fazer parte do conjunto básico da ISA, e também deveria ser possível salvar flags em registradores
  No RISC-V, uma desvantagem mais séria é não haver integer overflow flag
  Quando é preciso fazer contorno em software para detectar overflow, a perda de desempenho é muito maior do que a de contornar o carry bit
- A ausência de carry flag no RISC-V deriva do fato de a linguagem C ignorar o carry flag binário
  Na prática, a frequência de uso do carry flag é bem menor
- Então não fui só eu que pensei: “se o carry flag já é lento de qualquer forma, por que existiu toda aquela discussão sobre risc5 gmp?”
O “radix trick” também pode ser aplicado a estruturas de dados
Há um exemplo interessante no livro 'Purely Functional Data Structures', de Okasaki