Adaptive sparse matrix representation for efficient matrix-vector multiplication

摘要

A wide range of applications in engineering and scientific computing are based on the sparse matrix computation. There exist a variety of data representations to keep the non-zero elements in sparse matrices, and each representation favors some matrices while not working well for some others. The existing studies tend to process all types of applications, e.g., the most popular application which is matrix-vector multiplication, with different sparse matrix structures using a fixed representation. While Graphics Processing Units (GPUs) have evolved into a very attractive platform for general purpose computations, most of the existing works on sparse matrix-vector multiplication (SpMV, for short) consider CPUs. In this work, we design and implement an adaptive GPU-based SpMV scheme that selects the best format for the input matrix having the configuration and characteristics of GPUs in mind. We study the effect of various parameters and different settings on the performance of SpMV applications when employing different data representations. We then employ an adaptive scheme to execute different sparse matrix applications using proper sparse matrix representation formats. Evaluation results show that our run-time adaptive scheme properly adapts to different applications by selecting an appropriate representation for each input sparse matrix. The preliminary results show that our adaptive scheme improves the performance of sparse matrix multiplications by 2.1 for single-precision and 1.6 for double-precision formats, on average.