🔢 mathematics

Performance evaluation of branch-free fused multiply-add algorithms for multi-component-type multiple-precision floating-point arithmetic

Este artigo propõe e avalia novos algoritmos de multiplicação-acumulação fundida sem desvios para aritmética de precisão múltipla de palavra dupla, tripla e quádrupla, demonstrando que eles alcançam novos ganhos de desempenho sobre os métodos existentes ao eliminar desvios condicionais.

Autores originais: Tomonori Kouya

Publicado 2026-07-14

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Tomonori Kouya

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você esteja tentando construir uma calculadora superprecisa usando apenas peças de LEGO padrão, prontas para uso. Essas peças de LEGO são os números de ponto flutuante normais do seu computador. Geralmente, quando você empilha essas peças para fazer um "double-word" (duas peças), "triple-word" (três peças) ou "quadruple-word" (quatro peças), você tem que verificar constantemente o tamanho das peças enquanto as constrói. Se uma peça for grande demais ou pequena demais, você tem que parar, pausar e rearranjar a pilha. No mundo dos chips de computador, essas "pausas" são chamadas de desvios (branches).

Quando você tenta construir um milhão dessas pilhas de uma só vez (como em uma placa de vídeo moderna ou um processador poderoso), essas pausas tornam-se um pesadelo. É como um congestionamento onde cada carro tem que parar para verificar uma placa diferente antes de seguir adiante. Alguns carros vão para a esquerda, outros para a direita, e toda a fila trava. Isso é chamado de "divergência de lane" (lane divergence), e isso acaba com o desempenho.

A Grande Descoberta: A Rodovia "Sem Paradas"
O artigo de Tomonori Kouya introduz uma nova maneira de construir essas pilhas que nunca para para verificar as placas. É um algoritmo "livre de desvios" (branch-free). Em vez de perguntar "Esta peça é grande o suficiente?" e esperar por uma resposta, o novo método usa uma rota inteligente e pré-planejada que funciona perfeitamente, não importa como as peças sejam.

O artigo prova, usando um robô matemático superinteligente (um solver SMT chamado FPANVerifier), que essa nova rota é segura e precisa para todos os formatos de computador padrão. O principal achado é que, ao remover essas pausas de "parar e verificar", o computador pode calcular muito mais rápido.

O Truque de Mágica: Fundindo o Movimento
O artigo foca em um movimento específico chamado Fused Multiply-Add (FMA). Imagine que você tem que multiplicar dois números e depois somar um terceiro. Normalmente, você faz isso em duas etapas:

Multiplicar (e talvez pausar para corrigir o resultado).
Somar (e talvez pausar novamente).

O autor propõe uma versão "Fundida" (Fused) que faz ambos em um único movimento fluido, como um ninja que lança uma faca e a pega no mesmo fôlego.

Para Double-Word (2 peças): O modo antigo levava 29 passos. O novo modo leva apenas 17.
Para Triple-Word (3 peças): O modo antigo levava 96 passos. O novo modo leva 66.
Para Quadruple-Word (4 peças): O modo antigo levava 209 passos. O novo modo leva 146.

O artigo também discute um método de "atalho" proposto por outros pesquisadores (o método de 6 passos). Crucialmente, este atalho NÃO é geralmente válido. É uma ferramenta de alta velocidade que só funciona se os números já estiverem perfeitamente arranjados de uma forma específica (especificamente, se o número somado for pelo menos duas vezes maior que o produto). Se você tentar usar esse atalho em problemas matemáticos gerais como divisão ou raiz quadrada, onde você não pode garantir que esses números se alinhem, a precisão degrada drasticamente. O novo método do autor, porém, funciona para quaisquer números sem precisar de arranjos especiais, tornando-o um verdadeiro substituto direto para matemática de alta precisão geral.

O Quão Certos Estamos?
Os autores estão incrivelmente confiantes, mas eles sustentam isso com evidências concretas, não apenas suposições.

