Level-based Blocking for Sparse Matrices: Sparse Matrix-Power-Vector Multiplication

Abstract

The multiplication of a sparse matrix with a dense vector (SpMV) is a key component in many numerical schemes and its performance is known to be severely limited by main memory access. Several numerical schemes require the multiplication of a sparse matrix polynomial with a dense vector, which is typically implemented as a sequence of SpMVs. This results in low performance and ignores the potential to increase the arithmetic intensity by reusing the matrix data from cache. In this work we use the recursive algebraic coloring engine (RACE) to enable blocking of sparse matrix data across the polynomial computations. In the graph representing the sparse matrix we form levels using a breadth-first search. Locality relations of these levels are then used to improve spatial and temporal locality when accessing the matrix data and to implement an efficient multithreaded parallelization. Our approach is independent of the matrix structure and avoids shortcomings of existing "blocking" strategies in terms of hardware efficiency and parallelization overhead. We quantify the quality of our implementation using performance modelling and demonstrate speedups of up to 3$\times$ and 5$\times$ compared to an optimal SpMV-based baseline on a single multicore chip of recent Intel and AMD architectures. As a potential application, we demonstrate the benefit of our implementation for a Chebyshev time propagation scheme, representing the class of polynomial approximations to exponential integrators. Further numerical schemes which may benefit from our developments include $s$-step Krylov solvers and power clustering algorithms.

arXiv comment18 pages, 19 figures, 3 tables

References in corpus (7)

• The electronic properties of graphene
• A unified sparse matrix data format for efficient general sparse matrix-vector multiply on modern processors with wide SIMD units
• A Recursive Algebraic Coloring Technique for Hardware-Efficient Symmetric Sparse Matrix-Vector Multiplication
• Multicore-optimized wavefront diamond blocking for optimizing stencil updates
• Numerical approaches to time evolution of complex quantum systems
• Understanding HPC Benchmark Performance on Intel Broadwell and Cascade Lake Processors
• Validation of hardware events for successful performance pattern identification in High Performance Computing

Cited by in corpus (4)

• Occamy: A 432-Core Dual-Chiplet Dual-HBM2E 768-DP-GFLOP/s RISC-V System for 8-to-64-bit Dense and Sparse Computing in 12nm FinFET
• Algebraic Temporal Blocking for Sparse Iterative Solvers on Multi-Core CPUs
• Orthogonal layers of parallelism in large-scale eigenvalue computations
• Cache Blocking of Distributed-Memory Parallel Matrix Power Kernels