Speculative segmented sum for sparse matrix-vector multiplication on heterogeneous processors

TY - JOUR

T1 - Speculative segmented sum for sparse matrix-vector multiplication on heterogeneous processors

AU - Liu, Weifeng

AU - Vinter, Brian

PY - 2015/11/1

Y1 - 2015/11/1

N2 - 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 result. 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.

AB - 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 result. 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.

KW - Compressed sparse row

KW - Heterogeneous processors

KW - Segmented sum

KW - Sparse matrices

KW - Sparse matrix-vector multiplication

KW - Speculative execution

U2 - 10.1016/j.parco.2015.04.004

DO - 10.1016/j.parco.2015.04.004

M3 - Journal article

SN - 0167-8191

VL - 49

SP - 179

EP - 193

JO - Parallel Computing

JF - Parallel Computing

ER -