Arrow Matrix Decomposition: A Novel Approach for Communication-Efficient Sparse Matrix Multiplication
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929282868051968 |
|---|---|
| author | Gianinazzi, Lukas Ziogas, Alexandros Nikolaos Huang, Langwen Luczynski, Piotr Ashkboos, Saleh Scheidl, Florian Carigiet, Armon Ge, Chio Abubaker, Nabil Besta, Maciej Ben-Nun, Tal Hoefler, Torsten |
| author_facet | Gianinazzi, Lukas Ziogas, Alexandros Nikolaos Huang, Langwen Luczynski, Piotr Ashkboos, Saleh Scheidl, Florian Carigiet, Armon Ge, Chio Abubaker, Nabil Besta, Maciej Ben-Nun, Tal Hoefler, Torsten |
| contents | We propose a novel approach to iterated sparse matrix dense matrix multiplication, a fundamental computational kernel in scientific computing and graph neural network training. In cases where matrix sizes exceed the memory of a single compute node, data transfer becomes a bottleneck. An approach based on dense matrix multiplication algorithms leads to suboptimal scalability and fails to exploit the sparsity in the problem. To address these challenges, we propose decomposing the sparse matrix into a small number of highly structured matrices called arrow matrices, which are connected by permutations. Our approach enables communication-avoiding multiplications, achieving a polynomial reduction in communication volume per iteration for matrices corresponding to planar graphs and other minor-excluded families of graphs. Our evaluation demonstrates that our approach outperforms a state-of-the-art method for sparse matrix multiplication on matrices with hundreds of millions of rows, offering near-linear strong and weak scaling. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_19364 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Arrow Matrix Decomposition: A Novel Approach for Communication-Efficient Sparse Matrix Multiplication Gianinazzi, Lukas Ziogas, Alexandros Nikolaos Huang, Langwen Luczynski, Piotr Ashkboos, Saleh Scheidl, Florian Carigiet, Armon Ge, Chio Abubaker, Nabil Besta, Maciej Ben-Nun, Tal Hoefler, Torsten Distributed, Parallel, and Cluster Computing F.2.1 We propose a novel approach to iterated sparse matrix dense matrix multiplication, a fundamental computational kernel in scientific computing and graph neural network training. In cases where matrix sizes exceed the memory of a single compute node, data transfer becomes a bottleneck. An approach based on dense matrix multiplication algorithms leads to suboptimal scalability and fails to exploit the sparsity in the problem. To address these challenges, we propose decomposing the sparse matrix into a small number of highly structured matrices called arrow matrices, which are connected by permutations. Our approach enables communication-avoiding multiplications, achieving a polynomial reduction in communication volume per iteration for matrices corresponding to planar graphs and other minor-excluded families of graphs. Our evaluation demonstrates that our approach outperforms a state-of-the-art method for sparse matrix multiplication on matrices with hundreds of millions of rows, offering near-linear strong and weak scaling. |
| title | Arrow Matrix Decomposition: A Novel Approach for Communication-Efficient Sparse Matrix Multiplication |
| topic | Distributed, Parallel, and Cluster Computing F.2.1 |
| url | https://arxiv.org/abs/2402.19364 |