Autoscheduling for Sparse Tensor Algebra with an Asymptotic Cost Model
summary
The paper builds an autoscheduler that models sparse tensor runtimes as sets of iteration tasks and picks schedules by comparing those sets, using asymptotic cost model reasoning and database-style set-containment filtering. Implementation is in Julia using SymbolicUtils to manipulate symbolic iteration sets. Filtering shrinks the schedule frontier by over 100× and the model flags schedule choices that yield up to 1300× speedups on sparse kernels; it runs offline (no input-data profiling) and targets scalar serial code, not ISA-specific vectorization.
AI-written summary · about
chapters (6)
- 0:00Start
- 4:22Sparse Asymptotic Tradeoffs
- 7:05Model program runtime symbolically
- 10:23Sparse-Sparse Matrix Multiply
- 12:03Conclusion
- 16:31Sparse Tensor Kernels are Usually Small
related talks
20mSparseAuto: An Auto-Scheduler for Sparse Tensor Computations Using Recursive Loop Nest(…)
19mSparsity-Aware Autoscheduling for Numpy with Finch and Galley
24mVerified Tensor-Program Optimization Via High-Level Scheduling Rewrites
20mCompiling Structured Tensor Algebra
15mEfficient Automatic Scheduling of Imaging & Vision Pipelines for the GPU
19mCompiler Support for Sparse Tensor Convolutions
17mA Sparse Iteration Space Transformation Framework for Sparse Tensor Algebra
28mFunctional Sparse Tensor Compilation