Optimizing sparse Matrix-Vector Multiplication on GPU

Abstract

In era of today’s revolutionary world, we are witnessing increasing demand of parallel devices like modern microprocessors for High-performance scientific computing. GPUs have attracted attention at leading edge of this trend. The computational power of GPUs has increased at a much higher rate than CPUs. Large size Sparse Matrix-Vector Multiplication (SpMV) is one of most important operation in scientific and engineering computing. Implementation of SpMV has become complex because of indirection used in its storage presentation to exploit matrix sparsity. Thus, Designing parallel algorithm for SpMV presents interesting challenge for academia to achieve higher performance. Hence, sparse matrix-vector multiplication is an important and challenging GPU kernel. Many storage formats and efficient implementation for Sparse Matrix –Vector multiplication have been proposed in past. Sparse matrix problem has main two challenges: (i) optimized storage format (ii) efficient method to access nonzero elements form low latency and low bandwidth memory. Implementing SpMV on GPU has additional challenges: (i) best resource (thread) utilization to achieve high parallelization (ii) Avoidance of thread divergence, and (iii) coalesced memory access. In this paper, we have analyzed various proposed storage formats for optimized storage of sparse matrix like Coordinate format (COO), Compressed Row Storage (CRS), Block Compressed Row Storage (BCRS), ELLPACK, Sparse Compressed Row Storage (SBCRS). In this paper, we have proposed an alternative optimized storage format BCRS-combo and its implementation for SpMV to achieve high-performance for SpMV kernel on NVIDIA GPU considering parameters like excessive padding, storage compaction, Memory bandwidth, reloading of input and output vector, time to reorder elements, and execution time. We show that BCRS-combo not only improves performance over these methods, but it also improves storage space management.