Verificado por Máquina: Eles não apenas escreveram um código e esperaram; eles usaram um programa de computador para provar matematicamente que o erro no novo método é minúsculo (especificamente, limitado por fórmulas como $34u^2$ , $184u^3$ e $812u^4$ , onde $u$ é o erro de arredondamento minúsculo de um único número).
Testado em Todo Lugar: Eles rodaram esses novos algoritmos em dois supercomputadores muito diferentes: um chip baseado em Arm (GB10) e um chip baseado em Intel (H100).
Os Resultados:
- No chip Arm, o novo método foi de 1,5 a 2,1 vezes mais rápido para cálculos de divisão e raiz quadrada.
- No chip Intel, ele foi de 1,2 a 1,6 vezes mais rápido para divisão e raiz quadrada.
- Para tarefas matemáticas grandes como multiplicação de matrizes (GEMM), o ganho de velocidade foi ainda mais dramático no chip Arm, chegando a 2,0 vezes mais rápido para números triple-word.

A Alternativa "Exata"
O artigo também menciona uma versão "Perfeita" deste truque chamada Exact FMA. Esta versão é ainda mais precisa, mas vem com um preço pesado: ela é de 6 a 11 vezes mais lenta que o novo método proposto. Os autores sugerem usar esta versão "Perfeita" apenas quando você absolutamente, 100%, precisa da maior precisão possível e não se importa com a velocidade. Para quase tudo o resto, o método "livre de desvios" é o vencedor.

E Quanto ao "Modo Antigo"?
O artigo também corrige um erro de uma versão anterior desta pesquisa. Anteriormente, os autores compararam seu novo método com um método antigo "totalmente destilado" que era incrivelmente lento e ineficiente. Eles perceberam que essa não era uma luta justa. Quando compararam seu novo método contra o método "livre de desvios" (branch-free) padrão que já é bastante rápido, o novo método ainda venceu, mas o ganho de velocidade foi mais modesto (cerca de 1,3 a 1,7 vezes mais rápido). Isso ainda é uma grande vitória, mas é uma vitória realista.

O Ponto Principal
Este artigo mostra que, ao remover as pausas de "parar e verificar" na matemática de alta precisão, podemos tornar os computadores significativamente mais rápidos sem perder a precisão. É como atualizar de um carro que tem que parar em cada interseção para um carro que pode voar sobre elas. Os autores provaram que isso funciona, testaram em hardware real e mostraram que está pronto para ser usado na próxima geração de calculadoras super-rápidas.

Resumo Técnico: Avaliação de Desempenho de Algoritmos de Multiplicação e Soma Fundida (FMA) Livres de Desvio para Aritmética de Precisão Múltipla de Múltiplos Componentes

1. Definição do Problema

A aritmética de precisão múltipla de múltiplos componentes (ex: Double-Word/DW, Triple-Word/TW, Quadruple-Word/QW) alcança alto desempenho ao agrupar componentes padrão binary64 (ou binary32) e tratar carries exatamente via Transformações Livres de Erro (EFTs). No entanto, as etapas de renormalização nesses algoritmos dependem tipicamente de desvios de tipo if dependentes das magnitudes intermediárias dos valores. Esses desvios causam penalidades significativas de desempenho em implementações SIMD e GPU devido à divergência de lanes ou warps.

Embora Zhang e Aiken tenham proposto anteriormente algoritmos livres de desvio para adição e multiplicação DW/TW/QW, a composição dessas operações separadas livres de desvio permanece subótima. Especificamente, realizar uma operação de multiplicação e soma fundida (FMA) $z \leftarrow x \cdot y + c$ compondo sequencialmente uma multiplicação livre de desvio e uma adição livre de desvio incurre em uma contagem de operações elevada (ex: 29 flops para DW, 96 para TW, 209 para QW) e etapas de renormalização redundantes.

2. Metodologia

O artigo propõe novos algoritmos de multiplicação e soma fundida (FMA) livres de desvio para aritmética DW, TW e QW (e suas variantes de base de precisão simples DS, TS, QS). A metodologia central envolve:

