fgSpMSpV: A Fine-grained Parallel SpMSpV Framework on HPC Platforms
Yuedan Chen, Guoqing Xiao, Kenli Li, Francesco Piccialli, Albert Y. Zomaya · ACM Transactions on Parallel Computing · 2022
Sparse matrix-sparse vector (SpMSpV) multiplication is one of the fundamental and important operations in many high-performance scientific and engineering applications. The inherent irregularity and poor data locality lead to two main challenges to scaling SpMSpV over high-performance computing (HPC) systems: (i) a large amount of redundant data limits the utilization of bandwidth and parallel resources; (ii) the irregular access pattern limits the exploitation of computing resources. This paper proposes a fine-grained parallel SpMSpV (fgSpMSpV) framework on Sunway TaihuLight supercomputer to alleviate the challenges for large-scale real-world applications. First,fgSpMSpVadopts an MPI \( + \) OpenMP \( +X \) parallelization model to exploit the multi-stage and hybrid parallelism of heterogeneous HPC architectures and accelerate both pre-/post-processing and main SpMSpV computation. Second,fgSpMSpVutilizes an adaptive parallel execution to reduce the pre-processing, adapt to the parallelism and memory hierarchy of the Sunway system, while still tame redundant and random memory accesses in SpMSpV, including a set of techniques like the fine-grained partitioner, re-collection method, and Compressed Sparse Column Vector (CSCV) matrix format. Third,fgSpMSpVuses several optimization techniques to further utilize the computing resources.fgSpMSpVon the Sunway TaihuLight gains a noticeable performance improvement from the key optimization techniques with various sparsity of the input. Additionally,fgSpMSpVis implemented on an NVIDIA Tesal P100 GPU and applied to the breath-first-search (BFS) application.fgSpMSpVon a P100 GPU obtains the speedup of up to \( 134.38\times \) over the state-of-the-art SpMSpV algorithms, and the BFS application usingfgSpMSpVachieves the speedup of up to \( 21.68\times \) over the state-of-the-arts.