A Recursive Algebraic Coloring Technique for Hardware-Efficient Symmetric Sparse Matrix-Vector Multiplication

Abstract

The symmetric sparse matrix-vector multiplication (SymmSpMV) is an important building block for many numerical linear algebra kernel operations or graph traversal applications. Parallelizing SymmSpMV on today's multicore platforms with up to 100 cores is difficult due to the need to manage conflicting updates on the result vector. Coloring approaches can be used to solve this problem without data duplication, but existing coloring algorithms do not take load balancing and deep memory hierarchies into account, hampering scalability and full-chip performance. In this work, we propose the recursive algebraic coloring engine (RACE), a novel coloring algorithm and open-source library implementation, which eliminates the shortcomings of previous coloring methods in terms of hardware efficiency and parallelization overhead. We describe the level construction, distance-k coloring, and load balancing steps in RACE, use it to parallelize SymmSpMV, and compare its performance on 31 sparse matrices with other state-of-the-art coloring techniques and Intel MKL on two modern multicore processors. RACE outperforms all other approaches substantially and behaves in accordance with the Roofline model. Outliers are discussed and analyzed in detail. While we focus on SymmSpMV in this paper, our algorithm and software is applicable to any sparse matrix operation with data dependencies that can be resolved by distance-k coloring.

arXiv comment40 pages, 23 figures

References in corpus (4)

• LIKWID: Lightweight Performance Tools
• A unified sparse matrix data format for efficient general sparse matrix-vector multiply on modern processors with wide SIMD units
• Speculative Segmented Sum for Sparse Matrix-Vector Multiplication on Heterogeneous Processors
• Chebyshev Filter Diagonalization on Modern Manycore Processors and GPGPUs

Cited by in corpus (16)

• Arbitrary-order pressure-robust DDR and VEM methods for the Stokes problem on polyhedral meshes
• Differentiable solver for time-dependent deformation problems with contact
• Understanding HPC Benchmark Performance on Intel Broadwell and Cascade Lake Processors
• Level-based Blocking for Sparse Matrices: Sparse Matrix-Power-Vector Multiplication
• Fluidic Topology Optimization with an Anisotropic Mixture Model
• High-Order Incremental Potential Contact for Elastodynamic Simulation on Curved Meshes
• A micropolar isotropic plasticity formulation for non-associated flow rule and softening featuring multiple classical yield criteria Part I -- Theory
• Virtual elements for Maxwell's equations
• A Robust and Accurate Adaptive Approximation Method for a Diffuse-Interface Model of Binary-Fluid Flows
• Optimized shock-protecting microstructures
• A Coupled Hybridizable Discontinuous Galerkin and Boundary Integral Method for Analyzing Electromagnetic Scattering
• Algebraic Temporal Blocking for Sparse Iterative Solvers on Multi-Core CPUs
• Geometric Contact Potential
• Cut-Cell Microstructures for Two-scale Structural Optimization
• High-Order Continuous Geometrical Validity
• Cache Blocking of Distributed-Memory Parallel Matrix Power Kernels