2025-11-18T22:43:13.755250

Sparse Iterative Solvers Using High-Precision Arithmetic with Quasi Multi-Word Algorithms

Mukunoki, Ozaki
To obtain accurate results in numerical computation, high-precision arithmetic is a straightforward approach. However, most processors lack hardware support for floating-point formats beyond double precision (FP64). Double-word arithmetic (Dekker 1971) extends precision by using standard floating-point operations to represent numbers with twice the mantissa length. Building on this concept, various multi-word arithmetic methods have been proposed to further increase precision by combining additional words. Simplified variants, known as quasi algorithms, have also been introduced, which trade a certain loss of accuracy for reduced computational cost. In this study, we investigate the performance of quasi algorithms for double- and triple-word arithmetic in sparse iterative solvers based on the Conjugate Gradient method, and compare them with both non-quasi algorithms and standard FP64. We evaluate execution time on an x86 processor, the number of iterations to convergence, and solution accuracy. Although quasi algorithms require appropriate normalization to preserve accuracy - without it, convergence cannot be achieved - they can still reduce runtime when normalization is applied correctly, while maintaining accuracy comparable to full multi-word algorithms. In particular, quasi triple-word arithmetic can yield more accurate solutions without significantly increasing execution time relative to double-word arithmetic and its quasi variant. Furthermore, for certain problems, a reduction in iteration count contributes to additional speedup. Thus, quasi triple-word arithmetic can serve as a compelling alternative to conventional double-word arithmetic in sparse iterative solvers.
academic

Risolutori Iterativi Sparsi Utilizzando Aritmetica ad Alta Precisione con Algoritmi Quasi Multi-Parola

Informazioni Fondamentali

  • ID Articolo: 2510.13536
  • Titolo: Sparse Iterative Solvers Using High-Precision Arithmetic with Quasi Multi-Word Algorithms
  • Autori: Daichi Mukunoki (Nagoya University), Katsuhisa Ozaki (Shibaura Institute of Technology)
  • Classificazione: cs.MS (Mathematical Software)
  • Data di Pubblicazione: 15 ottobre 2025 (preprint arXiv)
  • Link Articolo: https://arxiv.org/abs/2510.13536

Riassunto

Per ottenere risultati accurati nel calcolo numerico, l'aritmetica ad alta precisione rappresenta un approccio diretto. Tuttavia, la maggior parte dei processori manca di supporto hardware per formati in virgola mobile al di là della doppia precisione (FP64). L'aritmetica a doppia parola (Dekker 1971) estende la precisione rappresentando numeri con lunghezza di mantissa doppia utilizzando operazioni in virgola mobile standard. Basandosi su questo concetto, sono stati proposti vari metodi di aritmetica multi-parola che aumentano ulteriormente la precisione combinando parole aggiuntive. Varianti semplificate, denominate algoritmi quasi, sono state introdotte, scambiando una certa perdita di precisione per una riduzione dei costi computazionali. Questo studio investiga le prestazioni degli algoritmi quasi per l'aritmetica a doppia e tripla parola in risolutori iterativi sparsi basati sul metodo del gradiente coniugato, confrontandoli con varianti non-quasi e FP64 standard.

Contesto di Ricerca e Motivazione

Problemi Fondamentali

  1. Limitazioni Hardware: La maggior parte dei processori manca di supporto hardware per formati in virgola mobile al di là di FP64, limitando l'implementazione del calcolo numerico ad alta precisione
  2. Requisiti di Precisione nei Risolutori Iterativi Sparsi: Nella risoluzione di grandi sistemi lineari sparsi, gli errori di arrotondamento aumentano il numero di iterazioni necessarie per la convergenza, influenzando la precisione e l'efficienza della soluzione
  3. Compromesso tra Prestazioni e Precisione: Sebbene i metodi tradizionali di aritmetica multi-parola possano migliorare la precisione, comportano un sovraccarico computazionale considerevole

