Simplifying Multiple-Statement Reductions with the Polyhedral Model
summary
Paper formalizes simplifying dependent reductions as an integer bilinear program over reuse vectors and polyhedral schedules and shows it is hard to solve directly, so it proposes a heuristic using an existing affine schedule that chooses reuse vectors preserving original dependences. Evaluation on 11 probabilistic-inference benchmarks (Gibbs, belief propagation, MCMC patterns) yields optimal complexity for all cases, complexity improvements by factors matching input sizes (10^4–10^6) and wall‑clock speedups from 1.1× to >10^6× (median 37×).
AI-written summary · about
chapters (16)
- 0:00Introduction
- 0:14Problem Statement
- 1:57Contributions
- 2:32Dependent Reductions
- 3:29Gibbs Sampling
- 7:07Visualization
- 9:22Polyhedral Sets
- 9:46Program Representation
- 10:27Scheduling
- 12:38Simplifying Reductions
- 14:51Simplifying Dependent Reductions
- 18:28Heuristic Algorithm
- 19:17Example
- 22:05Evaluation
- 23:19Conclusion
- 24:01Thank you
related talks
22mMaximal Simplification of Polyhedral Reductions
30mA Novel EGs-Based Framework for Systematic Propositional-Formula Simplification
15mClosing Remarks
19mIncremental Computation for Efficient Programmable Inference in Probabilistic Programs
15mA Modular Cost Analysis for Probabilistic Programs
15mProducts of Recursive Programs for Hypersafety Verification
15mScaling Optimization Over Uncertainty via Compilation
18mEquivalence and Similarity Refutation for Probabilistic Programs