Cache Blocking of Distributed-Memory Parallel Matrix Power Kernels

Abstract

Sparse matrix-vector products (SpMVs) are a bottleneck in many scientific codes. Due to the heavy strain on the main memory interface from loading the sparse matrix and the possibly irregular memory access pattern, SpMV typically exhibits low arithmetic intensity. Repeating these products multiple times with the same matrix is required in many algorithms. This so-called matrix power kernel (MPK) provides an opportunity for data reuse since the same matrix data is loaded from main memory multiple times, an opportunity that has only recently been exploited successfully with the Recursive Algebraic Coloring Engine (RACE). Using RACE, one considers a graph based formulation of the SpMV and employs s level-based implementation of SpMV for reuse of relevant matrix data. However, the underlying data dependencies have restricted the use of this concept to shared memory parallelization and thus to single compute nodes. Enabling cache blocking for distributed-memory parallelization of MPK is challenging due to the need for explicit communication and synchronization of data in neighboring levels. In this work, we propose and implement a flexible method that interleaves the cache-blocking capabilities of RACE with an MPI communication scheme that fulfills all data dependencies among processes. Compared to a "traditional" distributed memory parallel MPK, our new Distributed Level-Blocked MPK yields substantial speed-ups on modern Intel and AMD architectures across a wide range of sparse matrices from various scientific applications. Finally, we address a modern quantum physics problem to demonstrate the applicability of our method, achieving a speed-up of up to 4x on 832 cores of an Intel Sapphire Rapids cluster.

15 pages, 12 figures, 5 tables; added affiliation & extended acknowledgment

References in corpus (10)

• LIKWID: Lightweight Performance Tools
• 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
• Numerical approaches to time evolution of complex quantum systems
• Quantum boomeranglike effect of wave packets in random media
• Understanding HPC Benchmark Performance on Intel Broadwell and Cascade Lake Processors
• Quantum boomerang effect for interacting particles
• Quantum boomerang effect in systems without time reversal symmetry
• Level-based Blocking for Sparse Matrices: Sparse Matrix-Power-Vector Multiplication
• Algebraic Temporal Blocking for Sparse Iterative Solvers on Multi-Core CPUs