Importanza della Ricerca

  • I risolutori iterativi sparsi sono ampiamente applicati nel calcolo scientifico e nelle applicazioni ingegneristiche
  • L'aritmetica ad alta precisione può migliorare la convergenza, riducendo il numero di iterazioni
  • Nelle applicazioni con memoria limitata, il sovraccarico aggiuntivo dell'aritmetica multi-parola potrebbe essere mascherato dalla latenza della memoria

Limitazioni dei Metodi Esistenti

  • L'aritmetica multi-parola tradizionale (come DW, TW) presenta costi computazionali elevati
  • Sebbene gli algoritmi quasi riducano i costi computazionali, potrebbero causare perdita di precisione
  • Manca una valutazione sistematica delle prestazioni degli algoritmi quasi nei risolutori iterativi

Contributi Fondamentali

  1. Valutazione Sistematica delle Prestazioni degli Algoritmi Quasi: Prima valutazione sistematica delle prestazioni degli algoritmi QDW e QTW nei risolutori iterativi sparsi
  2. Scoperta del Ruolo Critico della Normalizzazione: Dimostrazione dell'importanza della normalizzazione appropriata per la convergenza degli algoritmi quasi
  3. Proposta di QTW come Alternativa Efficace: Dimostrazione che l'aritmetica quasi tripla-parola (QTW) può fungere da alternativa efficace all'aritmetica doppia-parola tradizionale
  4. Analisi Completa delle Prestazioni: Valutazione integrata da tre dimensioni: tempo di esecuzione, numero di iterazioni e precisione della soluzione

Dettagli Metodologici

Definizione del Compito

Risolvere il sistema lineare simmetrico definito positivo Ax = b, dove:

  • A è una matrice sparsa simmetrica n×n definita positiva
  • b è il vettore del termine noto
  • x è il vettore da risolvere

Utilizzare il metodo del gradiente coniugato (CG) per la risoluzione iterativa, valutando le prestazioni dell'aritmetica a diversi livelli di precisione.

Architettura dell'Aritmetica Multi-Parola

Algoritmi Fondamentali

Algoritmi di Trasformazione Libera da Errori:

  • TwoSum(a,b): Decompone a+b in risultato in virgola mobile x e errore di arrotondamento y
  • QuickTwoSum(a,b): Variante efficiente di TwoSum, richiede |a|≥|b|
  • TwoProdFMA(a,b): Decompone a×b in risultato e errore utilizzando operazioni FMA

Aritmetica Doppia-Parola (DW)

DWadd: [c1,c2] = DWadd(a1,a2,b1,b2)
- Operandi: 11 operazioni FP64
- Include passo di normalizzazione (QuickTwoSum)

DWmul: [c1,c2] = DWmul(a1,a2,b1,b2)  
- Operandi: 7 operazioni FP64
- Include passo di normalizzazione

Aritmetica Quasi Doppia-Parola (QDW)

  • Omette il passo di normalizzazione, permettendo sovrapposizione tra parole alte e basse
  • QDWadd: 8 operazioni, QDWmul: 4 operazioni
  • Riduzione significativa dei costi computazionali

Aritmetica Quasi Tripla-Parola (QTW)

QTWadd: [c1,c2,c3] = QTWadd(a1,a2,a3,b1,b2,b3)
- Operandi: 21 operazioni FP64
- Non impone fl(c1+c2)=c1 e fl(c2+c3)=c2

QTWmul: [c1,c2,c3] = QTWmul(a1,a2,a3,b1,b2,b3)
- Operandi: 24 operazioni FP64

Punti di Innovazione Tecnica

  1. Ottimizzazione Vettorizzazione SIMD:
    • Utilizzo dei set di istruzioni AVX2 e AVX-512 per la vettorizzazione
    • L'algoritmo QTW elimina i rami condizionali, rendendolo più adatto alla vettorizzazione
  2. Strategie di Normalizzazione:
    • Normalizzazione eseguita dopo l'aggiornamento del vettore residuo nel metodo CG
    • Utilizzo dell'algoritmo VecSum3 per mitigare la sovrapposizione di bit nell'aritmetica tripla-parola
  3. Implementazione a Precisione Mista:
    • Matrice di coefficienti A e vettore del termine noto b memorizzati in FP64
    • Calcoli interni utilizzano l'aritmetica multi-parola corrispondente

