Towards Efficient Symmetric Sparse Matrix-Vector Multiplication on Multi-Cores
ACM Transactions on Architecture and Code Optimization · 30.06.2026 · 23 (2) · 1-26
DOI: 10.1145/3803015 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Architecture and Code Optimization, online erschienen am 25.06.2026. Verfasst von Haozhong Qiu und 9 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 53 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
Exploiting matrix symmetry to halve memory footprint offers a substantial opportunity for accelerating memory-bound computations like Sparse Matrix-Vector Multiplication (SpMV). However, symmetric SpMV incurs data conflicts when concurrently writing the output vector. Previous approaches fail to address this issue efficiently, i.e., either are non-scalable or yield poor performance for large high-bandwidth irregular matrices. This article extends DCS-SpMV , a D ivide-and- C onquer (DC) based shared-memory implementation of S ymmetric SpMV. The key idea of DCS-SpMV is to recursively divide and reorder the matrix-induced conflict graph into independent subgraphs for parallel execution, and construct separate subgraphs to avoid data conflicts. The DC approach naturally transforms the input matrix into a low-conflict part and a high-conflict part, which motivates us to design a conflict-aware hybrid solution DCH-SpMV that executes these two parts using DCS-SpMV and the standard SpMV, respectively. We also develop a machine learning model for DCH-SpMV to predict the optimal number of DC recursions on a given matrix and architecture. In this work, we further optimize the hybrid DC implementation by reducing data conflicts before the DC preprocessing. First, we present a conflict-pruning strategy to decouple certain highly dense columns or rows from the conflict graph of a symmetric matrix. Second, we implement a heuristic to adaptively select the lower or upper triangular part of a symmetric matrix, leading to fewer data conflicts. Our optimizations not only facilitate the DC preprocessing, but also improve the performance of DCH-SpMV. We evaluate our work on both x86 and ARM multi-core CPUs using 298 symmetric sparse matrices from the SuiteSparse Matrix Collection. Our new optimizations improve the performance of previous version [ 42 ] by up to 4.89×, demonstrating significant speedup over the state-of-the-art approaches including the vendor-tuned Intel oneMKL library.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Qiu, H., Xu, C., Wang, Q., Fang, J., Zhang, J., Deng, L., Ding, Y., Wang, Y., Han, Z., & Che, Y. (2026). Towards Efficient Symmetric Sparse Matrix-Vector Multiplication on Multi-Cores. ACM Transactions on Architecture and Code Optimization, 23(2), 1-26. https://doi.org/10.1145/3803015
Vancouver
Qiu H, Xu C, Wang Q, Fang J, Zhang J, Deng L, et al. Towards Efficient Symmetric Sparse Matrix-Vector Multiplication on Multi-Cores. ACM Transactions on Architecture and Code Optimization. 2026;23(2):1-26. doi:10.1145/3803015
BibTeX
@article{Qiu2026,
author = {Qiu, Haozhong and Xu, Chuanfu and Wang, Qingsong and Fang, Jianbin and Zhang, Jian and Deng, Liang and Ding, Yue and Wang, Yue and Han, Zhimeng and Che, Yonggang},
title = {Towards Efficient Symmetric Sparse Matrix-Vector Multiplication on Multi-Cores},
journal = {ACM Transactions on Architecture and Code Optimization},
year = {2026},
volume = {23},
number = {2},
pages = {1--26},
doi = {10.1145/3803015}
}
EUVIMED