Optimization Of Sparse Matrix Vector Multiplication And Prediction Method Of Optimal Storage Format On GPUs

Solving large(sparse)linear system of algebraic equations(Ax=b)is the ba-sic common problem of scientific computing,and its main computational work is(sparse)matrix vector multiplication(SpMV),so efficient computation of matrix vector multiplication is the core of scientific calculation.With the rapid develop-ment of GPU in recent years,its multi-processor and unique physical architecture is suitable for compute-intensive and highly parallel computation.The performance of SpMV on GPU is mainly affected by the storage format of sparse matrix.In this paper,the optimization of sparse matrix vector multiplication and the prediction of optimal storage format on GPUs are studied.Firstly,based on the ordering idea of JAD format,we proposed an optimized and improved ELLR format,which we call it PELLR format.The ordering method reduces the number of iterations and redundant calculations of the SpMV,and the performance of the PELLR format is about 1.5 times better than that of the ELLR format in our test.The PELLR format is also superior to other formats,such as CSR,BiELL and so on,on the case of 70%test matrix.In addition,the formulas are derived to calculate the number of iterations and the degree of perturbation of the number of non-zero elements in each row of the matrix.Secondly,we propose a method to estimate the computing time of SpMV on GPU,from which to predict the storage format for optimal SpMV performance.The method adopts the idea of divide and conquer.The total time is divided into three parts:data transfer TC,SpMV calculation Ts and result rearrangement Tp.The estimation of each part uses the architecture parameters of GPU and the structure characteristics of sparse matrix,respectively.The Ts estimation is based on dividing the number of matrix rows into different intervals,and modeling the relationship between the number of iterations and the time on each interval by machine learning method.Furthermore,we study the influence of the computing time of SpMV on the time proportion of each part.The verification on ELL format shows that the accuracy of prediction is 85%both for relative error ?0.05 and absolute error ?1.5,respectively.