Compiling Control Flow in Sparse and Structured Array Programs
summary
Finch is a new language and compiler that merges control flow and data-format descriptions so the compiler specializes loops, ifs, breaks, masks and temporaries to structure like sparsity, sparse RLE, blocks, intervals or permutations via a hierarchical looplet IR. Implementations include BFS expressed as sparse frontier vectors that match hand-tuned GraphBLAS/Tim Davis kernels, SpMV/SpGEMM and image erosion that outperform baselines (examples show 2x and 6x speed or memory‑read reductions and large n‑factor gains for symmetric MTTKRP), and RLE beating bitpacked on compressible images.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:27Sparse array interfaces matter
- 3:52BFS in sparse compilers
- 7:20Structure beyond sparsity
- 10:56Eight-level formats for tensors
- 13:04Programming structured sparse formats
- 14:28Sparse matrix-vector multiplication
- 15:51Multi-dimensional tensor operations
- 16:54Image morphology with sparse
- 18:17Conclusion
- 19:22Q&A
related talks
15mFinch: Sparse and Structured Tensor Programming with Control Flow
19mCompiling Recurrences over Dense and Sparse Arrays
15mCompilation of Sparse Array Programming Models
20mVectorizing Sparse Coiteration for Two-finger Loop Structure (Extended Abstract)
23mDeep Fusion for Efficient Nested Recursive Computations
19mCompiler Support for Sparse Tensor Convolutions
21mFlow-Analysis-Based Closure Optimization
01h 05mControl Flow Obfuscation for Featherweight Java + Efficient Fair Conjunction