Home Publications edited volumes Awards Research Teaching Miscellaneous Full CV [pdf] BLOG
Events
Past Events

Publications of Torsten Hoefler
Lukas Gianinazzi, Alexandros Nikolaos Ziogas, Piotr Luczynski, Langwen Huang, Saleh Ashkboos, Florian Scheidl, Armon Carigiet, Chio Ge, Nabil Abubaker, Maciej Besta, Tal BenNun, Torsten Hoefler:
  Arrow Matrix Decomposition: A Novel Approach for CommunicationEfficient Sparse Matrix Multiplication
(In Proceedings of the 29th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP'24), presented in Edinburgh, United Kingdom, pages 404416, Association for Computing Machinery, Mar. 2024)
Publisher Reference
AbstractWe 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 communicationavoiding multiplications, achieving a polynomial reduction in communication volume per iteration for matrices corresponding to planar graphs and other minorexcluded families of graphs. Our evaluation demonstrates that our approach outperforms a stateoftheart method for sparse matrix multiplication on matrices with hundreds of millions of rows, offering nearlinear strong and weak scaling.
DocumentsPublisher URL: https://dl.acm.org/doi/10.1145/3627535.3638496download article: download slides:   BibTeX  @inproceedings{gianinazzi2024arrow, author={Lukas Gianinazzi and Alexandros Nikolaos Ziogas and Piotr Luczynski and Langwen Huang and Saleh Ashkboos and Florian Scheidl and Armon Carigiet and Chio Ge and Nabil Abubaker and Maciej Besta and Tal BenNun and Torsten Hoefler}, title={{Arrow Matrix Decomposition: A Novel Approach for CommunicationEfficient Sparse Matrix Multiplication}}, year={2024}, month={Mar.}, pages={404416}, booktitle={Proceedings of the 29th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP'24)}, location={Edinburgh, United Kingdom}, publisher={Association for Computing Machinery}, source={http://www.unixer.de/~htor/publications/}, } 

