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

Solucionadores Iterativos Dispersos Utilizando Aritmética de Alta Precisión con Algoritmos Cuasi Multi-Palabra

Información Básica

  • ID del Artículo: 2510.13536
  • Título: Sparse Iterative Solvers Using High-Precision Arithmetic with Quasi Multi-Word Algorithms
  • Autores: Daichi Mukunoki (Universidad de Nagoya), Katsuhisa Ozaki (Instituto Tecnológico Shibaura)
  • Clasificación: cs.MS (Software Matemático)
  • Fecha de Publicación: 15 de octubre de 2025 (preimpresión arXiv)
  • Enlace del Artículo: https://arxiv.org/abs/2510.13536

Resumen

Para obtener resultados precisos en cálculos numéricos, la aritmética de alta precisión es un método directo. Sin embargo, la mayoría de los procesadores carecen de soporte de hardware para formatos de punto flotante más allá de la precisión doble (FP64). La aritmética de doble palabra (Dekker 1971) extiende la precisión utilizando operaciones de punto flotante estándar para representar números con el doble de longitud de mantisa. Basándose en este concepto, se han propuesto varios métodos de aritmética multi-palabra que aumentan aún más la precisión combinando palabras adicionales. También se han introducido variantes simplificadas, es decir, algoritmos cuasi, que intercambian cierta pérdida de precisión por una reducción en el costo computacional. Este estudio investiga el rendimiento de los algoritmos cuasi para aritmética de doble y triple palabra en solucionadores iterativos dispersos basados en el método de gradiente conjugado, comparándolos con variantes no cuasi y FP64 estándar.

Antecedentes de Investigación y Motivación

Problemas Fundamentales

  1. Limitaciones de Hardware: La mayoría de los procesadores carecen de soporte de hardware para formatos de punto flotante más allá de FP64, lo que limita la implementación de cálculos numéricos de alta precisión
  2. Requisitos de Precisión en Solucionadores Iterativos Dispersos: Al resolver sistemas lineales dispersos grandes, los errores de redondeo aumentan el número de iteraciones necesarias para la convergencia, afectando la precisión y eficiencia de la solución
  3. Equilibrio entre Rendimiento y Precisión: Aunque los métodos tradicionales de aritmética multi-palabra pueden mejorar la precisión, conllevan un costo computacional considerable

Importancia de la Investigación

  • Los solucionadores iterativos dispersos se aplican ampliamente en cálculos científicos y aplicaciones de ingeniería
  • La aritmética de alta precisión puede mejorar la convergencia y reducir el número de iteraciones
  • En aplicaciones con memoria limitada, el costo adicional de la aritmética multi-palabra puede ser enmascarado por la latencia de memoria

Limitaciones de Métodos Existentes

  • La aritmética multi-palabra tradicional (como DW, TW) tiene alto costo computacional
  • Aunque los algoritmos cuasi reducen el costo computacional, pueden causar pérdida de precisión
  • Falta una evaluación sistemática del rendimiento de algoritmos cuasi en solucionadores iterativos

Contribuciones Principales

  1. Evaluación Sistemática del Rendimiento de Algoritmos Cuasi: Primera evaluación sistemática del rendimiento de algoritmos QDW y QTW en solucionadores iterativos dispersos
  2. Descubrimiento del Papel Crítico de la Normalización: Demostración de la importancia de la normalización apropiada para la convergencia de algoritmos cuasi
  3. Propuesta de QTW como Alternativa Efectiva: Demostración de que la aritmética cuasi triple-palabra (QTW) puede servir como alternativa efectiva a la aritmética de doble palabra tradicional
  4. Análisis Integral de Rendimiento: Evaluación comprehensiva desde tres dimensiones: tiempo de ejecución, número de iteraciones y precisión de solución

Detalles de la Metodología

Definición de la Tarea

Resolver el sistema lineal simétrico definido positivo Ax = b, donde:

  • A es una matriz dispersa simétrica definida positiva de n×n
  • b es el vector del lado derecho
  • x es el vector a resolver

Se utiliza el método de gradiente conjugado (CG) para la solución iterativa, evaluando el rendimiento de diferentes aritmética de precisión.

Arquitectura de Aritmética Multi-Palabra

Algoritmos Fundamentales

Algoritmos de Transformación Libre de Errores:

  • TwoSum(a,b): Descompone a+b en resultado de punto flotante x y error de redondeo y
  • QuickTwoSum(a,b): Variante eficiente de TwoSum, requiere |a|≥|b|
  • TwoProdFMA(a,b): Descompone a×b en resultado y error utilizando operación FMA

