Low Thread-Count Gustavson: A Multithreaded Algorithm for Sparse Matrix-Matrix Multiplication Using Perfect Hashing
Authors: James Elliott (Sandia National Laboratories)
Abstract: Sparse matrix-matrix multiplication is a critical kernel for several scientific computing applications, especially the setup phase of algebraic multigrid. The MPI+X programming model, which is growing in popularity, requires that such kernels be implemented in a way that exploits on-node parallelism. We present a single-pass OpenMP variant of Gustavson’s sparse matrix-matrix multiplication algorithm designed for architectures (e.g. CPU or Intel Xeon Phi) with reasonably large memory and modest thread counts (tens of threads, not thousands). These assumptions allow us to exploit perfect hashing and dynamic memory allocation achieve performance improvements of up to 2x over third-party kernels for matrices derived from algebraic multigrid setup.
Back to 9th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems Archive Listing
Back to Full Workshop Archive Listing