🔢 mathematics

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

Questo articolo propone e valuta nuovi algoritmi di moltiplicazione-accumulo fusi e privi di rami per l'aritmetica a precisione multipla di tipo double-word, triple-word e quadruple-word, dimostrando che essi ottengono ulteriori miglioramenti delle prestazioni rispetto ai metodi esistenti eliminando i rami condizionali.

Autori originali: Tomonori Kouya

Pubblicato 2026-07-14

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Tomonori Kouya

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di cercare di costruire una calcolatrice super precisa usando solo mattoncini LEGO standard, di quelli pronti all'uso. Questi mattoncini sono i numeri a virgola mobile normali del tuo computer. Di solito, quando impili questi mattoncini per creare un numero "double-word" (due mattoncini), "triple-word" (tre mattoncini) o "quadruple-word" (quattro mattoncini), devi controllare costantemente la dimensione dei pezzi mentre costruisci. Se un pezzo è troppo grande o troppo piccolo, devi fermarti, fare una pausa e riorganizzare la pila. Nel mondo dei chip per computer, queste "pause" sono chiamate branch (salti condizionali).

Se provi a costruire un milione di queste pile contemporaneamente (come su una moderna scheda grafica o un processore potente), queste pause diventano un incubo. È come un ingorgo stradale dove ogni auto deve fermarsi per controllare un cartello diverso prima di procedere. Alcune auto vanno a sinistra, altre a destra, e l'intera fila si blocca. Questo è chiamato "lane divergence" (divergenza di lane), e distrugge le prestazioni.

La Grande Scoperta: L'Autostrada "Senza Soste"
Il paper di Tomonori Kouya introduce un nuovo modo per costruire queste pile che non si ferma mai a controllare i cartelli. È un algoritmo "branch-free" (senza salti condizionali). Inveve di chiedere "Questo pezzo è abbastanza grande?" e aspettare una risposta, il nuovo metodo utilizza un percorso pianificato con cura che funziona perfettamente a prescindere dall'aspetto dei pezzi.

Il paper dimostra, usando un robot matematico super intelligente (un risolutore SMT chiamato FPANVerifier), che questo nuovo percorso è sicuro e accurato per tutti gli standard informatici. Il risultato principale è che, rimuovendo queste pause "fermati e controlla", il computer può calcolare molto più velocemente.

Il Trucco Magico: Fondere il Movimento
Il paper si concentra su un movimento specifico chiamato Fused Multiply-Add (FMA). Immagina di dover moltiplicare due numeri e poi aggiungere un terzo. Di solito, lo fai in due passaggi:

Moltiplicazione (e forse una pausa per sistemare il risultato).
Addizione (e forse un'altra pausa).

L'autore propone una versione "Fusa" (Fused) che fa entrambe le cose in un unico movimento fluido, come un ninja che lancia un coltello e lo riprende con un unico respiro.

Per il Double-Word (2 mattoncini): Il vecchio modo richiedeva 29 passaggi. Il nuovo modo ne richiede solo 17.
Per il Triple-Word (3 mattoncini): Il vecchio modo richiedeva 96 passaggi. Il nuovo modo ne richiede 66.
Per il Quadruple-Word (4 mattoncini): Il vecchio modo richiedeva 209 passaggi. Il nuovo modo ne richiede 146.

Il paper discute anche un metodo di "scorciatoia" proposto da altri ricercatori (il metodo a 6 passaggi). Fondamentalmente, questa scorciatoia NON è generalmente valida. È uno strumento ad alta velocità che funziona solo se i numeri sono già perfettamente disposti in un modo specifico (nello specifico, se il numero aggiunto è almeno il doppio del prodotto). Se provi a usare questa scorciatoia su problemi matematici generali come la divisione o la radice quadrata, dove non puoi garantire che quei numeri si allineino, l'accuratezza degrada drasticamente. Il nuovo metodo dell'autore, invece, funziona per qualsiasi numero senza richiedere disposizioni speciali, rendendolo un vero sostituto "drop-in" per la matematica ad alta precisione generale.

Quanto Siamo Sicuri?
Gli autori sono incredibilmente fiduciosi, ma sostengono la loro tesi con prove concrete, non con semplici supposizioni.

Verifica tramite Macchina: Non si sono limitati a scrivere del codice sperando che funzionasse; hanno usato un programma per computer per dimostrare matematicamente che l'errore nel loro nuovo metodo è minuscolo (specificamente, limitato da formule come $34u^2$ , $184u^3$ e $812u^4$ , dove $u$ è l'errore di arrotondamento infinitesimo di un singolo numero).
Test Ovunque: Hanno testato i loro nuovi algoritmi su due supercomputer molto diversi: un chip basato su Arm (GB10) e un chip basato su Intel (H100).
I Risultati:
- Sul chip Arm, il nuovo metodo è stato da 1,5 a 2,1 volte più veloce per i calcoli di divisione e radice quadrata.
- Sul chip Intel, è stato da 1,2 a 1,6 volte più veloce per divisione e radice quadrata.
- Per compiti matematici intensivi come la moltiplicazione di matrici (GEMM), l'accelerazione è stata ancora più drammatica sul chip Arm, raggiungendo fino a 2,0 volte la velocità per i numeri triple-word.

