Extending the Scope of the Array Abstraction beyond Sparsity
summary
Argues that the array abstraction extends past simple sparsity by operating directly on compressed formats (run‑length and implicit-value encodings), exploiting symmetry to halve storage and compute, and using integer grids to pick arbitrary point sets from continuous domains. Shows a concrete compiler stack (Taco) that generates fused SDMM code that is orders of magnitude faster than composing library kernels, cites a ~65% sparsity break‑even for SpMV (much lower for MatMul), and points to practical gains for sparse neural nets if compilers and hardware follow.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 1:07Arrays power and foundation
- 2:54Dense arrays vs sparsity
- 4:41Sparsity computation challenges
- 6:49Beyond sparsity: structured patterns
- 8:36Exploiting symmetry in arrays
- 9:40Integer grids and continuous space
- 10:46Summary
related talks
15mCompilation of Sparse Array Programming Models
19mCompiling Recurrences over Dense and Sparse Arrays
18mCompilation of Shape Operators on Sparse Arrays
19mCompiler Support for Sparse Tensor Convolutions
25mFormat Abstraction for Sparse Tensor Algebra Compilers
20mA Mechanized Algebra of Verified Data Structures for Optimizing Sparse Tensor Programs
28mFunctional Sparse Tensor Compilation
20mVectorizing Sparse Coiteration for Two-finger Loop Structure (Extended Abstract)