Architecture-aware sparse patterns to accelerate inverse preconditioning

Abstract

(English) This work focuses on improving the efficiency of iterative methods for solving large and sparse linear systems. These problems arise in many fields, including climate modeling, molecular and fluid dynamics, among others. To solve them, iterative methods such as the Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES) methods are widely employed. Their efficiency heavily depends on the choice of preconditioners, which accelerate convergence by improving the numerical properties of the system. Sparse Approximate Inverse (SAI) preconditioners, and their factorized variant (FSAI) for symmetric positive definite systems, are particularly appealing due to their parallel-friendly nature and straightforward application via Sparse Matrix-Vector (SpMV) operations. State-of-the-art SAI and FSAI approaches define their sparsity patterns primarily based on numerical considerations. This work introduces novel architecture-aware preconditioners designed to enhance performance by optimizing the sparse pattern selection process.

The first contribution presents the Factorized Sparse Approximate Inverse with Pattern Extension (FSAIE) preconditioner, an optimized version of FSAI tailored for shared memory CPU architectures. FSAIE introduces a cache-aware algorithm that extends sparsity patterns, improving both the numerical effectiveness of FSAI and its computational efficiency. Additionally, a filtering-out strategy is proposed to remove numerically insignificant entries, reducing computational cost without compromising convergence. These techniques enhance data locality in the SpMV kernel by ensuring that extended sparse patterns align with cache-line-sized memory access patterns.

The second contribution extends FSAIE to distributed memory CPU environments, introducing the Communication-aware Factorized Sparse Approximate Inverse with Pattern Extension (FSAIE-Comm) preconditioner. FSAIE-Comm incorporates communication-awareness to ensure that the sparse pattern extension does not introduce unnecessary inter-process communication overhead. To prevent load imbalance, an innovative strategy is developed to distribute computational workload more evenly.

The third contribution focuses on GPU execution by introducing the GPU-aware Factorized Sparse Approximate Inverse (GFSAI) preconditioner. By structuring the sparse pattern to enhance coalesced memory accesses and exploit GPU-specific architectural characteristics, GFSAI significantly accelerates FSAI computations on GPUs.

The final contribution generalizes the architecture-aware preconditioning strategies beyond FSAI by introducing the Communication-aware Sparse Approximate Inverse with Pattern Extension (SAIE-Comm) preconditioner. This approach optimizes SAI for distributed memory environments, similar to FSAIE-Comm, but is adapted for general linear systems where the GMRES solver is preferable over CG. SAIE-Comm highlights the versatility and flexibility of the proposed optimizations, demonstrating that architecture- and communication-aware pattern extensions can be effectively integrated into different preconditioning strategies and solver frameworks.

By integrating hardware-aware considerations into preconditioner design, this research advances the state of the art in iterative solvers and contributes to the development of scalable and high-performance numerical methods. The proposed methods achieve substantial improvements in time-to-solution across diverse High-Performance Computing (HPC) architectures, with reductions ranging from 12.94% to 26.43% on five different CPU architectures—Intel Skylake, Power9, Zen 2, A64FX, and Intel Sapphire Rapids—and from 23.83% to 26.07% on two GPU architectures—Volta and Vega20—when applied to representative sparse matrix benchmarks. These results underscore the impact of architecture-aware preconditioning strategies in modern HPC applications, paving the way for more efficient and scalable iterative solvers.

(Català) Aquest treball es centra en millorar l'eficiència dels mètodes iteratius per resoldre sistemes lineals grans i dispersos. Aquests problemes sorgeixen en molts camps, com ara la modelització del clima, la dinàmica molecular i de fluids, entre d'altres. Per resoldre'ls, s'utilitzen mètodes iteratius com el Gradient Conjugat (CG) i el Residu Mínim Generalitzat (GMRES). La seva eficiència depèn en gran mesura de l'elecció dels precondicionadors, que acceleren la convergència millorant les propietats numèriques del sistema. Els precondicionadors "Sparse Approximate Inverse" (SAI) i la seva variant factoritzada (FSAI) per a sistemes simètrics i definits positius són atractius per la seva naturalesa paral·lela i aplicació senzilla mitjançant productes Matriu-Vector dispersos (SpMV). Els SAI i FSAI d'última generació defineixen els seus patrons de dispersió basant-se principalment en aspectes numèrics. Aquest treball presenta nous precondicionadors considerant l'arquitectura on s'executen, dissenyats per millorar el rendiment optimitzant el procés de selecció de patrons de dispersió.

La primera contribució presenta el precondicionador "Factorized Sparse Approximate Inverse with Pattern Extension" (FSAIE), una versió optimitzada de FSAI adaptada a arquitectures de CPU de memòria compartida. FSAIE introdueix un algorisme que amplia els patrons de dispersió considerant els accessos a la memòria cau, millorant tant l'eficàcia numèrica de FSAI com la seva eficiència computacional. A més, es proposa una estratègia de filtratge per eliminar les entrades numèricament insignificants, reduint el cost computacional sense comprometre la convergència. Aquestes tècniques milloren la localitat de les dades a l'SpMV, assegurant que els patrons de dispersió ampliats s'alineen amb els patrons d'accés a la memòria cau.

La segona contribució amplia FSAIE als entorns de CPU de memòria distribuïda, introduint el precondicionador "Communication-aware FSAIE" (FSAIE-Comm). FSAIE-Comm considera els costs de la comunicació entre processos per garantir que l'extensió del patró de dispersió no introdueix una sobrecàrrega innecessària. Per evitar desequilibris, es desenvolupa una estratègia innovadora per distribuir la càrrega de treball computacional.