L'Alternativa "Esatta"
Il paper menziona anche una versione "Perfetta" di questo trucco chiamata Exact FMA. Questa versione è ancora più precisa, ma ha un prezzo pesante: è da 6 a 11 volte più lenta del nuovo metodo proposto. Gli autori suggeriscono di usare questa versione "Perfetta" solo quando è assolutamente, al 100%, necessaria la massima accuratezza e non ci si preoccupa della velocità. Per quasi tutto il resto, il metodo "branch-free" proposto è il vincitore.

E il "Vecchio" Modo?
Il paper corregge anche un errore di una versione precedente di questa ricerca. Precedentemente, gli autori avevano confrontato il loro nuovo metodo con un vecchio metodo "completamente distillato" che era incredibilmente lento e inefficiente. Si sono resi conto che non era un confronto equo. Quando hanno confrontato il loro nuovo metodo con l'effettivo metodo "branch-free" standard (che è già piuttosto veloce), il nuovo metodo ha comunque vinto, ma l'accelerazione è stata più modesta (circa da 1,3 a 1,7 volte più veloce). Questo è comunque un grande successo, ma è un risultato più realistico.

In Sintesi
Questo paper dimosta che eliminando le pause "fermati e controlla" nella matematica ad alta precisione, possiamo rendere i computer significativamente più veloci senza perdere accuratezza. È come passare da un'auto che deve fermarsi a ogni incrocio a un'auto che può volare sopra di essi. Gli autori hanno dimostrato che questo funziona, lo hanno testato su hardware reale e hanno mostato che è pronto per essere utilizzato nella prossima generazione di calcolatrici super veloci.

Riepilogo Tecnico: Valutazione delle Prestazioni di Algoritmi Fused Multiply-Add Branch-Free per l'Aritmetica Multi-Componente a Precisione Multipla

1. Definizione del Problema

L'aritmetica multi-componente a precisione multipla (ad es., Double-Word/DW, Triple-Word/TW, Quadruple-Word/QW) ottiene alte prestazioni raggruppando componenti standard binary64 (o binary32) e gestendo i riporti esattamente tramite Error-Free Transformations (EFT). Tuttavia, le fasi di rinormalizzazione in questi algoritmi dipendono tipicamente da rami if basati sull'entità dei valori intermedi. Questi rami causano significativi penalità di prestazione nelle implementazioni SIMD e GPU a causa della divergenza di lane o warp.

Sebbene Zhang e Aiken abbiano precedentemente proposto algoritmi branch-free per l'addizione e la moltiplicazione DW/TW/QW, la composizione di queste operazioni branch-free separate rimane subottimale. Nello specifico, eseguire un'operazione fused multiply-add (FMA) $z \leftarrow x \cdot y + c$ componendo sequenzialmente una moltiplicazione branch-free e un'addizione branch-free comporta un elevato conteggio di operazioni (ad es., 29 flop per DW, 96 per TW, 209 per QW) e ridondanti fasi di rinormalizzazione.

2. Metodologia

Il documento propone nuovi algoritmi fused multiply-add branch-free per l'aritmetica DW, TW e QW (e le loro varianti a precisione singola base DS, TS, QS). La metodologia principale prevede:

