Sparsity-Aware Autoscheduling for Numpy with Finch and Galley
summary
Galley implements an autoscheduler for the Finch sparse tensor compiler that makes concrete decisions: it uses database-style cardinality estimation (notably degree sequence bounds) to cost fusion at a logical layer and loop order, format and intersection strategy at a physical layer. It supports four level formats (bitmap, dense, hash, sorted) and an iterate-lookup intersection choice. Evaluated on subgraph counting and matrix‑chain examples, Galley+Finch matches or beats DuckDB-style optimizers and outperforms PyTorch on sparse outputs.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 1:04Sparse tensor challenges
- 2:52Scheduling interface limits
- 5:04Sparsity pattern impact
- 6:31Cost modeling for sparse ops
- 8:17Cardinality estimation
- 9:41Sparsity in optimizer
- 10:45Finch and Galley overview
- 11:07Logical optimizer
- 13:36Physical optimizer
- 14:38Sparse format algorithms
- 15:41Subgraph counting results
- 17:08PyTorch sparse multiply comparison
- 18:13Conclusion
related talks
15mFinch: Sparse and Structured Tensor Programming with Control Flow
20mSparseAuto: An Auto-Scheduler for Sparse Tensor Computations Using Recursive Loop Nest(…)
15mEffectively Scheduling Computational Graphs of Deep Neural Networks toward Their...
28mFunctional Sparse Tensor Compilation
15mGALA: A High Performance Graph Neural Network Acceleration LAnguage and Compiler
17mZEN: Empowering Distributed Training with Sparsity-driven Data Synchronization
25mScale Smarter, Not Harder, with cuPyNumeric.
15mCompilation of Sparse Array Programming Models