The 2024 SIAM Activity Group on Supercomputing Best Paper Prize Goes to NHR@FAU

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

Every two years, the Society for Industrial and Applied Mathematics (SIAM) Activity Group on Supercomputing (SIAG/SC) awards a best paper prize to the authors of the most outstanding paper in the field of parallel scientific and engineering computing published in English in a peer-reviewed journal. It is our great pleasure to announce that in 2024, the award goes to the paper

A Recursive Algebraic Coloring Technique for Hardware-Efficient Symmetric Sparse Matrix-Vector Multiplication

by Christie L. Alappat, Georg Hager, Olaf Schenk, Jonas Thies, Achim Basermann, Alan R. Bishop, Holger Fehske, and Gerhard Wellein.

This work was published in June 2020 in the renowned journal ACM Transactions on Parallel Computing. It is a collaboration among researchers from several institutions: NHR@FAU, the University of Lugano (Switzerland), German Aerospace Center (DLR), Los Alamos National Laboratory (USA), and the University of Greifswald (Germany).

Christie L. Alappat
Christie L. Alappat, lead author of the award-winning paper and developer of the RACE algorithm and library

This paper solves a long-standing problem in computational science. Mathematical models of many complex systems in science and engineering involve very large, sparse matrices, i.e., matrices in which almost all entries are zero. Although this sounds encouraging, it actually complicates matters when implementing algorithms, especially if one aims for high performance and efficiency on modern parallel computers. A key component in many algorithms is the multiplication of a sparse matrix with a vector (SpMV). This important computational kernel can be parallelized easily; however, if the matrix is symmetric and only half of it is stored in memory, parallelization becomes a hard problem. Although many partial solutions have been presented in the literature, they all involve compromises that can cause inefficiencies due to load imbalance and bad hardware utilization. In our award-winning paper, a novel algorithm and library was introduced, the Recursive Algebraic Coloring Engine (RACE).  It can adapt the parallelism in symmetric SpMV to the underlying hardware while retaining good load balancing and cache-friendly data access patterns. RACE is not restricted to optimizing symmetric SpMV but has already been shown to improve the performance of other relevant kernels and solvers in sparse  linear algebra.

Christie Alappat is the lead author of the paper. He is a PhD student at FAU and actively involved in user support in the field of sparse solvers and linear algebra at NHR@FAU. He will present the work during an awards session at the 2024 SIAM Conference on Parallel Processing for Scientific Computing (PP24) in Baltimore, MD on March 7.