UniRec: A Unimodular-Like Framework for Nested Recursions and Loops
summary
Claim: UniRec generalizes unimodular loop transforms to mixed recursion+loop code and actually implements arbitrary unimodular linear schedules for recursive iteration spaces. It builds a finite representation using multi‑tape automata, encodes subtraction with a Brahmagupta style debt/fortune pair trick, composes scheduling rewrites as transducers and fixes naming/order problems with a canonicalization transducer. The system includes dependence tests, runs on tree and hybrid benchmarks, and yields correct, sometimes substantially faster parallel schedules subject to the paper’s safety restrictions.
AI-written summary · about
chapters (26)
- 0:00Intro
- 0:43loops and recursion
- 4:00interchange
- 4:45reversal
- 5:25loops xforms = recursive xforms
- 6:09need for composition
- 6:36compositional frameworks
- 8:16gameplan
- 8:40representing iteration spaces
- 11:34multitape automata
- 12:10representing transformations
- 14:18transformation transducers
- 15:12skewing
- 16:08unimodular framework
- 16:42positive skew
- 17:21negative skew
- 18:11negative numbers
- 19:17control word pairs
- 19:54using pairs in automata
- 20:46transducers can subtract
- 21:41problem!
- 23:02canonical control word
- 23:38canonicalization
- 24:19more details in paper
- 24:50what does this buy us?
- 25:18unirec
related talks
25mRecursive Program Synthesis using Paramorphisms
56mAn introduction to recursion schemes
27mTail Recursion Modulo Context: An Equational Approach
23mDeep Fusion for Efficient Nested Recursive Computations
16mBeyond Relooper: Recursive Translation of Unstructured Control Flow to Structu…
19mCompiling Recurrences over Dense and Sparse Arrays
19mMutually Iso-Recursive Subtyping
15mProducts of Recursive Programs for Hypersafety Verification