Recursive Algebraic Coloring Engine: Performance optimization and engineering of sparse linear algebra kernels using RACE

Sparse linear algebra plays a pivotal role in numerous large-scale numerical simulations, which constitute a significant portion of the computations carried out on high-performance computing (HPC) systems. However, the hardware architectures used in HPC systems have not been designed with the performance requirements of sparse solvers in mind. Consequently, extensive research on efficient sparse kernels and data structures has been conducted over the past decades to leverage the capabilities of HPC systems for sparse linear algebra. The irregular nature of sparse kernels, their intricate dependencies, and the challenge of dealing with sparsity patterns that are only known at runtime still present substantial hurdles in efficiently running many of the kernels commonly used in sparse linear algebra applications on modern multi-core CPUs. Increasing degrees of parallelism and the complexities of cache hierarchies further drive the demand for new ideas in the field of sparse kernels. In this thesis, we introduce a new approach to address these challenges on modern multi-core CPUs: the Recursive Algebraic Coloring Engine (RACE) software framework. RACE operates on the graph of the underlying sparse matrix rather than using a standard matrix-oriented approach. Levels constructed through breadth-first search (BFS) reordering effectively capture the dependency relations between different nodes (rows) within the graph (matrix), providing a means to address the complex dependencies found in challenging sparse kernels. We introduce two schemes based on these levels: coloring and cache blocking, designed to efficiently execute different sets of sparse kernels. The level-based coloring scheme resolves inherent dependencies in certain sparse kernels, such as the distance-1 dependency in the Gauss-Seidel (GS) solver and the distance-2 dependency in the Kaczmarz (KACZ) solver. We further interpret the challenging problem of shared memory parallelization of symmetric sparse matrix-vector multiplication (SymmSpMV) as a distance-2 coloring problem. Data dependencies pose a challenge for straightforward parallelization. The level-based coloring scheme allows us to resolve these underlying data dependencies, enabling efficient thread-level parallelization. The RACE framework incorporates optimizations like level grouping, load balancing, recursive strategies, and automatic adaption to hardware. Benchmarking with 37 sparse matrices demonstrates that RACE outperforms other multicoloring methods and Intel MKL by an average factor of 1.4x on modern Intel and AMD architectures for distance-2 dependency kernels. For GS with distance-1 dependency, RACE performs on par with the best-performing multicoloring methods. Convergence studies on GS and KACZ iterative kernels also show that the convergence of RACE matches or surpasses other multicoloring methods. The second scheme, known as level-based cache blocking, leverages the levels within RACE to optimize kernels that repeatedly invoke the same sparse matrix operation consecutively. One notable example is the matrix power kernel (MPK), which invokes multiple consecutive sparse matrix-vector multiplications (SpMV) to calculate the product of the k-th power of a sparse matrix A and a dense vector x, i.e., Aᵏx. Current MPK implementations typically execute repeated back-to-back SpMV operations, ignoring the potential of cache blocking. By exploiting RACE’s level-based view, we can perform cache blocking on the matrix A across SpMVs, significantly accelerating MPK computations. The locality relations of the levels allow us to control dependencies between different SpMV invocations and execute in a hardware-aware manner that maximizes the spatial and temporal reuse of matrix and vector entries. Similar to the level-based coloring scheme, numerous optimizations have been incorporated into the RACE framework to efficiently cache block and execute the kernels in a thread-level parallel fashion. Our approach demonstrates remarkable effectiveness, achieving performance levels of 50-100 Gflop/s on a single modern Intel or AMD multicore chip, providing an average speedup of typically 1.8x–3x when compared to highly optimized classical SpMV-based implementations. The development of the RACE framework followed a systematic performance engineering process, enabling the identification of bottlenecks and the implementation of relevant optimization strategies. As a result, we have achieved a well-optimized framework that closely aligns with the performance model predictions. The potential applications of our highly efficient RACE framework extend to various domains, particularly within computational science and engineering. These applications encompass eigenvalue solvers, Krylov-based iterative solvers, preconditioners, and exponential time integrators. Throughout the thesis, we have showcased several applications of our framework for both level-based coloring and cache blocking schemes.