Optimization techniques for sparse matrix-vector multiplication on GPUs

doi:10.1016/j.jpdc.2016.03.011

Optimization techniques for sparse matrix-vector multiplication on GPUs

2016-07-01

21

OA

AI

DOI：10.1016/j.jpdc.2016.03.011

Original

Save

View PDF

Abstract

En 中文

Sparse linear algebra is fundamental to numerous areas of applied mathematics, science and engineering. In this paper, we propose an efficient data structure named AdELL+ for optimizing the SpMV kernel on GPUs, focusing on performance bottlenecks of sparse computation. The foundation of our work is an ELL-based adaptive format which copes with matrix irregularity using balanced warps composed using a parametrized warp-balancing heuristic. We also address the intrinsic bandwidth-limited nature of SpMV with warp granularity, blocking, delta compression and nonzero unrolling, targeting both memory footprint and memory hierarchy efficiency. Finally, we introduce a novel online auto-tuning approach that uses a quality metric to predict efficient block factors and that hides preprocessing overhead with useful SpMV computation. Our experimental results show that AdELL+ achieves comparable or better performance over other state-of-the-art SpMV sparse formats proposed in academia (BCCOO) and industry (CSR+ and CSR-Adaptive). Moreover, our auto-tuning approach makes AdELL+ viable for real world applications. (C) 2016 Elsevier Inc. All rights reserved.

Keywords:

SpMV

Optimization

GPU

Adaptive

AdELL

Blocking

Compression

Unrolling

Auto-tuning

Optimization techniques for sparse matrix-vector multiplication on GPUs

Abstract

AI Summary

Journal

Organization