Configurazione Sperimentale

Dataset

Utilizzo di 8 matrici simmetriche definite positive dalla collezione SuiteSparse:

MatriceDimensione nElementi non-zero nnzDominio Applicativo
Hook_14981.498.02360.917.445Problemi Strutturali
bone010986.70347.851.783Riduzione di Modelli
nd24k72.00028.715.634Problemi 2D/3D
crankseg_263.83814.148.858Problemi Strutturali

Metriche di Valutazione

  1. Tempo di Esecuzione: Tempo per iterazione e tempo totale di convergenza
  2. Numero di Iterazioni: Numero di iterazioni necessarie per raggiungere la convergenza
  3. Precisione della Soluzione: Norma dell'errore relativo ||xk-x*||2/||x*||2

Metodi di Confronto

  • CG-FP64: Implementazione standard a doppia precisione
  • CG-DW: Implementazione aritmetica doppia-parola
  • CG-QDW: Implementazione aritmetica quasi doppia-parola
  • CG-TW: Implementazione aritmetica tripla-parola
  • CG-QTW: Implementazione aritmetica quasi tripla-parola

Dettagli di Implementazione

  • Piattaforma Hardware: CPU Intel Xeon Gold 6230 (20 core, 2,10-3,90 GHz)
  • Compilatore: g++ 11.3.0, opzioni di ottimizzazione -O3 -march=native
  • Parallelizzazione: OpenMP + vettorizzazione SIMD
  • Tolleranza di Convergenza: ε = 10^-16, 10^-24, 10^-32

Risultati Sperimentali

Risultati Principali

Analisi del Sovraccarico di Prestazioni

Sovraccarico di tempo di esecuzione relativo a FP64 (100 iterazioni):

  • CG-QDW: circa 1,3 volte
  • CG-DW: circa 2,1 volte
  • CG-QTW: circa 2,4 volte
  • CG-TW: fino a 67 volte

Confronto delle Prestazioni di Convergenza

Risultati tipici con tolleranza di convergenza ε=10^-16:

MatriceTempo FP64(s)/IterazioniTempo QDW(s)/IterazioniTempo QTW(s)/Iterazioni
bone010170/21780120/12547150/11352
pdb1HYS5,4/128073,4/62854,9/5346

Scoperte Chiave

  1. Necessità della Normalizzazione:
    • Senza normalizzazione, gli algoritmi quasi non convergono
    • La normalizzazione dopo l'aggiornamento del vettore residuo assicura la convergenza
  2. Vantaggi di QTW:
    • Riduzione significativa del sovraccarico computazionale rispetto a TW
    • Raggiungimento di precisione comparabile a TW
    • Supporto per vettorizzazione SIMD con prestazioni superiori
  3. Benefici della Riduzione del Numero di Iterazioni:
    • L'aritmetica ad alta precisione riduce il numero di iterazioni
    • Il tempo di esecuzione totale può essere inferiore all'implementazione FP64

Analisi del Throughput

Throughput dell'operazione SpMV (GB/s):

  • FP64 e QDW: prossimi al limite della larghezza di banda della memoria (circa 90 GB/s)
  • DW e QTW: raggiungono il limite della memoria dopo ottimizzazione SIMD
  • TW: prestazioni significativamente ridotte a causa dell'impatto dei rami

Lavori Correlati

Sviluppo dell'Aritmetica Multi-Parola

  • Teoria Fondamentale: Aritmetica doppia-parola di Dekker (1971)
  • Metodi Estesi: Aritmetica tripla-parola (TW), quadrupla-parola (QW)
  • Varianti Semplificate: Algoritmi quasi (QDW, QTW, QQW)

