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

Solveurs Itératifs Creux Utilisant l'Arithmétique Haute Précision avec Algorithmes Quasi Multi-Mots

Informations Fondamentales

  • ID de l'article: 2510.13536
  • Titre: Sparse Iterative Solvers Using High-Precision Arithmetic with Quasi Multi-Word Algorithms
  • Auteurs: Daichi Mukunoki (Université de Nagoya), Katsuhisa Ozaki (Institut Technologique de Shibaura)
  • Classification: cs.MS (Logiciels Mathématiques)
  • Date de publication: 15 octobre 2025 (prépublication arXiv)
  • Lien de l'article: https://arxiv.org/abs/2510.13536

Résumé

Afin d'obtenir des résultats précis en calcul numérique, l'arithmétique haute précision constitue une approche directe. Cependant, la plupart des processeurs manquent de support matériel pour les formats de nombres flottants au-delà de la double précision (FP64). L'arithmétique double-mot (Dekker 1971) étend la précision en représentant des nombres avec une longueur de mantisse doublée en utilisant des opérations en virgule flottante standard. Sur la base de ce concept, diverses méthodes d'arithmétique multi-mots ont été proposées, augmentant davantage la précision en combinant des mots supplémentaires. Des variantes simplifiées, appelées algorithmes quasi, ont également été introduites, échangeant une certaine perte de précision contre une réduction des coûts de calcul. Cette étude examine les performances des algorithmes quasi pour l'arithmétique double-mot et triple-mot dans les solveurs itératifs creux basés sur la méthode du gradient conjugué, et les compare avec les variantes non-quasi et la FP64 standard.

Contexte et Motivation de la Recherche

Problèmes Fondamentaux

  1. Problème de limitations matérielles: La plupart des processeurs manquent de support matériel pour les formats de nombres flottants au-delà de la double précision (FP64), limitant la mise en œuvre du calcul numérique haute précision
  2. Exigences de précision des solveurs itératifs creux: Lors de la résolution de grands systèmes linéaires creux, les erreurs d'arrondi augmentent le nombre d'itérations nécessaires pour la convergence, affectant la précision et l'efficacité de la résolution
  3. Compromis entre performance et précision: Bien que les méthodes d'arithmétique multi-mots traditionnelles puissent améliorer la précision, elles entraînent des frais de calcul importants

Importance de la Recherche

  • Les solveurs itératifs creux sont largement appliqués au calcul scientifique et aux applications d'ingénierie
  • L'arithmétique haute précision peut améliorer la convergence et réduire le nombre d'itérations
  • Dans les applications à mémoire limitée, les frais supplémentaires de l'arithmétique multi-mots peuvent être masqués par la latence mémoire

Limitations des Méthodes Existantes

  • L'arithmétique multi-mots traditionnelle (telle que DW, TW) présente des coûts de calcul élevés
  • Bien que les algorithmes quasi réduisent les coûts de calcul, ils peuvent entraîner une perte de précision
  • Absence d'évaluation systématique des performances des algorithmes quasi dans les solveurs itératifs

Contributions Principales

  1. Évaluation systématique des performances des algorithmes quasi: Première évaluation systématique des performances des algorithmes QDW et QTW dans les solveurs itératifs creux
  2. Découverte du rôle clé de la normalisation: Démonstration de l'importance de la normalisation appropriée pour la convergence des algorithmes quasi
  3. Proposition de QTW comme alternative efficace: Démonstration que l'arithmétique quasi triple-mot (QTW) peut servir d'alternative efficace à l'arithmétique double-mot traditionnelle
  4. Analyse de performance complète: Évaluation synthétique selon trois dimensions: temps d'exécution, nombre d'itérations et précision de résolution

Détails Méthodologiques

Définition de la Tâche

Résoudre le système linéaire symétrique défini positif Ax = b, où:

  • A est une matrice creuse symétrique définie positive n×n
  • b est le vecteur du second membre
  • x est le vecteur à résoudre

La méthode du gradient conjugué (CG) est utilisée pour la résolution itérative, évaluant les performances de l'arithmétique à différentes précisions.

Architecture de l'Arithmétique Multi-Mots

Algorithmes Fondamentaux

Algorithmes de transformation sans erreur:

  • TwoSum(a,b): Décompose a+b en résultat en virgule flottante x et erreur d'arrondi y
  • QuickTwoSum(a,b): Variante efficace de TwoSum, nécessitant |a|≥|b|
  • TwoProdFMA(a,b): Décompose a×b en résultat et erreur en utilisant l'opération FMA

