Authors: Haozhong Qiu, Chuanfu Xu, Jianbin Fang, and Shengguo Li (National University of Defense Technology (NUDT), College of Computer Science and Technology); Chunye Gong (National University of Defense Technology (NUDT)); Tiaojie Xiao and Xiang Gao (National University of Defense Technology (NUDT), College of Computer Science and Technology); Liang Deng, Jian Zhang, and Zhe Dai (China Aerodynamics Research and Development Center); and Yue Ding, Yue Wang, Zhimeng Han, Qingsong Wang, Wenjing Zhang, Yonggang Che, and Jie Liu (National University of Defense Technology (NUDT), College of Computer Science and Technology)
Abstract: Many applications rely on the sparse matrix power kernel (MPK), which evaluates a short sequence of sparse matrix-vector multiplications (SpMVs) with the same matrix. MPK is therefore dominated by the memory traffic of repeatedly streaming the sparse matrix, and cache reuse across successive SpMVs offers a major opportunity to reduce data movement. However, exploiting such reuse introduces inter-SpMV dependencies that can severely restrict parallelism and induce frequent global synchronization, especially on GPUs.
This paper presents FastMPK, a cache-aware MPK designed to run efficiently on both CPUs and GPUs. FastMPK models the matrix as a dependency graph, recursively partitions it into cache-resident subgraphs, and constructs a separator subgraph to decouple cross-subgraph dependencies and recover parallel work. A dependency-preserving runtime schedule maximizes immediate cache reuse while a multi-granularity parallelization strategy enables scalability on many-core processors. Evaluated on diverse architectures, FastMPK delivers average speedups of up to 1.84× over state-of-the-art implementations.