An efficient SIMD compression format for sparse matrix‐vector multiplication. (29th June 2018)

• Record Type: Journal Article
• Authors: Chen, Xinhai; Xie, Peizhen; Chi, Lihua; Liu, Jie; Gong, Chunye
• Other Names: Barbosa Jorge G. guestEditor.; Jeannot Emmanuel guestEditor.; Li Maozhen guestEditor.
• Is Part Of: Concurrency and computation. Volume 30:Number 23(2018)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2018-06-29
• Subjects: compressed sparse row format (CSR) -- performance optimization -- single instruction multiple data (SIMD) -- sparse matrix‐vector multiplication (SpMV); Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.4800
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: Sparse matrix‐vector multiplication (SpMV) is an essential kernel in sparse linear algebra and has been studied extensively on all modern processor and accelerator architectures. Compressed Sparse Row (CSR) is a frequently used format for sparse matrices storage. However, CSR‐based SpMV has poor performance on processors with vector units. In order to take full advantage of SIMD acceleration technology in SpMV, we proposed a new matrix storage format called CSR‐SIMD. The new storage format compresses the non‐zero elements into many variable‐length data fragments with consecutive memory access addresses. Thus, the data locality of sparse matrix A and dense vector x expands and the floating‐point operations for each fragment can be completely calculated by vectorized implementation on wide SIMD units. Our experimental results indicate that CSR‐SIMD has better storage efficiency and low‐overhead for format conversion. Besides, the new format achieves high scalability on wide SIMD units. In comparison with the CSR‐based and BCSR‐based SpMV, CSR‐SIMD obtains better performance on FT1500A, Intel Xeon, and Intel Xeon Phi.