Memory bandwidth optimization of SpMV on GPGPUs

• Published in: Frontiers of Computer Science 2015-06, Vol.9 (3), p.431-441
• Main Authors: YAN, Chenggang Clarence, YU, Hui, XU, Weizhi, ZHANG, Yingping, CHEN, Bochuan, TIAN, Zhu, WANG, Yuxuan, YIN, Jian
• Format: Article
• Language: English
• Subjects: Bandwidths; cache blocking; Computer architecture; Computer Science; Format; GeForce; GPGPU; GPU; Graphics processing units; Mathematical analysis; memory bandwidth; Performance enhancement; performance tuning; Research Article; Sparse matrices; Sparsity; SpMV; 内存带宽; 存储器; 存储格式; 带宽优化; 稀疏矩阵; 高速缓存
• ISSN: 2095-2228; 2095-2236
• DOI: 10.1007/s11704-014-4127-1

It is an important task to improve performance for sparse matrix vector multiplication （SpMV）, and it is a difficult task because of its irregular memory access. Gen- eral purpose GPU （GPGPU） provides high computing abil- ity and substantial bandwidth that cannot be fully exploited by SpMV due to its irregularity. In this paper, we propose two novel methods to optimize the memory bandwidth for SpMV on GPGPU. First, a new storage format is proposed to exploit memory bandwidth of GPU architecture more effi- ciently. The new storage format can ensure that there are as many non-zeros as possible in the format which is suitable to exploit the memory bandwidth of the GPU. Second, we pro- pose a cache blocking method to improve the performance of SpMV on GPU architecture. The sparse matrix is partitioned into sub-blocks that are stored in CSR format. With the block- ing method, the corresponding part of vector x can be reused in the GPU cache, so the time to access the global memory for vector x is reduced heavily. Experiments are carried out on three GPU platforms, GeForce 9800 GX2, GeForce GTX 480, and Tesla K40. Experimental results show that both new methods can efficiently improve the utilization of GPU mem- ory bandwidth and the performance of the GPU.