Community-based Matrix Reordering for Sparse Linear Algebra Optimization
Authors:
- 1 April 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 214-223
Abstract
Sparse linear algebra kernels achieve sub-optimal performance due to their poor cache locality. Matrix reordering is an effective pre-processing optimization that improves cache locality and performance of these kernels. While many reordering techniques have been proposed, most prior work on matrix reordering suffer from two key limitations: (1) they evaluate their reordering proposal on a small set of arbitrarily-selected inputs and (2) they do not quantify the additional headroom for improvement after reordering is applied. To address these two limitations, we perform a detailed characterization of reordering techniques across a broad set of 50 input matrices where we quantify the ability of matrix reordering techniques to bring sparse linear algebra kernels close to hardware limits. Our analysis reveals that community-based matrix reordering is most effective at optimizing the execution of sparse linear algebra kernels, bringing the cuSPARSE SpMV kernel to within 54% of ideal run time on an NVIDIA A6000 GPU on average. However, community-based reordering is not uniformly effective across all 50 input matrices. We investigate the reasons when community-based reordering falls short and propose an enhanced version of community-based reordering that provides up to 1.57× additional performance improvements for the SpMV kernel.Keywords
This publication has 38 references indexed in Scilit:
- GraphMatProceedings of the VLDB Endowment, 2015
- SlashBurn: Graph Compression and Mining beyond Caveman CommunitiesIEEE Transactions on Knowledge and Data Engineering, 2014
- X-Stream2013
- Multi-threaded Graph Partitioning2013
- Direction-Optimizing Breadth-First SearchScientific Programming, 2013
- Scale-Free Networks: A Decade and BeyondScience, 2009
- RooflineCommunications of the ACM, 2009
- Community structure in social and biological networksProceedings of the National Academy of Sciences of the United States of America, 2002
- Efficient Behavior of Small-World NetworksPhysical Review Letters, 2001
- Evaluating associativity in CPU cachesIEEE Transactions on Computers, 1989