收藏切换
Optimizing Sequences of Sparse Matrix-Vector Multiplications via Cache Data Reuse
收藏切换
Chuanfu Xu, Haozhong Qiu*, Yonggang Che
Journal of Computer Research and Development | 2025, 62(6) : 1434 - 1442
Less
收藏切换
Journal of Computer Research and Development | 2025, 62(6): 1434-1442
• Compiling and Scheduling Optimization •
Optimizing Sequences of Sparse Matrix-Vector Multiplications via Cache Data Reuse
Full
Chuanfu Xu, Haozhong Qiu*, Yonggang Che
Affiliations
  • College of Computer Science and Technology, National University of Defense Technology, Changsha 410073
  • born in 1980. PhD, associate professor. His main research interest includes high-performance computing and applications

    born in 1998. PhD candidate. His main research interest includes high-performance computing and applications

    born in 1973. PhD, professor. His main research interest includes high-performance computing and applications

About Author:

born in 1980. PhD, associate professor. His main research interest includes high-performance computing and applications

born in 1998. PhD candidate. His main research interest includes high-performance computing and applications

born in 1973. PhD, professor. His main research interest includes high-performance computing and applications

Published: 2025-06-02 doi: 10.7544/issn1000-1239.202550125
Outline
收藏切换

Many high performance computing (HPC) applications such as solving sparse linear systems involve the calculation of sequences of sparse matrix-vector multiplications (SpMV) like Ax, A2x, …, Asx, which is known as the sparse matrix power kernel (MPK). Since MPK calls SpMV using the same sparse matrix, reusing the matrix elements in cache, instead of repeatedly loading them from main memory, can potentially alleviate the memory-constrained problem for SpMV and enhance the performance of MPK. However, reusing the matrix introduces data dependencies between subsequent SpMVs. Prior work mainly either focuses on optimizing an individual SpMV invocation, or introduces significant overheads for cache data reuse in MPK. We propose a cache-aware MPK (Ca-MPK) to optimize MPK via cache data reuse. Based on the dependency graph of a sparse matrix, an architecture-aware recursive partitioning of the graph is designed to obtain subgraphs/submatrices which are fit into cache. Separating subgraphs (i.e., separators) are constructed to decouple data dependencies among subgraphs. Then cache data reuse is achieved by executing sequences of SpMVs on subgraphs with a specified order. Performance evaluation demonstrates that Ca-MPK outperforms the MPK implementations based on the Intel OneMKL library and the state-of-the-art approach, with an average speedup of up to about 1.57 times and 1.40 times, respectively.

sparse matrix-vector multiplications  /  matrix power kernel  /  cache data reuse  /  data dependencies  /  solution of sparse linear systems
徐传福, 邱昊中, 车永刚. 基于缓存数据重用的稀疏矩阵向量乘序列优化. 计算机研究与发展, 2025 , 62 (6) : 1434 -1442 . DOI: 10.7544/issn1000-1239.202550125
Chuanfu Xu, Haozhong Qiu, Yonggang Che. Optimizing Sequences of Sparse Matrix-Vector Multiplications via Cache Data Reuse[J]. Journal of Computer Research and Development, 2025 , 62 (6) : 1434 -1442 . DOI: 10.7544/issn1000-1239.202550125
Year 2025 volume 62 Issue 6
169
70
Cite this Article
BibTeX
Article Info
doi: 10.7544/issn1000-1239.202550125
  • Receive Date:2025-03-01
  • Online Date:2026-11-10
  • Published:2025-06-02
Article Data
Affiliations
History
  • Received:2025-03-01
  • Revised:2025-04-09
Affiliations
    College of Computer Science and Technology, National University of Defense Technology, Changsha 410073
References
Share
https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202550125
Share to
QR

Scan QR to access full text

Cite this article
BibTeX
Citations
表12种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏
  • BibTeX
  • EndNote
  • RefWorks
  • TxT