An Efficient Sparse Matrix Multiplication for Skewed Matrix on GPU

Abstract

This paper presents a new sparse matrix format ALIGNED COO, an extension to COO format to optimize performance of large sparse matrix having skewed distribution of nonzero elements. Load balancing, alignment and synchronization free distribution of work load are three important factors to improve performance of sparse matrices representing powerlaw graph. Coordinate (COO) format is selected for extension in this paper as it is the most suitable format for sparse matrices representing power-law graph. The ALIGNED COO format tries to set maximum alignment across the computing resources. Our heuristic to decide degree of concurrency is different from the existing approaches. Dispite the availability of other popular sparse formats, ALIGNED COO format helps to gain better performance without any extra memory overhead. Our approach not only achieves higher performance on skewed matrices with power-law distribution, but also gives appreciable performance for wide range of sparse matrix patterns. The proposed implementation of SpMV kernel for ALIGNED COO sparse format helps to achieve 1.0-25.72 times higher performance than COO flat kernel with increase in the level of accuracy. The average performance gain over other sparse formats is in tolerable range of 0.89-48.8.