Arithmétique Double-Mot (DW)

DWadd: [c1,c2] = DWadd(a1,a2,b1,b2)
- Opérandes: 11 opérations FP64
- Inclut l'étape de normalisation (QuickTwoSum)

DWmul: [c1,c2] = DWmul(a1,a2,b1,b2)  
- Opérandes: 7 opérations FP64
- Inclut l'étape de normalisation

Arithmétique Quasi Double-Mot (QDW)

  • Omet l'étape de normalisation, permettant le chevauchement des mots hauts et bas
  • QDWadd: 8 opérations, QDWmul: 4 opérations
  • Réduction significative des coûts de calcul

Arithmétique Quasi Triple-Mot (QTW)

QTWadd: [c1,c2,c3] = QTWadd(a1,a2,a3,b1,b2,b3)
- Opérandes: 21 opérations FP64
- N'impose pas fl(c1+c2)=c1 et fl(c2+c3)=c2

QTWmul: [c1,c2,c3] = QTWmul(a1,a2,a3,b1,b2,b3)
- Opérandes: 24 opérations FP64

Points d'Innovation Technique

  1. Optimisation de vectorisation SIMD:
    • Vectorisation utilisant les jeux d'instructions AVX2 et AVX-512
    • L'algorithme QTW élimine les branches conditionnelles, mieux adapté à la vectorisation
  2. Stratégies de normalisation:
    • Normalisation effectuée après la mise à jour du vecteur résidu dans la méthode CG
    • Utilisation de l'algorithme VecSum3 pour atténuer le chevauchement de bits dans l'arithmétique triple-mot
  3. Implémentation en précision mixte:
    • Matrice de coefficients A et vecteur du second membre b stockés en FP64
    • Les calculs internes utilisent l'arithmétique multi-mots correspondante

Configuration Expérimentale

Ensemble de Données

Utilisation de 8 matrices symétriques définies positives de la collection SuiteSparse:

MatriceDimension nÉléments non-nuls nnzDomaine d'Application
Hook_14981,498,02360,917,445Problèmes structurels
bone010986,70347,851,783Réduction de modèles
nd24k72,00028,715,634Problèmes 2D/3D
crankseg_263,83814,148,858Problèmes structurels

Indicateurs d'Évaluation

  1. Temps d'exécution: Temps par itération et temps total de convergence
  2. Nombre d'itérations: Nombre d'itérations nécessaires pour atteindre la convergence
  3. Précision de résolution: Norme d'erreur relative ||xk-x*||2/||x*||2

Méthodes Comparatives

  • CG-FP64: Implémentation en double précision standard
  • CG-DW: Implémentation en arithmétique double-mot
  • CG-QDW: Implémentation en arithmétique quasi double-mot
  • CG-TW: Implémentation en arithmétique triple-mot
  • CG-QTW: Implémentation en arithmétique quasi triple-mot

Détails d'Implémentation

  • Plateforme matérielle: Processeur Intel Xeon Gold 6230 (20 cœurs, 2,10-3,90 GHz)
  • Compilateur: g++ 11.3.0, options d'optimisation -O3 -march=native
  • Parallélisation: OpenMP + vectorisation SIMD
  • Tolérance de convergence: ε = 10^-16, 10^-24, 10^-32

Résultats Expérimentaux

Résultats Principaux

Analyse des Frais de Performance

Frais d'exécution relatifs à FP64 (100 itérations):

  • CG-QDW: environ 1,3 fois
  • CG-DW: environ 2,1 fois
  • CG-QTW: environ 2,4 fois
  • CG-TW: jusqu'à 67 fois

Comparaison des Performances de Convergence

Résultats typiques avec tolérance de convergence ε=10^-16:

MatriceTemps FP64(s)/ItérationsTemps QDW(s)/ItérationsTemps QTW(s)/Itérations
bone010170/21780120/12547150/11352
pdb1HYS5.4/128073.4/62854.9/5346

Découvertes Clés

  1. Nécessité de la normalisation:
    • Sans normalisation, les algorithmes quasi ne convergent pas
    • La normalisation après la mise à jour du vecteur résidu assure la convergence
  2. Avantages de QTW:
    • Réduction significative des frais de calcul par rapport à TW
    • Atteint une précision comparable à TW
    • Supporte la vectorisation SIMD, performance supérieure
  3. Bénéfices de la réduction du nombre d'itérations:
    • L'arithmétique haute précision réduit le nombre d'itérations
    • Le temps d'exécution total peut être inférieur à l'implémentation FP64

