Efficient Tiled Sparse Matrix Multiplication through Matrix Signatures
| Autor: | Aravind Sukumaran-Rajam, P. Sadayyapan, Sureyya Emre Kurt, Fabrice Rastello |
|---|---|
| Přispěvatelé: | University of Utah, Washington State University (WSU), Compiler Optimization and Run-time Systems (CORSE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), School of computing [UTAH] |
| Rok vydání: | 2020 |
| Předmět: |
Sparse Dense Matrix Multiplication
Computer science Computation MathematicsofComputing_NUMERICALANALYSIS 010103 numerical & computational mathematics 02 engineering and technology 01 natural sciences Kernel (linear algebra) Matrix (mathematics) 0202 electrical engineering electronic engineering information engineering [INFO]Computer Science [cs] Tensor 0101 mathematics Multi-core Sparse matrix computations SpMM Sparse matrix [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL] SpMDM sparse matrix signature Matrix multiplication [INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF] Kernel (image processing) sparse tiling 020201 artificial intelligence & image processing Multiplication [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] Algorithm |
| Zdroj: | SC SC 2020-International Conference for High Performance Computing, Networking, Storage and Analysis SC 2020-International Conference for High Performance Computing, Networking, Storage and Analysis, Nov 2020, virtual, United States. pp.1-13 |
| DOI: | 10.1109/sc41405.2020.00091 |
| Popis: | International audience; Tiling is a key technique to reduce data movement in matrix computations. While tiling is well understood and widely used for dense matrix/tensor computations, effective tiling of sparse matrix computations remains a challenging problem. This paper proposes a novel method to efficiently summarize the impact of the sparsity structure of a matrix on achievable data reuse as a one-dimensional signature, which is then used to build an analytical cost model for tile size optimization for sparse matrix computations. The proposed model-driven approach to sparse tiling is evaluated on two key sparse matrix kernels: Sparse Matrix-Dense Matrix Multiplication (SpMM) and Sampled Dense-Dense Matrix Multiplication (SDDMM). Experimental results demonstrate that model-based tiled SpMM and SDDMM achieve high performance relative to the current state-of-the-art. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|