La tercera contribució es centra en l'execució a la GPU amb la introducció del precondicionador "GPU-aware Factorized Sparse Approximate Inverse" (GFSAI). Mitjançant l'estructuració del patró de dispersió, s'optimitzen els accessos de memòria coalescents i s'exploten les característiques arquitectòniques específiques de la GPU.

La contribució final generalitza les noves estratègies de precondicionament més enllà de FSAI amb la introducció del precondicionador "Communication-aware Sparse Approximate Inverse with Pattern Extension" (SAIE-Comm). Aquest mètode optimitza SAI per a entorns de memòria distribuïda, però s'adapta per a sistemes lineals generals on GMRES és preferible a CG. SAIE-Comm destaca la versatilitat i flexibilitat de les optimitzacions proposades, demostrant que les noves extensions de patrons es poden integrar eficaçment en diferents estratègies de precondicionament i solucionadors.

Aquest treball avança l'estat de l'art en solucionadors iteratius i contribueix al desenvolupament de mètodes numèrics escalables i d'alt rendiment. Els mètodes proposats aconsegueixen millores substancials en el temps de solució a diverses arquitectures de computació d'alt rendiment (HPC), amb reduccions del 12,94% al 26,43% en cinc arquitectures de CPU diferents—Intel Skylake, Power9, Zen 2, A64FX i Intel Sapphire Rapids—i del 23,83% al 26,07% en dues arquitectures de GPU—Volta i Vega20—quan s'apliquen casos representatius de matriu dispersa. Aquests resultats destaquen l'impacte de les estratègies de precondicionament que consideren l'arquitectura en les aplicacions HPC modernes, obrint el camí per a solucionadors iteratius més eficients i escalables.

(Español) Este trabajo se centra en mejorar la eficiencia de los métodos iterativos para resolver sistemas lineales grandes y dispersos. Estos problemas surgen en muchos campos, como la modelización del clima, la dinámica molecular y de fluidos, entre otros. Para resolverlos, se utilizan métodos iterativos como el Gradiente Conjugado (CG) y el Residuo Mínimo Generalizado (GMRES). Su eficiencia depende en gran medida de la elección de los precondicionadores, que aceleran la convergencia mejorando las propiedades numéricas del sistema. Los precondicionadores "Sparse Approximate Inverse" (SAI) y su variante factorizada (FSAI) para sistemas simétricos y definidos positivos son atractivos por su naturaleza paralela y aplicación sencilla mediante productos Matriz-Vector dispersos (SpMV). Los SAI y FSAI de última generación definen sus patrones de dispersión basándose principalmente en aspectos numéricos. Este trabajo presenta nuevos precondicionadores considerando la arquitectura en la que se ejecutan, diseñados para mejorar el rendimiento optimizando la selección de patrones.

La primera contribución presenta el precondicionador "Factorized Sparse Approximate Inverse with Pattern Extension" (FSAIE), una versión optimizada de FSAI adaptada a arquitecturas de CPU de memoria compartida. FSAIE introduce un algoritmo que amplía los patrones de dispersión considerando los accesos a la caché, mejorando tanto la eficacia numérica de FSAI como su eficiencia computacional. Además, se propone una estrategia de filtrado para eliminar entradas numéricamente insignificantes, reduciendo el coste computacional sin comprometer la convergencia. Estas técnicas mejoran la localidad de los datos en SpMV, asegurando que los patrones de dispersión ampliados se alinean con los accesos a la caché.

La segunda contribución amplía FSAIE a entornos de CPU de memoria distribuida, introduciendo el precondicionador "Communication-aware FSAIE" (FSAIE-Comm). FSAIE-Comm considera los costes de comunicación entre procesos para garantizar que la extensión del patrón de dispersión no introduce una sobrecarga innecesaria. Para evitar desequilibrios, se desarrolla una innovadora estrategia para distribuir la carga computacional.

La tercera contribución se centra en la ejecución en GPU con la introducción del precondicionador "GPU-aware Factorized Sparse Approximate Inverse" (GFSAI). Mediante la estructuración del patrón de dispersión, se optimizan los accesos de memoria coalescentes y se explotan las características arquitectónicas de la GPU.

La contribución final generaliza las nuevas estrategias de precondicionamiento más allá de FSAI con la introducción del precondicionador "Communication-aware Sparse Approximate Inverse with Pattern Extension" (SAIE-Comm). Este método optimiza SAI para entornos de memoria distribuida, pero se adapta a sistemas lineales generales en los que GMRES es preferible a CG. SAIE-Comm destaca la versatilidad de las optimizaciones propuestas, demostrando que las nuevas extensiones de patrones pueden integrarse eficazmente en distintas estrategias de precondicionamiento y solucionadores.

Este trabajo avanza el estado del arte en solucionadores iterativos y contribuye al desarrollo de métodos numéricos escalables y de alto rendimiento. Los métodos propuestos consiguen mejoras sustanciales en el tiempo de solución en diversas arquitecturas de computación de alto rendimiento (HPC), con reducciones del 12,94% al 26,43% en cinco arquitecturas de CPU—Intel Skylake, Power9, Zen 2, A64FX e Intel Sapphire Rapids—y del 23,83% al 26,07% en dos arquitecturas de GPU—Volta y Vega20—cuando se aplican casos representativos de matriz dispersa. Estos resultados destacan el impacto de las estrategias de precondicionamiento que consideran la arquitectura en las aplicaciones HPC modernas, abriendo el camino para solucionadores iterativos más eficientes y escalables.