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

Dünnbesetzte iterative Löser unter Verwendung von Hochpräzisions-Arithmetik mit Quasi-Mehrwort-Algorithmen

Grundlegende Informationen

Papier-ID: 2510.13536
Titel: Sparse Iterative Solvers Using High-Precision Arithmetic with Quasi Multi-Word Algorithms
Autoren: Daichi Mukunoki (Nagoya University), Katsuhisa Ozaki (Shibaura Institute of Technology)
Klassifizierung: cs.MS (Mathematische Software)
Veröffentlichungsdatum: 15. Oktober 2025 (arXiv-Preprint)
Papierlink: https://arxiv.org/abs/2510.13536

Zusammenfassung

Um genaue Ergebnisse in numerischen Berechnungen zu erhalten, ist Hochpräzisions-Arithmetik ein direkter Ansatz. Die meisten Prozessoren verfügen jedoch über keine Hardwareunterstützung für Gleitkommaformate außerhalb der doppelten Genauigkeit (FP64). Die Doppelwort-Arithmetik (Dekker 1971) erweitert die Präzision durch die Verwendung von Standard-Gleitkommaoperationen zur Darstellung von Zahlen mit doppelter Mantissenlänge. Basierend auf diesem Konzept wurden verschiedene Mehrwort-Arithmetik-Methoden vorgeschlagen, die die Präzision durch die Kombination zusätzlicher Wörter weiter erhöhen. Vereinfachte Varianten, sogenannte Quasi-Algorithmen, wurden ebenfalls eingeführt, die einen gewissen Präzisionsverlust gegen reduzierte Rechenkosten eintauschen. Diese Studie untersucht die Leistung von Quasi-Algorithmen für Doppel- und Dreiwort-Arithmetik in dünnbesetzten iterativen Lösern basierend auf der Konjugierte-Gradienten-Methode und vergleicht diese mit Nicht-Quasi-Algorithmen und Standard-FP64.

Forschungshintergrund und Motivation

Kernprobleme

Hardware-Einschränkungsproblem: Die meisten Prozessoren verfügen über keine Hardwareunterstützung für Gleitkommaformate außerhalb von doppelter Genauigkeit (FP64), was die Implementierung von Hochpräzisions-Numerikberechnungen einschränkt
Präzisionsanforderungen dünnbesetzter iterativer Löser: Bei der Lösung großer dünnbesetzter linearer Systeme erhöhen Rundungsfehler die Anzahl der für die Konvergenz erforderlichen Iterationen und beeinflussen die Lösungspräzision und Effizienz
Abwägung zwischen Leistung und Präzision: Obwohl traditionelle Mehrwort-Arithmetik-Methoden die Präzision verbessern können, sind die Rechenkosten erheblich

Forschungsbedeutung

Dünnbesetzte iterative Löser werden häufig in wissenschaftlichen Berechnungen und technischen Anwendungen eingesetzt
Hochpräzisions-Arithmetik kann die Konvergenz verbessern und die Anzahl der Iterationen reduzieren
In speicherbegrenzten Anwendungen können die zusätzlichen Kosten der Mehrwort-Arithmetik durch Speicherlatenzen verdeckt werden

Einschränkungen bestehender Methoden

Traditionelle Mehrwort-Arithmetik (wie DW, TW) hat hohe Rechenkosten
Quasi-Algorithmen reduzieren zwar die Rechenkosten, können aber zu Präzisionsverlusten führen
Es fehlt eine systematische Bewertung der Leistung von Quasi-Algorithmen in iterativen Lösern

Kernbeiträge

Systematische Bewertung der Quasi-Algorithmen-Leistung: Erste systematische Bewertung der Leistung von QDW- und QTW-Algorithmen in dünnbesetzten iterativen Lösern
Entdeckung der kritischen Rolle der Normalisierung: Nachweis der Wichtigkeit angemessener Normalisierung für die Konvergenz von Quasi-Algorithmen
Vorschlag von QTW als effektive Alternative: Nachweis, dass Quasi-Dreiwort-Arithmetik (QTW) eine effektive Alternative zur traditionellen Doppelwort-Arithmetik darstellt
Umfassende Leistungsanalyse: Ganzheitliche Bewertung aus drei Dimensionen: Ausführungszeit, Iterationszahl und Lösungspräzision

Methodische Details

Aufgabendefinition

Lösung symmetrisch positiv definiter linearer Systeme Ax = b, wobei:

A eine n×n symmetrisch positiv definite dünnbesetzte Matrix ist
b der Rechtsvektor ist
x der zu lösende Vektor ist

