Compilation of Dynamic Sparse Tensor Algebra
summary
A compiler generates efficient tensor-algebra kernels from high-level node-schema language descriptions of recursive pointer-based layouts (block linked lists, BSTs, B-trees, C-trees, C3 hybrids). It emits iterator-based code, flattens recursion to a manual stack, and supports mixed static/dynamic tensors; insertion into pointer formats avoids rebuilding CSR and is orders of magnitude cheaper while page-rank on graphs up to ~255 million nonzeros runs on generated kernels that outperform PAM, Aspen, STINGER, Terrace and match or beat hand-tuned libraries.
AI-written summary · about
chapters (11)
- 0:00Start
- 0:11Sparse Data Values
- 1:33Ignoring Sparsity is Throwing away performance
- 4:17Sparse tensors can be compressed by adding metadata
- 8:49Many real-world applications work with dynamic sparse tensors
- 10:13Inserting a new value to an array-based structure CSR
- 11:30Pointer-based formats allow for efficient in-place modification
- 12:23Performance of array-based vs. pointer-based formats
- 13:16Computing with different formats can require very distinct code
- 16:17Pointer-based data structures can be precisely defined using node schema language
- 18:31Compiler can generate code to compute on pointer-based data structures directly from node schemas
related talks
20mCompiling Structured Tensor Algebra
28mFunctional Sparse Tensor Compilation
15mCompiling and Compressing Structured Tensors
19mCompiler Support for Sparse Tensor Convolutions
15mCompilation of Sparse Array Programming Models
14mCompressed and Parallelized Structured Tensor Algebra
19mOptimizations and abstractions for sparse machine learning
56mEfficient array (and data) processing by leveraging structure