spECK: Accelerating GPU Sparse Matrix-Matrix Multiplication Through Lightweight Analysis
Sparse general matrix-matrix multiplication on GPUs is challenging due to the varying sparsity patterns of sparse matrices. Existing solutions achieve good performance for certain types of matrices, but fail to accelerate all kinds of matrices in the same manner. Our approach combines multiple strategies with dynamic parameter selection to dynamically choose and tune the best fitting algorithm for each row of the matrix. This choice is supported by a lightweight, multi-level matrix analysis, which carefully balances between analysis cost and expected performance gains. Our evaluation on thousands of matrices with various characteristics shows that we outperform all existing solutions in 85% of the cases and that we achieve the second best performance in 12%. Over the entire data set, our solution is on average twice as fast as the second best approach and up to 25$\times$ faster than other state-of-the-art GPU implementations. Using our approach, applications can expect the best performance independent of the matrices they work on.
Wed 26 FebDisplayed time zone: Tijuana, Baja California change
11:20 - 12:35 | Matrix Multiplication and Approximation (Mediterranean Ballroom)Main Conference Chair(s): Albert Cohen Google | ||
11:20 25mTalk | spECK: Accelerating GPU Sparse Matrix-Matrix Multiplication Through Lightweight Analysis Main Conference Mathias Parger Graz University of Technology, Martin Winter Graz University of Technology, Austria, Daniel Mlakar Graz University of Technology, Austria, Markus Steinberger Graz University of Technology, Austria | ||
11:45 25mTalk | A Novel Data Transformation and Execution Strategy for Accelerating Sparse Matrix Multiplication on GPUs Main Conference Peng Jiang The University of Iowa, Changwan Hong The Ohio State University, Gagan Agrawal The Ohio State University | ||
12:10 25mTalk | MatRox: Modular approach for improving data locality in Hierarchical (Mat)rix App(Rox)imation Main Conference Bangtian Liu University of Toronto, Kazem Cheshmi University of Toronto, Saeed Soori University of Toronto, Michelle Strout University of Arizona, Maryam Mehri Dehnavi University of Toronto |