Loop Fusion in Matrix Multiplications with Sparse Dependence
summary
A compiler pass called tile fusion fuses tiles of two consecutive matrix multiplications when sparsity creates partial dependences, implemented as a Python/Numba prototype that generates a runtime dependence DAG, builds a fusion schedule, and emits fused loop variants guarded by cheap runtime checks. Results show geometric-mean speedups of 2.33× over PyG for GCN training and 1.32× over MKL for sparse linear solves, demonstrating practical end-to-end gains.
AI-written summary · about
chapters (15)
- 0:00Loop fusion in matrix multiplications
- 1:47Fusion benefits for locality
- 3:13Dense dependence challenges
- 5:20Sparse dependence enables partial fusion
- 6:49Feasibility of sparse fusion
- 7:32Tile Fusion system overview
- 9:19Compile-time dependence analysis
- 11:01Runtime DAG generation
- 12:26Fused code variants
- 13:33GCN training performance
- 14:39Sparse optimization research
- 15:43Lossless compression pipeline
- 16:24Lossy compression benefits
- 16:45Sparse matrix multiplication on GPUs
- 17:28Q&A
related talks
20mVectorizing Sparse Coiteration for Two-finger Loop Structure (Extended Abstract)
23mDeep Fusion for Efficient Nested Recursive Computations
19mCompiler Support for Sparse Tensor Convolutions
20mExploiting Sparsity and Redundancy
19mCompiling Recurrences over Dense and Sparse Arrays
17mA Sparse Iteration Space Transformation Framework for Sparse Tensor Algebra
18mCompiling Strassen-like Matrix Multiplication Algorithms to Fast CUDA Kernels
18mCompilation of Shape Operators on Sparse Arrays