A unified sparse matrix data format for efficient general sparse matrix-vector multiply on modern processors with wide SIMD units

Abstract

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-sigma, a variant of Sliced ELLPACK, as a SIMD-friendly data format which combines long-standing ideas from General Purpose Graphics Processing Units (GPGPUs) and vector computer programming. We discuss the advantages of SELL-C-sigma compared to established formats like Compressed Row Storage (CRS) 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-sigma spMVM kernel. SELL-C-sigma 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.

23 pages, 7 figures, 6 listings

Cited by in corpus (24)

• A Recursive Algebraic Coloring Technique for Hardware-Efficient Symmetric Sparse Matrix-Vector Multiplication
• Performance Analysis and Optimization of Sparse Matrix-Vector Multiplication on Modern Multi- and Many-Core Processors
• ECM modeling and performance tuning of SpMV and Lattice QCD on A64FX
• GHOST: Building blocks for high performance sparse linear algebra on heterogeneous systems
• Performance Modeling of Streaming Kernels and Sparse Matrix-Vector Multiplication on A64FX
• An Approach for Accelerating Incompressible Turbulent Flow Simulations Based on Simultaneous Modelling of Multiple Ensembles
• Performance Engineering of the Kernel Polynomial Method on Large-Scale CPU-GPU Systems
• Pipelined Iterative Solvers with Kernel Fusion for Graphics Processing Units
• Copernicus: Characterizing the Performance Implications of Compression Formats Used in Sparse Workloads
• Level-based Blocking for Sparse Matrices: Sparse Matrix-Power-Vector Multiplication
• Chebyshev Filter Diagonalization on Modern Manycore Processors and GPGPUs
• The Role of Idle Waves, Desynchronization, and Bottleneck Evasion in the Performance of Parallel Programs
• Characterizing Scalability of Sparse Matrix-Vector Multiplications on Phytium FT-2000+ Many-cores
• Evaluating the Performance of NVIDIA's A100 Ampere GPU for Sparse Linear Algebra Computations
• Accelerating the SpMV kernel on standard CPUs by exploiting the partially diagonal structures
• Algebraic Temporal Blocking for Sparse Iterative Solvers on Multi-Core CPUs
• CB-SpMV:A Data Aggregating and Balance Algorithm for Cache-Friendly Block-Based SpMV on GPUs
• Orthogonal layers of parallelism in large-scale eigenvalue computations
• Benefits from using mixed precision computations in the ELPA-AEO and ESSEX-II eigensolver projects
• Hierarchical Block Multi-Color Ordering: A New Parallel Ordering Method for Vectorization and Parallelization of the Sparse Triangular Solver in the ICCG Method
• Accelerating Radiation Therapy Dose Calculation with Nvidia GPUs
• Cache Blocking of Distributed-Memory Parallel Matrix Power Kernels
• SlimSell: A Vectorizable Graph Representation for Breadth-First Search
• Computing the sparse matrix vector product using block-based kernels without zero padding on processors with AVX-512 instructions