Die Konjugierte-Gradienten-Methode (CG) wird für die iterative Lösung verwendet, um die Leistung verschiedener Präzisions-Arithmetiken zu bewerten.

Mehrwort-Arithmetik-Architektur

Grundlegende Algorithmen

Fehlerfreie Transformationsalgorithmen:

TwoSum(a,b): Zerlegt a+b in Gleitkommaergebnis x und Rundungsfehler y
QuickTwoSum(a,b): Effiziente Variante von TwoSum, erfordert |a|≥|b|
TwoProdFMA(a,b): Zerlegt a×b unter Verwendung von FMA-Operationen in Ergebnis und Fehler

Doppelwort-Arithmetik (DW)

DWadd: [c1,c2] = DWadd(a1,a2,b1,b2)
- Operanden: 11 FP64-Operationen
- Enthält Normalisierungsschritt (QuickTwoSum)

DWmul: [c1,c2] = DWmul(a1,a2,b1,b2)  
- Operanden: 7 FP64-Operationen
- Enthält Normalisierungsschritt

Quasi-Doppelwort-Arithmetik (QDW)

Normalisierungsschritt wird weggelassen, ermöglicht Überlappung von hohem und niedrigem Wort
QDWadd: 8 Operationen, QDWmul: 4 Operationen
Rechenkosten deutlich reduziert

Quasi-Dreiwort-Arithmetik (QTW)

QTWadd: [c1,c2,c3] = QTWadd(a1,a2,a3,b1,b2,b3)
- Operanden: 21 FP64-Operationen
- Erzwingt nicht fl(c1+c2)=c1 und fl(c2+c3)=c2

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

Technische Innovationen

SIMD-Vektorisierungsoptimierung:
- Verwendung von AVX2- und AVX-512-Befehlssätzen für Vektorisierung
- QTW-Algorithmus eliminiert bedingte Verzweigungen, besser geeignet für Vektorisierung
Normalisierungsstrategie:
- Normalisierung nach der Aktualisierung des Residuumsvektors in der CG-Methode
- Verwendung des VecSum3-Algorithmus zur Minderung von Bitüberlappung in Dreiwort-Arithmetik
Implementierung mit gemischter Präzision:
- Koeffizientenmatrix A und Rechtsvektor b werden in FP64 gespeichert
- Interne Berechnungen verwenden entsprechende Mehrwort-Arithmetik

Experimentelle Einrichtung

Datensätze

Verwendung von 8 symmetrisch positiv definiten Matrizen aus der SuiteSparse-Matrixsammlung:

Matrix	Dimension n	Nicht-Null-Elemente nnz	Anwendungsbereich
Hook_1498	1.498.023	60.917.445	Strukturprobleme
bone010	986.703	47.851.783	Modellreduktion
nd24k	72.000	28.715.634	2D/3D-Probleme
crankseg_2	63.838	14.148.858	Strukturprobleme

Bewertungsmetriken

Ausführungszeit: Zeit pro Iteration und Gesamtkonvergenzzeit
Iterationszahl: Anzahl der für Konvergenz erforderlichen Iterationen
Lösungspräzision: Relative Fehlernorm ||xk-x*||2/||x*||2

Vergleichsmethoden

CG-FP64: Standard-Doppelpräzisions-Implementierung
CG-DW: Doppelwort-Arithmetik-Implementierung
CG-QDW: Quasi-Doppelwort-Arithmetik-Implementierung
CG-TW: Dreiwort-Arithmetik-Implementierung
CG-QTW: Quasi-Dreiwort-Arithmetik-Implementierung

Implementierungsdetails

Hardware-Plattform: Intel Xeon Gold 6230 CPU (20 Kerne, 2,10-3,90 GHz)
Compiler: g++ 11.3.0, Optimierungsoptionen -O3 -march=native
Parallelisierung: OpenMP + SIMD-Vektorisierung
Konvergenztoleranz: ε = 10^-16, 10^-24, 10^-32

Experimentelle Ergebnisse

Hauptergebnisse

Analyse des Leistungsaufwands

Ausführungszeit-Overhead relativ zu FP64 (100 Iterationen):

CG-QDW: etwa 1,3-fach
CG-DW: etwa 2,1-fach
CG-QTW: etwa 2,4-fach
CG-TW: bis zu 67-fach

Vergleich der Konvergenzleistung

Typische Ergebnisse bei Konvergenztoleranz ε=10^-16:

Matrix	FP64-Zeit(s)/Iterationen	QDW-Zeit(s)/Iterationen	QTW-Zeit(s)/Iterationen
bone010	170/21780	120/12547	150/11352
pdb1HYS	5,4/12807	3,4/6285	4,9/5346