Struttura Algoritmica: Il FMA proposto calcola $z \leftarrow x \cdot y + c$ $z \leftarrow x \cdot y + c$ in un unico stadio fuso anziché comporre separatamente moltiplicazione e addizione. Il processo prevede:
1. Espansione del Prodotto: Decomposizione dei prodotti dei componenti utilizzando TwoProd.
2. Accumulazione per Peso: Raccolta dei termini che arrivano alla stessa posizione di potenza di due utilizzando catene di TwoSum.
3. Rinormalizzazione: Rimodellamento del risultato in $K$ componenti non sovrapponibili.
Selezione delle Porte e Verifica: Un principio di progettazione critico è la selezione delle porte di rinormalizzazione basata su precondizioni verificabili dalla macchina. L'algoritmo utilizza FastTwoSum (3 flop) solo dove la precondizione $\text{exp}(a) \ge \text{exp}(b)$ può essere provata dalla macchina per tutte le precisioni $p$ tramite il solver SMT z3 attraverso lo strumento FPANVerifier. Laddove la precondizione non può essere provata, viene utilizzato TwoSum (6 flop) per garantire la correttezza.
Commutatività: Per garantire l'accordo bit a bit sotto scambio di operandi ( $x \leftrightarrow y$ ), l'algoritmo ri-associa le somme diagonali in modo che le coppie trasposte (ad es., $P_{ij}$ e $P_{ji}$ ) siano elaborate per prime. Ciò è ottenuto senza aumentare il conteggio delle operazioni.
Variante Esatta: Una variante di "distillazione" (Exact FMA) è anche implementata come riferimento. Essa esegue un'espansione completa error-free seguita da molteplici passaggi TwoSum per ottenere limiti di errore relativi al risultato, sebbene con un costo computazionale significamente più elevato.

3. Contributi Chiave

3.1 Costruzioni FMA Branch-Free Minime

