Compilation of Shape Operators on Sparse Arrays
summary
A compiler called burrito extends the taco compiler to emit specialized C++ iterators that traverse reshaped sparse formats without materializing temporaries, representing shape ops as IR primitives like product (concatenation), split (unflatten), and slice and compiling them with the classical iterator model. Generated kernels beat hand kernels by 1.66×–15.3× vs scipy.sparse (and 1.67×–651× vs pydata/sparse), avoid costly conversions (7.29×–13.0× and 21.3×–511×), and show fusion gains of 1.22×–2.23× while producing complex but correct control flow; artifacts and reproducible results are available.
AI-written summary · about
chapters (9)
- 0:00Shape operators in sparse arrays
- 1:48Why shape operators matter
- 3:30Challenges across data structures
- 5:14Performance benefits
- 6:58Operator fusion
- 8:23Taco compiler iteration space
- 10:30Shape operators transforming spaces
- 11:53Iterator model
- 13:19Final thoughts
related talks
15mCompilation of Sparse Array Programming Models
25mFormat Abstraction for Sparse Tensor Algebra Compilers
17mA Sparse Iteration Space Transformation Framework for Sparse Tensor Algebra
28mFunctional Sparse Tensor Compilation
11mExtending the Scope of the Array Abstraction beyond Sparsity
20mVectorizing Sparse Coiteration for Two-finger Loop Structure (Extended Abstract)
24mMapping Sparse Applications to Accelerated Computing Systems
18mLoop Fusion in Matrix Multiplications with Sparse Dependence