Research And Application Of Parallel Sparse Diagonal Matrix-vector Multiplication Algorithm On GPU

Sparse matrix structure has existed in many disciplines and has widely used in the fields of linear algebra,data mining,graph analysis and some other areas.Sparse matrix-vector multiplication shows great significance in the field of computational science.With the maturity of GPU(Graphics Processing Unit)programming model and development of tool chain,many researchers have paid attention to accelerating sparse matrix-vector multiplication on GPU.Sparse diagonal matrices are a sort of special sparse matrices.Most of the non-zero elements in the matrix are concentrated on a small number of diagonals.The DIA(Diagonal Storage)format is the most suitable storage format for storing sparse diagonal matrices.For diagonal sparse matrices that have many long zero sections or scatter points or diagonal deviations from the main diagonal,a great number of zeros need be filled to maintain the diagonal structure while using DIA to store them,which leads to the performance degradation of the existing DIA kernels.Sparse block diagonal matrices are also a kind of special sparse matrices.Its structure of the non-zero elements has a certain regularity and presents block diagonal.Obviously,the DIA format is not suitable for storing this kind of matrices.Although the CSR(Compressed Row Storage)and ELL(ELLPACK Storage)formats can store them effectively,the performance of their kernels is not good because they do not utilize diagonal structure.Therefore,based on the two kinds of matrices and GPU programming model CUDA(Compute Unified Device Architecture),the sparse diagonal matrix-vector multiplication algorithm on GPU is studied in this thesis.To sum up,the main work and contributions of this thesis are as follows:1.Propose an adaptive sparse matrix-vector multiplication algorithm for diagonal sparse matrices on GPU,which is called DIA-Adaptive.For diagonal sparse matrices that have many long zero sections or scatter points or diagonal deviations from the main diagonal,the matrixs are divided into three categories according to some rules firstly.Secondly,based on the classification,the thesis proposes two novel algorithms BRCSD(Diagonal Compressed Storage based on Row-Blocks)-? and BRCSD-? to adapt it to various types of diagonal sparse matrices besides adopting DIA.Finally,a search engine is designed to choose the most appropriate storage format and kernel automatically for any diagonal sparse matrix.Experimental results show that the proposed DIA-Adaptive is valid and has high performance.2.Propose a parallel sparse matrix-vector multiplication algorithm for block diagonal matrix on GPU,which is called IndexBDIA.For a class of sparse block diagonal matrices by using its block diagonal structure,the thesis divides the sparse block diagonal matrices into a number of small block with a certain size and record the row and column index values corresponding to each small block to search the block diagonals.The establishment of block diagonal reduces the storage of row and column index values.Finally,according to the block diagonal offset value,the matrix is divided into several row-segement matrixs to store.It effectively reduces the filling of zero-elements when the block diagonals deviate from the main block diagonal in the matrix.Experiments show that the IndexBDIA algorithm has high performance.3.Verify the effectiveness of the proposed algorithm by applying it to solve the Klein-Gordon-Schrodinger(KGS)equation.For the sparse diagonal linear system by discreting the 2D and 3D KGS equations,based on the GMRES(Generalized Minimum Residual Method)algorithm and the proposed adaptive sparse matrix-vector multiplication algorithm,the thesis proposes a GPU-accelerated time-domain algorithm,which is called T-GMRES.The experimental results show that T-GMRES algorithm is effective in solving the KGS 2D and 3D equations.