Warping Cache Simulation of Polyhedral Programs
summary
A simulation system builds a Presburger polyhedral trace of looped, input‑independent programs, runs a plug‑in cache simulator and a warp component that detects bijection‑based repeating cache states and jumps whole iteration ranges. Implemented and evaluated on PolyBench, it reports up to 10,000x speedup on stencil kernels and similar gains across several real replacement policies, while admitting worst‑case parity with trace simulation and occasional slowdowns (roughly 10–20x) when matching states are rare.
AI-written summary · about
chapters (12)
- 0:00Caches appear to be important
- 0:34Cache behavior is non-obvious Example: Matrix multiplication
- 1:27Techniques for cache analysis
- 4:282. Analytical cache models: State of the art
- 5:10Real-world cache configurations
- 5:44Our goal: "Best of both worlds"
- 6:19Our approach in a nutshell
- 7:21Example: 1D stencil computation
- 10:37Key property: Data independence
- 12:34Experimental evaluation
- 15:54Example revisited
- 18:18Performance: Speedup due to warping
related talks
15mCopy-and-Patch Compilation
15mAutomatically Reasoning About How Systems Code Uses the CPU Cache
26mNon-Interference Preserving and Optimising Compilation with Hyperproperty Simulations
14mCollapsing Towers for Side-Channel Security
17mFuzzing Loop Optimizations in Compilers for C++ and Data-Parallel Languages
01h 02mMemory and Compilers
08mCompiling pattern matching to in-place modifications
23mVerified Code Generation for the Polyhedral Model