Half-day tutorial at ISC High Performance 2025 (ISC25), June 10-13, 2025, Hamburg, Germany:
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 CPU and GPU nodes. Performance Engineering is often taught using simple loops as instructive examples for performance models and how they can guide optimization; however, full, preconditioned linear solvers comprise multiple back-to-back loops enclosed in an iteration scheme that is executed until convergence is achieved. Consequently, the concept of “optimal performance” has to account for both hardware resource efficiency and iterative solver convergence. We convey a performance engineering process that is geared towards linear iterative solvers. After introducing basic notions of hardware organization and storage for dense and sparse data structures, we show how the Roofline performance model can be applied 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 pure memory boundedness. Then we advance to the structure of preconditioned solvers, using the Conjugate Gradient Method (CG) algorithm as a leading example. Hotspots and bottlenecks of the complete solver are identified followed by the introduction of advanced algorithmic and implementation-centric optimization techniques like the use of preconditioners and cache blocking. The interplay among solver performance, convergence, and actual 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.
Feedback link
Please do not forget to fill out the feedback form for the tutorial and give us your honest opinion. The link can be found on the Swapcard page for the tutorial (left panel, below “Prerequisites”).
Demo code
The code shown during the demos is available at: https://go-nhr.de/PELS-Code