search-icon
ACM Student Research Competition
Poster
:
Recursive Algebraic Coloring Engine
Event Type
ACM Student Research Competition
Poster
Registration Categories
TP
EX
TimeTuesday, November 13th8:30am - 5pm
DescriptionMany 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×.
Archive
Back To Top Button