BiELL: A bisection ELLPACK-based storage format for optimizing SpMV on GPUs

• SpMV is one of the most important high level operations for basic linear algebra.
• We will show how to achieve high performance for general SpMV on GPUs.
• BiELL format and its improvement BiJAD format were proposed.
• They have better load balance, access the data coalescing and thus higher performance.
• They perform better especially when the number of non-zero elements per row varies a lot.

Sparse matrix–vector multiplication (SpMV) is one of the most important high level operations for basic linear algebra. Nowadays, the GPU has evolved into a highly parallel coprocessor which is suited to compute-intensive, highly parallel computation. Achieving high performance of SpMV on GPUs is relatively challenging, especially when the matrix has no specific structure. For these general sparse matrices, a new data structure based on the bisection ELLPACK format, BiELL, is designed to realize the load balance better, and thus improve the performance of the SpMV. Besides, based on the same idea of JAD format, the BiJAD format can be obtained. Experimental results on various matrices show that the BiELL and BiJAD formats perform better than other similar formats, especially when the number of non-zero elements per row varies a lot.