Level-Based Blocking for Sparse Matrices: Sparse Matrix-Power-Vector Multiplication
Open Access
- 21 November 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 34 (2), 581-597
- https://doi.org/10.1109/tpds.2022.3223512
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× and 5× compared to an optimal SpMV-based baseline on a single multicore chip of recent Intel and AMD architectures. Various numerical schemes like $s$ -step Krylov solvers, polynomial preconditioners and power clustering algorithms will benefit from our development.
Keywords
Funding Information
- NHR@FAU
- State of Bavaria
- German Federal Ministry of Education and Research
This publication has 36 references indexed in Scilit:
- A Unified Sparse Matrix Data Format for Efficient General Sparse Matrix-Vector Multiplication on Modern Processors with Wide SIMD UnitsSIAM Journal on Scientific Computing, 2014
- An Accurate Polynomial Approximation of Exponential IntegratorsJournal of Scientific Computing, 2013
- Auto-tuning the Matrix Powers Kernel with SEJITSLecture Notes in Computer Science, 2013
- Numerical approaches to time evolution of complex quantum systemsPhysics Letters A, 2009
- Optimization and Performance Modeling of Stencil Computations on Modern MicroprocessorsSIAM Review, 2009
- When cache blocking of sparse matrix vector multiply works and whyApplicable Algebra in Engineering, Communication and Computing, 2007
- The memory behavior of cache oblivious stencil computationsThe Journal of Supercomputing, 2007
- Effects of Ordering Strategies and Programming Paradigms on Sparse Matrix ComputationsSIAM Review, 2002
- Rescheduling for Locality in Sparse Matrix ComputationsLecture Notes in Computer Science, 2001
- s-step iterative methods for symmetric linear systemsJournal of Computational and Applied Mathematics, 1989