REPTILE: Performant Tiling of Recurrences
summary
REPTILE is a compiler that tiles mathematical recurrences by decomposing programs into unique hierarchical tiles, simplifying each tile into its own recurrence, and lowering tiles either to generated C loops or to library-backed tiles via user-supplied mappings. The user supplies recurrences, tiling sizes, and a bank of decorated library kernels; intersection checks use SMT-style reasoning. Generated code matches or exceeds MKL (e.g., LU 0.79–1.27x, Cholesky 0.97–1.21x, trtri 1.61–2.72x) and speeds up bioinformatics recurrences like Needleman–Wunsch and Smith–Waterman. 0.79–2.72x speedup
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:46Matrix multiply vs solvers
- 3:52Library and compiler limits
- 4:56Reptile system
- 6:20Hierarchical tiling
- 7:24User inputs and workflow
- 8:26Tile discovery via intersection
- 11:55Algorithm intuition
- 12:17Evaluation vs MKL
- 13:24Non-solver recurrences
- 13:45Q&A
related talks
19mCompiling Recurrences over Dense and Sparse Arrays
22mTileLoom: Automatic Dataflow Planning for Tile-Based Languages on Spatial Dataflow Accel…
31mUniRec: A Unimodular-Like Framework for Nested Recursions and Loops
56mRhombus: The Non-shrubbery Parts (Keynote)
08mCompiling pattern matching to in-place modifications
01h 05mTiles, Bricks, and Layouts: How Aggregate Data Abstractions Aid in Optimizing Data(…)
11mEnabling Composition of Kernels and Compilers
19mMosaic: An Interoperable Compiler for Tensor Algebra