Sparse matrix storage method CSRL (Compressed Sparse Row with Local Information) and SpMV (Sparse Matrix Vector Multiplication) realization method based on same

Abstract

The invention discloses a sparse matrix storage method CSRL (Compressed Sparse Row with Local Information) and an SpMV (Sparse Matrix Vector Multiplication) realization method based on the same. The storage method comprises the following steps of scanning a sparse matrix A in rows and storing each non-zero element value information in an array val sequence; defining a plurality of non-zero elements with continuous row subscripts as a continuous non-zero element section, recording a row subscript of a first element in each continuous non-zero element section by use of an array jas, and recording the number of non-zero elements in each continuous non-zero element section by use of an array jan; and recording an initial index of a first continuous non-zero element section in each row of the sparse matrix A by use of an array ptr. According to the data storage method, row indexes of the non-zero elements are combined and stored, so that the storage space requirement is reduced, the data locality of the sparse matrix is fully excavated, access and calculation can be performed by use of an SIMD (Single Instruction Multiple Data) instruction, the access frequency of an internal storage can be reduced, and the SpMV performance is improved.

Description

technical field [0001] The invention relates to a data storage method CSRL (compressed sparse row with local information) for a sparse matrix and a SpMV implementation method based on the method, which belongs to the technical field of high-performance numerical calculation and is mainly used in meteorology, turbulence simulation, and astrophysics , reservoir simulation and other scientific calculations and practical applications. Background technique [0002] Sparse matrix-vector multiplication (SpMV) y=A*x is a very important calculation kernel in iterative solvers, and iterative methods are widely used in scientific calculations such as meteorology, turbulence simulation, astrophysics, and reservoir simulation. and practical applications. But on the current computing platform based on memory hierarchy, the sparse matrix-vector multiplication performance of traditional CSR storage is very poor, and the operating efficiency is often lower than 10% of the peak value of hard...

AI Technical Summary

Problems solved by technology

[0013] The technical problem solved by the present invention is: to overcome the shortage that the sparse storage method in the prior art does not contain a lot of key local information and cannot be directly vectorized, and to provide a sparse matrix storage method CSRL and a SpMV implementation method based on the method. The column indexes of non-zero elements are merged and stored, which reduces the storage space requirement; reduces the number of memory accesses, and improves the performance of sparse matrix vector multiplication SpMV

Images