Compilation of Sparse Array Programming Models
summary
A compiler built on TACO generates C-like code from array index notation and a format language that supports arbitrary fill values, lifts operators into an explicit set algebra and emits iteration lattices that include a new set complement to omit computation for nonstandard sparsity patterns. It handles user-defined functions, array slicing, and fused ufuncs; on benchmarks it reports 3×–20× speedups for ufuncs, 10×–50× for fused calls, 1.4×–53.7× vs PyData/Sparse overall, and competitive 0.56×–3.50× results vs SuiteSparse:GraphBLAS.
AI-written summary · about
chapters (19)
- 0:00Importance of NumPy and array programming
- 0:38NumPy is not enough
- 1:06Sparse Tensor Algebra allows for sparsity
- 1:52Sparse Tensor Algebra is also not enough
- 2:52We propose Sparse Array Programming
- 4:20Sparse Array Programming generalizes many programming models
- 4:56System Overview
- 5:56GCD Example
- 6:47User-Defined Functions
- 7:40Sparse arrays as iteration spaces
- 8:33Lifting iteration space from operators
- 8:52Generating code from iteration algebra
- 9:52Full representation and code for addition
- 10:05Iteration space complements for XOR
- 10:38Ability to describe any sparse iteration space
- 11:47Evaluation - Universal Functions (Ufuncs)
- 13:12Evaluation - Graph Linear Algebra
- 13:45Evaluation - Medical Imaging
- 14:35Conclusion and Future Directions
related talks
11mExtending the Scope of the Array Abstraction beyond Sparsity
18mCompilation of Shape Operators on Sparse Arrays
17mA Sparse Iteration Space Transformation Framework for Sparse Tensor Algebra
19mCompiling Recurrences over Dense and Sparse Arrays
19mCompiler Support for Sparse Tensor Convolutions
28mFunctional Sparse Tensor Compilation
20mCompiling Structured Tensor Algebra
32mCompilation of Dynamic Sparse Tensor Algebra