<span class="var-sub_title">Recursive Algebraic Coloring Engine</span> SC18 Proceedings

The International Conference for High Performance Computing, Networking, Storage, and Analysis

Recursive Algebraic Coloring Engine


Student: Christie Louis Alappat (University of Erlangen-Nuremberg)
Supervisor: Georg Hager (University of Erlangen-Nuremberg)

Abstract: Many iterative numerical methods for sparse systems and building blocks of sparse linear algebra are difficult to parallelize due to data dependencies. These may be loop-carried dependencies as they occur in solvers like Gauss-Seidel or write conflicts as in symmetric sparse matrix vector. Most of the existing parallelization strategies suffer from low performance on modern hardware, are matrix specific, or require tailored storage formats.

In this poster, we introduce a novel recursive level based algorithm called Recursive Algebraic Coloring (RAC), which achieves high hardware efficiency on modern multi-core architectures and works with simple data formats like compressed row storage. Method is implemented in a library called Recursive Algebraic Coloring Engine (RACE). Thorough performance analysis shows that RACE outperforms traditional multicoloring methods and Intel-MKL implementations with a factor of 2–2.5×. We are on par with Algebraic Block Multicoloring for small matrices, while for large matrices we gain a factor of 1.5–2×.


ACM-SRC Semi-Finalist: no

Poster: PDF
Poster Summary: pdf
Reproducibility Description Appendix: PDF


Back to Poster Archive Listing