Analyse du Débit

Débit de l'opération SpMV (GB/s):

  • FP64 et QDW: proche de la limite de bande passante mémoire (environ 90 GB/s)
  • DW et QTW: atteignent la limite mémoire après optimisation SIMD
  • TW: performance significativement réduite en raison des branches

Travaux Connexes

Développement de l'Arithmétique Multi-Mots

  • Théorie fondamentale: Arithmétique double-mot de Dekker (1971)
  • Méthodes étendues: Arithmétique triple-mot (TW), quadruple-mot (QW)
  • Variantes simplifiées: Algorithmes quasi (QDW, QTW, QQW)

Bibliothèques d'Algèbre Linéaire Haute Précision

  • Bibliothèque QD: Implémentation Fortran/C++ d'arithmétique double-mot et quadruple-mot
  • XBLAS: Routines BLAS basées sur l'arithmétique DW
  • MPLAPACK: BLAS et LAPACK haute précision

Applications des Solveurs Itératifs Creux

  • Recherche sur les solveurs CG en quadruple précision
  • Méthodes en précision mixte
  • Multiplication matrice-vecteur creuse exacte selon le schéma d'Ozaki

Conclusions et Discussion

Conclusions Principales

  1. Faisabilité des algorithmes quasi: Grâce à une normalisation appropriée, les algorithmes quasi peuvent être appliqués efficacement dans les solveurs itératifs creux
  2. Avantages de QTW: L'arithmétique quasi triple-mot offre un bon équilibre entre précision et performance
  3. Potentiel d'amélioration des performances: Sur certains problèmes, la réduction du nombre d'itérations peut apporter des effets d'accélération supplémentaires

Limitations

  1. Frais de normalisation: Nécessité de compromis entre précision et temps d'exécution
  2. Dépendance au problème: Les effets d'amélioration des performances dépendent des caractéristiques du problème spécifique
  3. Portée d'évaluation: Évaluation limitée à la méthode CG de base, sans inclusion de techniques de préconditionnement

Directions Futures

  1. Optimisation des stratégies de normalisation: Étude de l'impact d'une normalisation plus fréquente sur la précision
  2. Extension à d'autres méthodes itératives: Évaluation de l'application dans d'autres solveurs
  3. Application en environnement distribué: Potentiel dans les environnements où la latence de communication est dominante
  4. Implémentation en formats basse précision: Implémentation d'arithmétique multi-mots utilisant FP16/FP32 sur processeurs IA

Évaluation Approfondie

Points Forts

  1. Étude systématique: Première évaluation systématique des performances des algorithmes quasi dans les solveurs itératifs
  2. Valeur pratique élevée: L'algorithme QTW offre une solution pratique de calcul haute précision
  3. Expériences complètes: Évaluation synthétique selon plusieurs dimensions (temps, précision, convergence)
  4. Innovation technique: Conception raisonnée de l'optimisation SIMD et des stratégies de normalisation

Insuffisances

  1. Analyse théorique insuffisante: Manque d'analyse théorique de l'accumulation d'erreurs dans les algorithmes quasi
  2. Portée d'évaluation limitée: Évaluation limitée à la méthode CG, manque de vérification avec d'autres méthodes itératives
  3. Stratégies de normalisation uniques: Seule une position et fréquence de normalisation ont été testées

Impact

  • Contribution académique: Offre de nouvelles options algorithmiques pour le domaine du calcul numérique haute précision
  • Valeur pratique: L'algorithme QTW peut être directement appliqué aux problèmes de calcul scientifique réels
  • Reproductibilité: Description détaillée des détails d'implémentation, facilitant la reproduction

Scénarios d'Application

  1. Calcul scientifique: Résolution de grands systèmes linéaires creux nécessitant une haute précision
  2. Simulation d'ingénierie: Applications telles que l'analyse structurelle et le calcul de champs électromagnétiques
  3. Environnements aux ressources limitées: Systèmes manquant de support matériel pour la quadruple précision

Références Bibliographiques

Cet article cite 29 références connexes, couvrant les domaines clés de la théorie de l'arithmétique multi-mots, des bibliothèques d'algèbre linéaire haute précision et des solveurs itératifs creux, fournissant une base théorique solide pour la recherche.