Aritmética de Doble Palabra (DW)

DWadd: [c1,c2] = DWadd(a1,a2,b1,b2)
- Operandos: 11 operaciones FP64
- Incluye paso de normalización (QuickTwoSum)

DWmul: [c1,c2] = DWmul(a1,a2,b1,b2)  
- Operandos: 7 operaciones FP64
- Incluye paso de normalización

Aritmética Cuasi Doble-Palabra (QDW)

  • Omite paso de normalización, permitiendo superposición de palabras altas y bajas
  • QDWadd: 8 operaciones, QDWmul: 4 operaciones
  • Reducción significativa del costo computacional

Aritmética Cuasi Triple-Palabra (QTW)

QTWadd: [c1,c2,c3] = QTWadd(a1,a2,a3,b1,b2,b3)
- Operandos: 21 operaciones FP64
- No impone fl(c1+c2)=c1 ni fl(c2+c3)=c2

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

Puntos de Innovación Técnica

  1. Optimización de Vectorización SIMD:
    • Utiliza conjuntos de instrucciones AVX2 y AVX-512 para vectorización
    • El algoritmo QTW elimina ramificaciones condicionales, más adecuado para vectorización
  2. Estrategia de Normalización:
    • Normalización después de la actualización del vector residual en el método CG
    • Utiliza algoritmo VecSum3 para mitigar superposición de bits en aritmética triple-palabra
  3. Implementación de Precisión Mixta:
    • Matriz de coeficientes A y vector derecho b almacenados en FP64
    • Cálculos internos utilizan aritmética multi-palabra correspondiente

Configuración Experimental

Conjunto de Datos

Se utilizan 8 matrices simétricas definidas positivas de la colección de matrices SuiteSparse:

MatrizDimensión nElementos no nulos nnzDominio de Aplicación
Hook_14981,498,02360,917,445Problemas estructurales
bone010986,70347,851,783Reducción de modelos
nd24k72,00028,715,634Problemas 2D/3D
crankseg_263,83814,148,858Problemas estructurales

Métricas de Evaluación

  1. Tiempo de Ejecución: Tiempo por iteración y tiempo total de convergencia
  2. Número de Iteraciones: Número de iteraciones requeridas para alcanzar convergencia
  3. Precisión de Solución: Norma de error relativo ||xk-x*||2/||x*||2

Métodos de Comparación

  • CG-FP64: Implementación estándar de precisión doble
  • CG-DW: Implementación de aritmética de doble palabra
  • CG-QDW: Implementación de aritmética cuasi doble-palabra
  • CG-TW: Implementación de aritmética triple-palabra
  • CG-QTW: Implementación de aritmética cuasi triple-palabra

Detalles de Implementación

  • Plataforma de Hardware: CPU Intel Xeon Gold 6230 (20 núcleos, 2.10-3.90 GHz)
  • Compilador: g++ 11.3.0, opciones de optimización -O3 -march=native
  • Paralelización: OpenMP + vectorización SIMD
  • Tolerancia de Convergencia: ε = 10^-16, 10^-24, 10^-32

Resultados Experimentales

Resultados Principales

Análisis de Sobrecarga de Rendimiento

Sobrecarga de tiempo de ejecución relativa a FP64 (100 iteraciones):

  • CG-QDW: aproximadamente 1.3 veces
  • CG-DW: aproximadamente 2.1 veces
  • CG-QTW: aproximadamente 2.4 veces
  • CG-TW: hasta 67 veces

Comparación de Rendimiento de Convergencia

Resultados típicos bajo tolerancia de convergencia ε=10^-16:

MatrizTiempo FP64(s)/IteracionesTiempo QDW(s)/IteracionesTiempo QTW(s)/Iteraciones
bone010170/21780120/12547150/11352
pdb1HYS5.4/128073.4/62854.9/5346

Hallazgos Clave

  1. Necesidad de Normalización:
    • Sin normalización, los algoritmos cuasi no convergen
    • La normalización después de la actualización del vector residual asegura convergencia
  2. Ventajas de QTW:
    • Reducción significativa de costo computacional en comparación con TW
    • Alcanza precisión comparable a TW
    • Soporta vectorización SIMD con mejor rendimiento
  3. Beneficios de la Reducción de Iteraciones:
    • La aritmética de alta precisión reduce el número de iteraciones
    • El tiempo total de ejecución puede ser inferior a la implementación FP64

