<span class="var-sub_title">Low Thread-Count Gustavson: A Multithreaded Algorithm for Sparse Matrix-Matrix Multiplication Using Perfect Hashing</span> SC18 Proceedings

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

9th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems


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.

Archive Materials


Back to 9th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems Archive Listing

Back to Full Workshop Archive Listing