2013/07/31 by Moritz Kreutzer, Georg Hager, Gerhard Wellein +3 · 2 citations
Computer Science · Mathematics · #Arithmetic #Combinatorics #Computer science #Embedded Systems Design Techniques #Interconnection Networks and Systems #Mathematics #Matrix (chemical analysis) #Matrix multiplication #Multiplication (music) #Parallel Computing and Optimization Techniques #Parallel computing #Physics #SIMD #Sparse matrix #Vectorization (mathematics) #cs.DC #cs.MS
paper · pdf · doi:10.1137/130930352
published as SIAM Journal on Scientific Computing 2014 36:5, C401-C423 · 23 pages, 7 figures, 6 listings
openalex publication_date 2014/01/01 · arxiv created 2014/03/05 · arxiv updated 2014/10/21 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
Sparse matrix-vector multiplication (spMVM) is the most time-consuming kernel in many numerical algorithms and has been studied extensively on all modern processor and accelerator architectures. However, the optimal sparse matrix data storage format is highly hardware-specific, which could become an obstacle when using heterogeneous systems. Also, it is as yet unclear how the wide single instruction multiple data (SIMD) units in current multi- and many-core processors should be used most efficiently if there is no structure in the sparsity pattern of the matrix. We suggest SELL-C-σ, a variant of Sliced ELLPACK, as a SIMD-friendly data format which combines long-standing ideas from general-purpose graphics processing units and vector computer programming. We discuss the advantages of SELL-C-σ compared to established formats like Compressed Row Storage and ELLPACK and show its suitability on a variety of hardware platforms (Intel Sandy Bridge, Intel Xeon Phi, and Nvidia Tesla K20) for a wide range of test matrices from different application areas. Using appropriate performance models we develop deep insight into the data transfer properties of the SELL-C-σ spMVM kernel. SELL-C-σ comes with two tuning parameters whose performance impact across the range of test matrices is studied and for which reasonable choices are proposed. This leads to a hardware-independent (``catch-all'') sparse matrix format, which achieves very high efficiency for all test matrices across all hardware platforms.