SparseAuto: An Auto-Scheduler for Sparse Tensor Computations Using Recursive Loop Nest(…)
summary
SparseAuto is an auto-scheduler that applies recursive loop-nest fission/fusion to produce imperfectly nested code, uses a poset-based cost model combining symbolic time and auxiliary memory complexity, and invokes an SMT solver to prune schedules and approximate a Pareto frontier. The system generates code and, across eight real-world contractions, finds schedules in the top 5% and achieves orders-of-magnitude speedup over TACO (40–140× on extended kernels), while sometimes losing when cache effects, not modeled at compile time, dominate.
AI-written summary · about
chapters (18)
- 0:00SparseAuto introduction
- 0:22Scheduling sparse tensor challenges
- 1:44Splitting tensor contractions
- 2:47Schedule space pruning principles
- 3:50Recursive loop nest restructuring
- 5:15Compile-time complexity pruning
- 6:22Memory depth pruning stage
- 7:27Combined loop and memory pruning
- 8:53SMT solver for pruning
- 9:56Runtime complexity pruning
- 10:37Cache access complexity
- 11:19Performance vs autotuners
- 12:44Auxiliary memory impact
- 13:51Top schedules in space
- 14:35Summary and future directions
- 15:43Q&A: CPU parameterization
- 16:46Q&A: Tiling and strip mining
- 17:51Q&A: Sparsity patterns handling
related talks
17mA Sparse Iteration Space Transformation Framework for Sparse Tensor Algebra
19mSparsity-Aware Autoscheduling for Numpy with Finch and Galley
28mFunctional Sparse Tensor Compilation
15mCompilation of Sparse Array Programming Models
32mCompilation of Dynamic Sparse Tensor Algebra
15mEfficient Automatic Scheduling of Imaging & Vision Pipelines for the GPU
15mEffectively Scheduling Computational Graphs of Deep Neural Networks toward Their...
17mSparseZETA: Intelligent Auto-tuner for Designing High-Performance SpMV Programs