EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Towards Efficient Symmetric Sparse Matrix-Vector Multiplication on Multi-Cores

Haozhong Qiu, Chuanfu Xu, Qingsong Wang, Jianbin Fang, Jian Zhang, Liang Deng, Yue Ding, Yue Wang, Zhimeng Han, Yonggang Che

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →