Half-day tutorial at SC 25, November 16, 2025, St. Louis, MO:
Performance Engineering for Sparse Linear Solvers
Authors/Presenters
Christie Alappat1, Hartwig Anzt2, Georg Hager1, and Jonas Thies3
1 Erlangen National High Performance Computing Center (NHR@FAU), FAU Erlangen-Nürnberg, Germany
2 TUM School of Computation, Information and Technology, TU München Campus Heilbronn, Germany
3 Delft Institute of Applied Mathematics, TU Delft, The Netherlands
Abstract
This tutorial covers code analysis, performance modeling, and optimization for sparse linear solvers on CPUs and GPUs. Performance engineering is often taught using simple loops as examples for performance models and how they can guide optimization; however, full, preconditioned linear solvers comprise multiple loops and an iteration scheme that is executed to convergence. Consequently, the concept of “optimal performance” must account for both hardware efficiency and solver convergence. After introducing basic notions of hardware organization and storage for dense and sparse data structures, we show how to apply the Roofline model to such solvers in predictive and diagnostic ways and how it can be used to assess the hardware efficiency of a solver, covering important corner cases such as memory boundedness. Then we advance to preconditioned solvers, using the conjugate gradient method (CG) algorithm as a leading example. Bottlenecks of the solver are identified, followed by the introduction of optimization techniques like the use of preconditioners and cache blocking. The interplay among solver performance, convergence, and time to solution is given special attention. In hands-on exercises, attendees will be able to carry out experiments on a GPU cluster and study the influence of matrix data formats, preconditioners, and cache optimizations.
Hands-on code
The code used during the hands-on exercises is available at: https://github.com/RRZE-HPC/PELS