Speculative Segmented Sum for Sparse Matrix-Vector Multiplication on Heterogeneous Processors

Abstract

Sparse matrix-vector multiplication (SpMV) is a central building block for scientific software and graph applications. Recently, heterogeneous processors composed of different types of cores attracted much attention because of their flexible core configuration and high energy efficiency. In this paper, we propose a compressed sparse row (CSR) format based SpMV algorithm utilizing both types of cores in a CPU-GPU heterogeneous processor. We first speculatively execute segmented sum operations on the GPU part of a heterogeneous processor and generate a possibly incorrect results. Then the CPU part of the same chip is triggered to re-arrange the predicted partial sums for a correct resulting vector. On three heterogeneous processors from Intel, AMD and nVidia, using 20 sparse matrices as a benchmark suite, the experimental results show that our method obtains significant performance improvement over the best existing CSR-based SpMV algorithms. The source code of this work is downloadable at https://github.com/bhSPARSE/Benchmark_SpMV_using_CSR

22 pages, 8 figures, Published at Parallel Computing (PARCO)

References in corpus (1)

• CSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector Multiplication

Cited by in corpus (5)

• A Recursive Algebraic Coloring Technique for Hardware-Efficient Symmetric Sparse Matrix-Vector Multiplication
• A Framework for General Sparse Matrix-Matrix Multiplication on GPUs and Heterogeneous Processors
• AdR-Gaussian: Accelerating Gaussian Splatting with Adaptive Radius
• Characterizing Scalability of Sparse Matrix-Vector Multiplications on Phytium FT-2000+ Many-cores
• On Parallel Solution of Sparse Triangular Linear Systems in CUDA