HAM-SpMSpV: an Optimized Parallel Algorithm for Masked Sparse Matrix-Sparse Vector Multiplications on multi-core CPUs
Open Access
- 3 June 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 160-173
Abstract
The efficiency of Sparse Matrix-Sparse Vector Multiplication (SpM-SpV) is critically important in fields such as machine learning and graph analytics. In certain algorithms, masked SpMSpV computes only a subset of the result entries. Despite its significance, this selective computation poses unique challenges, and existing algorithms often struggle to exploit the sparsity of the input and the mask vectors concurrently. To boost the efficiency of masked SpMSpV on shared memory architectures, we introduce a hybrid adaptive masked SpMSpV algorithm (HAM-SpMSpV) designed to select the efficient kernel automatically based on input features. This approach builds upon the foundation of a conventional algorithm, incorporating two novel masked SpMSpVs: the pre-bucketing masked SPA-based algorithm and the pre-masking bucketed hash-based algorithm. The newly proposed algorithms significantly expedite computation, especially in scenarios with high sparsity in input vectors and masks. Our evaluation involved extensive testing across a diverse range of real-world graphs, utilizing various sparsity of input vectors and masks. This rigorous testing confirmed that our approach notably outperforms existing solutions. Specifically, it achieves a speedup of up to 1.96 times compared to SuiteSparse:GraphBLAS and a remarkable 6.28 times relative to MKL Graph, demonstrating significant advancements in SpMSpV efficiency.Keywords
Funding Information
- National Key Research and Development Program of China (2023 YFB3001700)
- National Natural Science Foundation of China (No.62372432, No.61972376, No.62072431, No.62032023)
- Shanxi Province Science and Technology Major Special Project (No.202201010101004)
This publication has 39 references indexed in Scilit:
- Segmented Merge: A New Primitive for Parallel Sparse Matrix ComputationsInternational Journal of Parallel Programming, 2021
- Towards an Auto-Tuned and Task-Based SpMV (LASs Library)2020
- Performance optimization, modeling and analysis of sparse matrix-matrix products on multi-core and many-core processorsParallel Computing, 2019
- Register-Aware Optimizations for Parallel Sparse Matrix–Matrix MultiplicationInternational Journal of Parallel Programming, 2019
- Multithreaded sparse matrix-matrix multiplication for many-core and GPU architecturesParallel Computing, 2018
- Optimizing and auto-tuning scale-free sparse matrix-vector multiplication on Intel Xeon Phi2015
- Graphs, Matrices, and the GraphBLAS: Seven Good ReasonsProcedia Computer Science, 2015
- Intel Math Kernel Library2014
- Automatically Tuning Sparse Matrix-Vector Multiplication for GPU Architectures2010
- Towards a Theory of Scale-Free Graphs: Definition, Properties, and ImplicationsInternet Mathematics, 2005