Librerie di Algebra Lineare ad Alta Precisione

  • Libreria QD: Implementazione Fortran/C++ di aritmetica doppia-parola e quadrupla-parola
  • XBLAS: Routine BLAS basate su aritmetica DW
  • MPLAPACK: BLAS e LAPACK ad alta precisione

Applicazioni di Risolutori Iterativi Sparsi

  • Ricerca su risolutori CG a quadrupla precisione
  • Metodi a precisione mista
  • Moltiplicazione matrice-vettore sparsa esatta secondo lo schema Ozaki

Conclusioni e Discussione

Conclusioni Principali

  1. Fattibilità degli Algoritmi Quasi: Attraverso una normalizzazione appropriata, gli algoritmi quasi possono essere applicati efficacemente nei risolutori iterativi sparsi
  2. Vantaggi di QTW: L'aritmetica quasi tripla-parola fornisce un buon equilibrio tra precisione e prestazioni
  3. Potenziale di Miglioramento delle Prestazioni: Su alcuni problemi, la riduzione del numero di iterazioni può portare a ulteriori effetti di accelerazione

Limitazioni

  1. Sovraccarico di Normalizzazione: Necessità di compromesso tra precisione e tempo di esecuzione
  2. Dipendenza dal Problema: L'effetto del miglioramento delle prestazioni dipende dalle caratteristiche specifiche del problema
  3. Ambito di Valutazione: Valutazione limitata al metodo CG di base, senza inclusione di tecniche di precondizionamento

Direzioni Future

  1. Ottimizzazione delle Strategie di Normalizzazione: Ricerca sull'impatto di una normalizzazione più frequente sulla precisione
  2. Estensione ad Altri Metodi Iterativi: Valutazione dell'applicazione in altri risolutori
  3. Applicazioni in Ambienti Distribuiti: Potenziale in ambienti dove la latenza di comunicazione è dominante
  4. Implementazione di Formati a Bassa Precisione: Implementazione di aritmetica multi-parola utilizzando FP16/FP32 su processori AI

Valutazione Approfondita

Punti di Forza

  1. Ricerca Sistematica: Prima valutazione sistematica delle prestazioni degli algoritmi quasi nei risolutori iterativi
  2. Valore Pratico Elevato: L'algoritmo QTW fornisce uno schema pratico di calcolo ad alta precisione
  3. Esperimenti Completi: Valutazione integrata da molteplici dimensioni (tempo, precisione, convergenza)
  4. Innovazione Tecnica: Progettazione ragionevole dell'ottimizzazione SIMD e delle strategie di normalizzazione

Insufficienze

  1. Analisi Teorica Limitata: Mancanza di analisi teorica dell'accumulo di errori negli algoritmi quasi
  2. Ambito di Valutazione Limitato: Valutazione limitata al metodo CG, mancanza di verifica su altri metodi iterativi
  3. Strategie di Normalizzazione Singole: Tentativo di una sola posizione e frequenza di normalizzazione

Impatto

  • Contributo Accademico: Fornisce nuove scelte algoritmiche per il campo del calcolo numerico ad alta precisione
  • Valore Pratico: L'algoritmo QTW può essere direttamente applicato a problemi di calcolo scientifico reale
  • Riproducibilità: Descrizione dettagliata dei dettagli di implementazione, facilitando la riproduzione

Scenari Applicabili

  1. Calcolo Scientifico: Risoluzione di grandi sistemi lineari sparsi che richiedono alta precisione
  2. Simulazione Ingegneristica: Applicazioni come analisi strutturale, calcolo di campi elettromagnetici
  3. Ambienti con Risorse Limitate: Sistemi che mancano di supporto hardware per precisione quadrupla

Bibliografia

L'articolo cita 29 riferimenti correlati, coprendo aree chiave come teoria dell'aritmetica multi-parola, librerie di algebra lineare ad alta precisione, risolutori iterativi sparsi, fornendo una base teorica solida per la ricerca.