Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication

Abstract : Sparse matrix-matrix multiplication (or SpGEMM) is a key primitive for many high-performance graph algorithms as well as for some linear solvers, such as algebraic multigrid. The scaling of existing parallel implementations of SpGEMM is heavily bound by communication. Even though 3D (or 2.5D) algorithms have been proposed and theoretically analyzed in the flat MPI model on Erdös--Rényi matrices, those algorithms had not been implemented in practice and their complexities had not been analyzed for the general case. In this work, we present the first implementation of the 3D SpGEMM formulation that exploits multiple (intranode and internode) levels of parallelism, achieving significant speedups over the state-of-the-art publicly available codes at all levels of concurrencies. We extensively evaluate our implementation and identify bottlenecks that should be subject to further research. Read More: http://epubs.siam.org/doi/10.1137/15M104253X
Type de document :
Article dans une revue
SIAM Journal on Scientific Computing, Society for Industrial and Applied Mathematics, 2016, 38 (6), pp.27. 〈10.1137/15M104253X〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01426294
Contributeur : Laura Grigori <>
Soumis le : mercredi 4 janvier 2017 - 12:46:25
Dernière modification le : vendredi 31 août 2018 - 09:06:03

Lien texte intégral

Identifiants

Collections

Citation

Ariful Azad, Grey Ballard, Aydin Buluc, James W. Demmel, Laura Grigori, et al.. Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication. SIAM Journal on Scientific Computing, Society for Industrial and Applied Mathematics, 2016, 38 (6), pp.27. 〈10.1137/15M104253X〉. 〈hal-01426294〉

Partager

Métriques

Consultations de la notice

252