NHR PerfLab Seminar: Performance Engineering for Sparse Matrix-Vector Multiplication with the Recursive Algebraic Coloring Engine

Symbolic picture for the article. The link opens the image in a large view.

Speaker:  Christie L. Alappat, Erlangen National High Performance Computing Center (NHR@FAU)

Title: Performance Engineering for Sparse Matrix-Vector Multiplication with the Recursive Algebraic Coloring Engine

Date & time: Tuesday, February 1, 2022, 2:00 p.m. – 3:00 p.m. CET



The sparse matrix-vector multiplication (SpMV) kernel is a key performance component of numerous algorithms in computational science. Despite the kernel’s apparent simplicity, the sparse and potentially irregular data access patterns of SpMV and its intrinsically low computational intensity have been challenging the development of high-performance implementations over decades. In this talk, we present methods to increase the computational intensity and thereby accelerate the performance of SpMV kernels on symmetric and/or square matrices. The method is based on the concept of levels as developed in the context of our RACE library framework [1]. We demonstrate that one can typically achieve a speedup of 1.5-4x on a single modern Intel or AMD multicore chip for symmetric SpMV and matrix power kernels using this level-based approach.

After introducing optimization strategies, the talk sheds light on the application of these optimized kernels in iterative solvers. To this end, we discuss the coupling of the RACE library with the Trilinos framework and address the application to commonly found solvers like GMRES and its s-step variants, which benefit from our optimizations.

The work on RACE has been started in the ESSEX project within the DFG priority program SPPEXA and has received multiple international awards including the SC18 Best Student Poster Award and the second place in the 2019 ACM Student Research Competition Grand Finals.

[1] Alappat, C. L. et al: A Recursive Algebraic Coloring Technique for Hardware-efficient Symmetric Sparse Matrix-vector Multiplication. In: ACM TOPC 7 (2020), Article No.: 19. ISSN: 2329-4949. DOI: 10.1145/3399732


Speaker bio

Christie Louis Alappat graduated with a Masters degree in computational engineering from Friedrich Alexander University, Erlangen. He is currently doing his PhD under the guidance of Prof. Dr. Gerhard Wellein. Research interests include performance engineering, sparse matrix and graph algorithms, linear solvers and eigenvalue computations.