Functional Sparse Tensor Compilation
summary
A modular compiler named STAR lowers tensor algebra to a functional pipeline (HC → SDQL → LQL → C++) and separates scheduling from data-format decisions so sparse outputs are correct without user hacks. It implements hinted dictionaries and intermediate workspace reasoning, emits C++ for SpMM and TTM, and on real NIPS datasets matches or beats Taco once hints and workspaces are applied; unsorted maps are orders of magnitude slower. Forward-mode AD is supported; reverse mode is future work.
AI-written summary · about
chapters (24)
- 0:00Introduction
- 0:23Sparse tensor computation overview
- 1:28Dense tensor limits for sparse data
- 2:11Sparse tensor formats
- 3:17Sparse algorithm complexity
- 4:23Sparse tensor compilers role
- 5:31Tree representation for sparse tensors
- 6:13Loop reordering for sparse
- 7:16Sparse output handling
- 8:22Existing compiler limits
- 9:25Modular compiler architecture
- 10:09Compiler input and ordering
- 10:50Tensor lowering to HSeen IR
- 11:56SDQL as functional IR
- 13:01Dictionaries for sparse outputs
- 13:44HC lowering to SDQL
- 14:47LQL as low-level IR
- 16:11Optimizing sorted dictionaries
- 16:55Hinted dictionaries for lookups
- 18:21Workspace reasoning for updates
- 19:06Sparse matrix multiplication eval
- 20:35Performance vs Taco
- 20:57Conclusion and future
- 21:37Q&A
related talks
20mCompiling Structured Tensor Algebra
32mCompilation of Dynamic Sparse Tensor Algebra
15mCompiling and Compressing Structured Tensors
20mA Mechanized Algebra of Verified Data Structures for Optimizing Sparse Tensor Programs
19mCompiler Support for Sparse Tensor Convolutions
15mCompilation of Sparse Array Programming Models
20mExploiting Sparsity and Redundancy
25mFormat Abstraction for Sparse Tensor Algebra Compilers