Wichtigste Erkenntnisse

Notwendigkeit der Normalisierung:
- Ohne Normalisierung können Quasi-Algorithmen nicht konvergieren
- Normalisierung nach der Residuumsvektoraktualisierung gewährleistet Konvergenz
Vorteile von QTW:
- Deutlich reduzierter Rechenaufwand im Vergleich zu TW
- Erreicht vergleichbare Präzision wie TW
- Unterstützt SIMD-Vektorisierung mit besserer Leistung
Nutzen der Reduktion der Iterationszahl:
- Hochpräzisions-Arithmetik kann die Iterationszahl reduzieren
- Die Gesamtausführungszeit kann unter FP64-Implementierung liegen

Durchsatzanalyse

Durchsatz von SpMV-Operationen (GB/s):

FP64 und QDW: Nah an der Speicherbandbreitenbegrenzung (etwa 90 GB/s)
DW und QTW: Nach SIMD-Optimierung speicherbegrenzt
TW: Aufgrund von Verzweigungseffekten deutlich reduzierte Leistung

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

Machbarkeit von Quasi-Algorithmen: Durch angemessene Normalisierung können Quasi-Algorithmen effektiv in dünnbesetzten iterativen Lösern angewendet werden
Vorteile von QTW: Quasi-Dreiwort-Arithmetik bietet ein gutes Gleichgewicht zwischen Präzision und Leistung
Leistungssteigerungspotenzial: Bei einigen Problemen kann die Reduktion der Iterationszahl zu zusätzlichen Beschleunigungseffekten führen

Einschränkungen

Normalisierungsaufwand: Erforderliche Abwägung zwischen Präzision und Ausführungszeit
Problemabhängigkeit: Leistungssteigerungseffekte hängen von spezifischen Problemmerkmalen ab
Bewertungsumfang: Nur grundlegende CG-Methode bewertet, keine Vorkonditionierungstechniken enthalten

Zukünftige Richtungen

Optimierung der Normalisierungsstrategie: Untersuchung der Auswirkungen häufigerer Normalisierung auf die Präzision
Erweiterung auf andere iterative Methoden: Bewertung der Anwendung in anderen Lösern
Anwendung in verteilten Umgebungen: Potenzial in Umgebungen mit dominanter Kommunikationslatenzen
Implementierung mit niedriger Präzision: Verwendung von FP16/FP32 zur Implementierung von Mehrwort-Arithmetik auf KI-Prozessoren

Tiefgreifende Bewertung

Stärken

Systematische Forschung: Erste systematische Bewertung der Quasi-Algorithmen-Leistung in iterativen Lösern
Hoher praktischer Wert: QTW-Algorithmus bietet praktische Hochpräzisions-Rechenlösung
Umfassende Experimente: Ganzheitliche Bewertung aus mehreren Dimensionen (Zeit, Präzision, Konvergenz)
Technische Innovation: Angemessenes Design von SIMD-Optimierung und Normalisierungsstrategie

Mängel

Unzureichende theoretische Analyse: Fehlende theoretische Analyse der Fehlerakkumulation in Quasi-Algorithmen
Begrenzte Bewertungsreichweite: Nur CG-Methode bewertet, fehlende Validierung anderer iterativer Methoden
Einzelne Normalisierungsstrategie: Nur eine Normalisierungsposition und -häufigkeit getestet

Einfluss

Akademischer Beitrag: Bietet neue Algorithmusoptionen für das Hochpräzisions-Numerikrechnen
Praktischer Wert: QTW-Algorithmus kann direkt auf praktische wissenschaftliche Rechenproblem angewendet werden
Reproduzierbarkeit: Ausreichend detaillierte Implementierungsbeschreibung ermöglicht Reproduktion

Anwendungsszenarien

Wissenschaftliche Berechnungen: Hochpräzisions-Lösung großer dünnbesetzter linearer Systeme erforderlich
Technische Simulation: Strukturanalyse, elektromagnetische Feldberechnungen und andere Anwendungen
Ressourcenbegrenzte Umgebungen: Systeme ohne Hardwareunterstützung für vierfache Präzision

Literaturverzeichnis

Dieses Papier zitiert 29 relevante Literaturquellen, die Mehrwort-Arithmetik-Theorie, Hochpräzisions-Linearen-Algebra-Bibliotheken, dünnbesetzte iterative Löser und andere Schlüsselbereiche abdecken und eine solide theoretische Grundlage für die Forschung bieten.