Compiling Recurrences over Dense and Sparse Arrays
summary
A compiler framework that takes recurrence equations, data-format declarations, and schedule commands and emits native C for dense and sparse arrays by lowering through dependency analysis and a loop-based IR. It uses automatic dependency bootstrapping (induction-style assumptions over loop indices) to place mutually recursive or in-place recurrences, detects and reports impossible loop orderings, and fuses equations automatically. Generated code targets CSR/CSC and dense formats, matches hand-tuned libraries (roughly 0.8–1.2× with examples) and shows up to ~2× improvement from fusion; artifacts and reproduction materials are available.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 0:21Recurrence and applications
- 1:44Dense vs sparse recurrences
- 3:52Optimizing recurrences
- 4:33Recurrence system
- 5:16Recurrence language
- 7:02Loop orderings
- 9:07Code generation
- 11:14Assumptions and validation
- 12:17Lowering to C
- 12:38Automatic fusion
- 13:00Performance vs libraries
- 13:42Summary
- 14:50Q&A
related talks
15mCompilation of Sparse Array Programming Models
11mExtending the Scope of the Array Abstraction beyond Sparsity
30mGenerating High Performance Code for Irregular Data Structures using Dependent Types
20mExploiting Sparsity and Redundancy
20mCompiling Control Flow in Sparse and Structured Array Programs
24mMapping Sparse Applications to Accelerated Computing Systems
20mVectorizing Sparse Coiteration for Two-finger Loop Structure (Extended Abstract)
28mFunctional Sparse Tensor Compilation