A Joint Approach to Instruction Scheduling and Algebraic Rewriting with E-Graphs
summary
Scheduling Modulo Equality (SME) builds an e-graph via equality saturation and then encodes extraction as an ILP with binary variables XNT and YCT, latency constraints (child classes finish before parent minus D), and per-time-step resource caps; the ILP minimizes root finish time. Applied to prefix sum (n=8, m=2 shows Kogge‑Stone oversubscribes and can be slower), degree‑6 polynomial (Horner’s 6 FMA → a 3‑cycle parallel schedule), and EMA, SME reports e-graph + ILP extraction and claims up to 2.15× speedup.
AI-written summary · about
chapters (10)
- 0:00Joint optimization intro
- 2:27Scheduling requirements
- 3:51Double scheduling explained
- 7:00Prefix sum performance
- 8:04Horner’s method eval
- 10:34Filter optimization
- 12:17Exact methods guarantee
- 13:21Scaling challenges
- 14:01Future work
- 14:44Q&A
related talks
24mIncremental Equality Saturation
20mFast and Optimal Extraction for Sparse Equality Graphs
21mCut Tracing with E-Graphs for Boolean FHE Circuit Synthesis
22mOptimizing Optimizations: Case Study on Detecting Specific Types of Mathematical(…)
19meqsat: An Equality Saturation Dialect for Non-destructive Rewriting
24mOptimism in Equality Saturation
30mAutomated High-Level Synthesis Design Modularization via E-Graph Anti-Unification
21mImproving Equality Saturation for EDA via Semantic E-Graphs