Il documento presenta costruzioni FMA branch-free minime e verificate dalla macchina con i seguenti conteggi di operazioni (l'istruzione FMA fusa conta come 1):

DW (K=2): 17 flop (vs. 29 per la composizione branch-free mul+add).
TW (K=3): 66 flop (vs. 96).
QW (K=4): 146 flop (vs. 209).

Questi conteggi rappresentano le costruzioni minime in cui ogni precondizione di FastTwoSum è verificata dalla macchina.

3.2 Limiti di Errore Verificati dalla Macchina

Utilizzando FPANVerifier, gli autori certificano i limiti di errore relativi a $(|xy| + |c|)$ per tutte le precisioni:

DW: $34 u^2 (|xy| + |c|)$
TW: $184 u^3 (|xy| + |c|)$
QW: $812 u^4 (|xy| + |c|)$
La validità di ogni precondizione di FastTwoSum e l'accordo bit a bit tra la variante provata e una variante ingenua (dove FastTwoSum è posizionato alla fine indipendentemente dalla prova) sono confermati.

3.3 Commutatività

Gli algoritmi proposti sono bitwise commutativi in $x$ e $y$ per tutti i sei tipi (DD/TD/QD/DS/TS/QS). Ciò è ottenuto simmetrizzando l'ordine di associazione delle addizioni semplici, garantendo che $fma(x, y, c) \equiv fma(y, x, c)$ senza aggiungere operazioni.

3.4 Varianti Specializzate per Divisione e Radice Quadrata

Il documento identifica che i residui intermedi negli algoritmi di divisione e radice quadrata potrebbero non soddisfare le assunzioni di non sovrapposizione richieste per gli standard FMA. Di conseguenza, viene proposta una variante "sicura" per questi contesti (DW 20 / TW 69 / QW 149 flop), che declassa le porte FastTwoSum non provate a TwoSum per garantire l'accuratezza senza dover ri-verificare l'intera struttura per ogni contesto d'uso.

4. Risultati Sperimentali

Gli algoritmi sono stati valutati su due piattaforme:

Arm: NVIDIA GB10 (Grace-Blackwell, CPU Cortex-X925, GPU Blackwell).
x86: Nodo H100 (CPU Intel Xeon Gold 6526Y, GPU H100).
Implementazioni: Scalare, AVX2, AVX-512, NEON, SVE2 e CUDA.

4.1 Kernel di Algebra Lineare (AXPY, GEMV, GEMM)

Speedup: Il FMA proposto supera costantemente la baseline branch-free (BF) in scenari compute-bound.
- AVX2 (x86): Speedup di $\times 1.49$ (DD), $\times 1.32$ (TD) e $\times 1.47$ (QD) in GEMM.
- NEON (Arm): Speedup di $\times 1.40$ (DD), $\times 1.42$ (TD) e $\times 1.47$ (QD) in GEMM.
- SVE2: Prestazioni simili a NEON a parità di lane width, con il GEMM QD che raggiunge uno speedup di $\times 1.62$ rispetto a BF.
- GPU (GB10): Sui tipi a doppia precisione compute-bound, gli speedup corrispondono ai rapporti teorici di FLOP ( $\times 1.71$ per DD, $\times 1.46$ per TD, $\times 1.40$ per QD). Sui carichi di lavoro bandwidth-bound (precisione singola o H100), gli speedup sono più vicini a $\times 1.00$ .
Accuratezza: Il FMA proposto mantiene un'accuratezza operativa comparabile ai metodi branch-free esistenti (Q/BF). Nei casi di cancellazione, il comportamento dell'errore è numericamente identico alla baseline. L'Exact FMA offre un'accuratezza relativa al risultato superiore, ma comporta un rallentamento di 2.5–5.0 $\times$ .

4.2 Divisione e Radice Quadrata

Divisione: Il FMA proposto accelera significativamente la divisione lunga, in particolare per le precisioni più elevate.
- NEON/SVE2: Speedup da $\times 1.54$ a $\times 2.11$ (la divisione QD raggiunge $\times 2.11$ , superando il rapporto di conteggio delle operazioni di 1.51 grazie al folding di due catene di normalizzazione seriali in una sola).
- GB10 (Solo Compute): Speedup da $\times 1.25$ a $\times 1.61$ .
Radice Quadrata: Il FMA proposto ottiene speedup da $\times 1.51$ a $\times 1.61$ con zero perdita di accuratezza rispetto alla baseline. Questo perché l'iterazione di Newton converge ben al di sotto dell'unità di arrotondamento, rendendo l'errore finale dominato dall'ultima moltiplicazione comune a tutti i metodi.

4.3 Base a Precisione Singola (DS/TS/QS)

Gli algoritmi sono stati estesi con successo alla precisione singola, mantenendo l'accuratezza operativa e ottenendo speedup da $\times 1.37$ a $\times 1.83$ rispetto alla baseline BF.

5. Significato e Rivendicazioni

Il documento sostiene che il FMA fused branch-free proposto rappresenta una costruzione minima e verificata dalla macchina che riesce a fondere le due fasi delle esistenti moltiplicazioni e addizioni branch-free in un'unica operazione.

Prestazioni: Fornisce speedup reali (fino a $\times 2.11$ nella divisione su CPU e $\times 1.71$ in GEMM su GPU) riducendo i conteggi delle operazioni e accorciando le catene di dipendenza, beneficiando particolarmente delle precisioni più elevate (TW/QW).
Correttezza: Gli algoritmi sono rigorosamente verificati. I limiti di errore e le precondizioni di FastTwoSum sono provati dalla macchina per tutte le precisioni, e l'accordo bit a bit tra le implementazioni scalari, SIMD e GPU è confermato tramite test estesi (oltre 200.000 prove).
Generalità: L'approccio non è limitato all'algebra lineare; accelera efficacementamente gli algoritmi di divisione e radice quadrata, che si basano pesantemente sulle operazioni MAC.
Commutatività: A differenza di alcuni approcci branch-free precedenti, il FMA proposto preserva la commutatività bitwise, una proprietà cruciale per la riproducibilità nelle riduzioni parallele.

Gli autori pongono questo lavoro come un sostituto pratico per la composizione di operazioni branch-free separate, offrendo un'accelerazione "drop-in" per le librerie di aritmetica multi-componente senza sacrificare l'accuratezza o la verificabilità. Il lavoro futuro suggerisce di esplorare strutture di rinormalizzazione alternative (ad es., stile Priest) per potenzialmente ridurre ulteriormente i conteggi delle operazioni mantenendo la verificabilità dalla macchina.