Research On Sparse Matrix Storage Format Suitable For Vectorization

The Sparse matrix-vector multiplication(SpMV)operation(y=A*x)is widely used in scientific and engineering calculations such as linear algebra,particle transport simulation,hydrodynamics partial differential equation solution,astrophysics and fractional problems.It has been categorized as a member of the “seven dwarfs”,i.e.the numerical methods which are believed to be important for at least the next decade.The study of sparse matrix vector multiplication helps to improve the research in there related fields and solve the problem of computing efficiency.Therefore,this study is meaningful.In SpMV,sparse matrices are dominated by a large number of zeros which cause irregular memory access patterns and poor floating-point performance.This irregularity results in hardly using the vector unit and increasing the number of cache miss.Achieving high performance of SpMV,which heavily relies on the storage format of sparse matrices in memory,requires to choose a compact data structure and code transformations especially for the calculations involving large-scale sparse matrices.In this paper,series optimization methods of SpMV have been approached.In order to take full advantage of the SIMD(single instruction multiple data)acceleration technology in SpMV,we proposed three CSR-extended format called CSR(r),CSR(r,l1,l2)and BCSR(r,l1,l2).The main work of this paper can be summarized as follows:(1)With the study of the existing optimization techniques,this paper focuses on the aspect of computer architecture,summaries and presents four kinds of optimization strategy.(2)In order to take full advantage of the SIMD(single instruction multiple data)acceleration technology in SpMV,we proposed two CSR-extended format called CSR(r)and CSR(r,l1,l2).Compared with the traditional CSR format,the CSR(r)and CSR(r,l1,l2)respectively gains 45% and 49% performance improvement.(3)Combined with the block structure,we proposed another CSR-extended format called BCSR(r,l1,l2).The performance of BCSR(r,l1,l2)increased 66% compared with the CSR format.(4)With the summary,this paper shows the optimization direction of this paper and presents the future work.