Estrutura Algorítmica: O FMA proposto calcula $z \leftarrow x \cdot y + c$ $z \leftarrow x \cdot y + c$ em um único estágio fundido, em vez de compor multiplicação e adição separadas. O processo envolve:
1. Expansão do Produto: Decomposição dos produtos dos componentes usando TwoProd.
2. Acumulação por Peso: Agrupamento de termos que chegam à mesma posição de potência de dois usando cadeias de TwoSum.
3. Renormalização: Remodelagem do resultado em $K$ componentes não sobrepostos.
Seleção de Portões e Verificação: Um princípio de design crítico é a seleção de portões de renormalização baseados em precondições verificáveis por máquina. O algoritmo utiliza FastTwoSum (3 flops) apenas onde a precondição $\text{exp}(a) \ge \text{exp}(b)$ pode ser provada por máquina para todas as precisões $p$ usando o solver SMT z3 via ferramenta FPANVerifier. Onde a precondição não pode ser provada, o TwoSum (6 flops) é utilizado para garantir a correção.
Comutatividade: Para garantir a concordância bit a bit sob troca de operandos ( $x \leftrightarrow y$ ), o algoritmo reassocia as somas diagonais para que os pares transpostos (ex: $P_{ij}$ e $P_{ji}$ ) sejam processados primeiro. Isso é alcançado sem aumentar a contagem de operações.
Variante Exata: Uma variante de "destilação" (FMA Exato) também é implementada como referência. Ela realiza uma expansão completa livre de erro seguida por múltiplas varreduras de TwoSum para alcançar limites de erro relativos ao resultado, embora com um custo computacional significativamente maior.

3. Principais Contribuições

3.1 Construções de FMA Livres de Desvio Minimais

O artigo apresenta algoritmos FMA livres de desvio minimais e verificados por máquina com as seguintes contagens de operações (a instrução FMA fundida conta como 1):

DW (K=2): 17 flops (vs. 29 para a composição de mul+add livre de desvio).
TW (K=3): 66 flops (vs. 96).
QW (K=4): 146 flops (vs. 209).

Essas contagens representam as construções minimais onde cada precondição de FastTwoSum é verificada por máquina.

3.2 Limites de Erro Verificados por Máquina

Usando FPANVerifier, os autores certificam limites de erro relativos a $(|xy| + |c|)$ para todas as precisões:

DW: $34 u^2 (|xy| + |c|)$
TW: $184 u^3 (|xy| + |c|)$
QW: $812 u^4 (|xy| + |c|)$
A validade de cada precondição de FastTwoSum e a concordância bit a bit entre a variante provada e uma variante ingênua (onde o FastTwoSum é colocado na cauda independentemente da prova) são confirmadas.

3.3 Comutatividade

Os algoritmos propostos são bitwise comutativos em $x$ e $y$ para todos os seis tipos (DD/TD/QD/DS/TS/QS). Isso é alcançado pela simetrização da ordem de associação das adições simples, garantindo que $fma(x, y, c) \equiv fma(y, x, c)$ sem adicionar operações.

3.4 Variantes Especializadas para Divisão e Raiz Quadrada

O artigo identifica que os resíduos intermediários em algoritmos de divisão e raiz quadrada podem não satisfazer as suposições de não sobreposição exigidas pelos FMA padrão. Consequentemente, uma variante "segura" é proposta para esses contextos (DW 20 / TW 69 / QW 149 flops), que rebaixa portões FastTwoSum não provados para TwoSum para garantir a precisão sem re-verificar toda a estrutura para cada contexto de uso.

4. Resultados Experimentais

Os algoritmos foram avaliados em duas plataformas:

Arm: NVIDIA GB10 (Grace-Blackwell, CPU Cortex-X925, GPU Blackwell).
x86: Nó H100 (CPU Intel Xeon Gold 6526Y, GPU H100).
Implementações: Escalar, AVX2, AVX-512, NEON, SVE2 e CUDA.

4.1 Kernels de Álgebra Linear (AXPY, GEMV, GEMM)

