Finch: Sparse and Structured Tensor Programming with Control Flow
summary
Finch is a new language and compiler that combines flexible control flow with a parameterized format DSL to generate code that iterates only over nonzeros and automatically specializes control flow to data. It implements freeze/thaw and looplet lowering to transition tensors between readable/writable modes, emits code for formats like compressed sparse column (val/idx/ptr), and encodes short‑circuiting and fused push/pull BFS traversals. Papers and artifacts report dramatic speedups on SpMV/SpGEMM, image processing, and graph analytics and reproducible results.
AI-written summary · about
chapters (8)
- 0:00Array programming limits
- 3:31Sparse tensor challenges
- 6:23Finch control flow
- 8:28Finch structure language
- 9:31Control flow and data structures
- 10:12Case study: Breath-first search in Finch
- 12:40Finch performance
- 14:23Q&A
related talks
20mCompiling Control Flow in Sparse and Structured Array Programs
19mSparsity-Aware Autoscheduling for Numpy with Finch and Galley
28mFunctional Sparse Tensor Compilation
23mDeep Fusion for Efficient Nested Recursive Computations
19mCompiler Support for Sparse Tensor Convolutions
14mAchieving High-Performance the Functional Way - A Functional Pearl on Expressing High...
20mVectorizing Sparse Coiteration for Two-finger Loop Structure (Extended Abstract)
24mVerified Tensor-Program Optimization Via High-Level Scheduling Rewrites