Análisis de Rendimiento

Rendimiento de operación SpMV (GB/s):

  • FP64 y QDW: cercano al límite de ancho de banda de memoria (aproximadamente 90 GB/s)
  • DW y QTW: alcanzan límite de memoria después de optimización SIMD
  • TW: rendimiento significativamente reducido debido al impacto de ramificaciones

Trabajo Relacionado

Desarrollo de Aritmética Multi-Palabra

  • Teoría Fundamental: Aritmética de doble palabra de Dekker (1971)
  • Métodos Extendidos: Aritmética triple-palabra (TW), cuádruple-palabra (QW)
  • Variantes Simplificadas: Algoritmos cuasi (QDW, QTW, QQW)

Bibliotecas de Álgebra Lineal de Alta Precisión

  • Biblioteca QD: Implementación Fortran/C++ de aritmética de doble y cuádruple palabra
  • XBLAS: Rutinas BLAS basadas en aritmética DW
  • MPLAPACK: BLAS y LAPACK de alta precisión

Aplicaciones de Solucionadores Iterativos Dispersos

  • Investigación de solucionadores CG de cuádruple precisión
  • Métodos de precisión mixta
  • Multiplicación exacta de matriz-vector dispersa del esquema Ozaki

Conclusiones y Discusión

Conclusiones Principales

  1. Viabilidad de Algoritmos Cuasi: Con normalización apropiada, los algoritmos cuasi pueden aplicarse efectivamente en solucionadores iterativos dispersos
  2. Ventajas de QTW: La aritmética cuasi triple-palabra proporciona un buen equilibrio entre precisión y rendimiento
  3. Potencial de Mejora de Rendimiento: En ciertos problemas, la reducción de iteraciones puede proporcionar efectos de aceleración adicionales

Limitaciones

  1. Costo de Normalización: Necesidad de equilibrio entre precisión y tiempo de ejecución
  2. Dependencia del Problema: Los efectos de mejora de rendimiento dependen de características específicas del problema
  3. Alcance de Evaluación: Solo se evaluó el método CG básico, sin incluir técnicas de precondicionamiento

Direcciones Futuras

  1. Optimización de Estrategia de Normalización: Investigación del impacto de normalización más frecuente en precisión
  2. Extensión a Otros Métodos Iterativos: Evaluación de aplicación en otros solucionadores
  3. Aplicación en Entornos Distribuidos: Potencial en entornos donde la latencia de comunicación es dominante
  4. Implementación de Formatos de Baja Precisión: Implementación de aritmética multi-palabra utilizando FP16/FP32 en procesadores de IA

Evaluación Profunda

Fortalezas

  1. Investigación Sistemática: Primera evaluación sistemática del rendimiento de algoritmos cuasi en solucionadores iterativos
  2. Alto Valor Práctico: El algoritmo QTW proporciona un esquema práctico de cálculo de alta precisión
  3. Experimentación Exhaustiva: Evaluación comprehensiva desde múltiples dimensiones (tiempo, precisión, convergencia)
  4. Innovación Técnica: Diseño razonable de optimización SIMD y estrategia de normalización

Insuficiencias

  1. Análisis Teórico Limitado: Falta análisis teórico de acumulación de errores en algoritmos cuasi
  2. Alcance de Evaluación Limitado: Solo se evaluó el método CG, falta verificación en otros métodos iterativos
  3. Estrategia de Normalización Única: Solo se intentó una ubicación y frecuencia de normalización

Impacto

  • Contribución Académica: Proporciona nuevas opciones de algoritmos para el campo de cálculos numéricos de alta precisión
  • Valor Práctico: El algoritmo QTW puede aplicarse directamente a problemas de cálculo científico real
  • Reproducibilidad: Descripción detallada de detalles de implementación, facilitando la reproducción

Escenarios de Aplicación

  1. Cálculo Científico: Solución de sistemas lineales dispersos grandes que requieren alta precisión
  2. Simulación de Ingeniería: Análisis estructural, cálculos de campos electromagnéticos y otras aplicaciones
  3. Entornos con Recursos Limitados: Sistemas que carecen de soporte de hardware para precisión cuádruple

Referencias Bibliográficas

Este artículo cita 29 referencias relacionadas, que abarcan teoría de aritmética multi-palabra, bibliotecas de álgebra lineal de alta precisión, solucionadores iterativos dispersos y otros campos clave, proporcionando una base teórica sólida para la investigación.