Aceleração (Speedup): O FMA proposto supera consistentemente a linha de base livre de desvio (BF) em cenários limitados por computação (compute-bound).
- AVX2 (x86): Acelerações de $\times 1.49$ (DD), $\times 1.32$ (TD) e $\times 1.47$ (QD) em GEMM.
- NEON (Arm): Acelerações de $\times 1.40$ (DD), $\times 1.42$ (TD) e $\times 1.47$ (QD) em GEMM.
- SVE2: Desempenho similar ao NEON com igual largura de lane, com QD GEMM atingindo $\times 1.62$ de aceleração sobre o BF.
- GPU (GB10): Em tipos de precisão dupla limitados por computação, as acelerações correspondem às razões teóricas de FLOPs ( $\times 1.71$ para DD, $\times 1.46$ para TD, $\times 1.40$ para QD). Em cargas de trabalho limitadas por largura de banda (precisão simples ou H100), as acelerações são próximas de $\times 1.00$ .
Precisão: O FMA proposto mantém a precisão de trabalho comparável aos métodos livres de desvio existentes (Q/BF). Em cenários de cancelamento, o comportamento do erro é numericamente idêntico à linha de base. O FMA Exato oferece precisão relativa ao resultado superior, mas incorre em um atraso de 2.5–5.0 $\times$ .

4.2 Divisão e Raiz Quadrada

Divisão: O FMA proposto acelera significativamente divisões longas, particularmente para precisões mais altas.
- NEON/SVE2: Acelerações de $\times 1.54$ a $\times 2.11$ (divisão QD atinge $\times 2.11$ , excedendo a razão de contagem de operações de 1.51 devido ao dobramento de duas cadeias de normalização seriais em uma).
- GB10 (Apenas Computação): Acelerações de $\times 1.25$ a $\times 1.61$ .
Raiz Quadrada: O FMA proposto atinge acelerações de $\times 1.51$ a $\times 1.61$ com zero perda de precisão em comparação com a linha de base. Isso ocorre porque a iteração de Newton converge bem abaixo da unidade de arredondamento, tornando o erro final dominado pela última multiplicação comum a todos os métodos.

4.3 Base de Precisão Simples (DS/TS/QS)

Os algoritmos foram estendidos com sucesso para componentes de precisão simples, mantendo a precisão de trabalho e alcançando acelerações de $\times 1.37$ a $\times 1.83$ sobre a linha de base BF.

5. Significância e Alegações

O artigo afirma que o FMA fundido livre de desvio proposto representa uma construção minimal e verificada por máquina que funde com sucesso as duas etapas de multiplicação e adição livres de desvio existentes em uma única operação.

Desempenho: Fornece acelerações reais (até $\times 2.11$ em divisão em CPUs e $\times 1.71$ em GEMM em GPUs) ao reduzir as contagens de operações e encurtar as cadeias de dependência, sendo particularmente benéfico para precisões mais altas (TW/QW).
Corretude: Os algoritmos são rigorosamente verificados. Os limites de erro e as precondições de FastTwoSum são provados por máquina para todas as precisões, e a concordância bit a bit entre as implementações escalar, SIMD e GPU é confirmada via testes extensivos (mais de 200.000 tentativas).
Generalidade: A abordagem não se limita à álgebra linear; ela acelera efetivamente algoritmos de divisão e raiz quadrada, que dependem fortemente de operações MAC.
Comutatividade: Ao contrário de algumas abordagens anteriores livres de desvio, o FMA proposto preserva a comutatividade bitwise, uma propriedade crucial para a reprodutibilidade em reduções paralelas.

Os autores posicionam este trabalho como um substituto prático para a composição de operações separadas livres de desvio, ofereando uma aceleração "drop-in" para bibliotecas de aritmética de múltiplos componentes sem sacrificar a precisão ou a provabilidade. Sugere-se como trabalho futuro explorar estruturas de renormalização alternativas (ex: estilo Priest) para potencialmente reduzir as contagens de operações enquanto mantém a verificabilidade por máquina.