Optimizing Stateful Dataflow with Local Rewrites
Optimizing a stateful dataflow language is a challenging task. There are strict correctness constraints for preserving properties expected by downstream consumers, a large space of possible optimizations, and complex analyses that must reason about the behavior of the program over time. Classic compiler techniques with specialized optimization passes yield unpredictable performance and have complex correctness proofs. But with e-graphs, we can dramatically simplify the process of building a correct optimizer while yielding more consistent results! In this short paper, we discuss our early work using e-graphs to develop an optimizer for a the Hydroflow dataflow language. Our prototype demonstrates that composing simple, easy-to-prove rewrite rules is sufficient to match techniques in hand-optimized systems.
Presentation (optimizing-stateful-dataflow-egraphs-2023.pdf) | 3.39MiB |
Extended Abstract (optimizing_stateful_dataflow.pdf) | 424KiB |
Sun 18 JunDisplayed time zone: Eastern Time (US & Canada) change
09:00 - 11:00 | |||
09:40 20mTalk | Automating Constraint-Aware Datapath Optimization using E-Graphs EGRAPHS Samuel Coward Imperial College London, UK / Intel Corporation, George A. Constantinides Imperial College London, UK, Theo Drane Intel Corporation, USA Pre-print File Attached | ||
10:00 20mTalk | egglog In Practice: Automatically Improving Floating-point Error EGRAPHS | ||
10:20 20mTalk | Optimizing Stateful Dataflow with Local Rewrites EGRAPHS Shadaj Laddad University of California at Berkeley, Conor Power University of California at Berkeley, Tyler Hou University of California, Berkeley, Alvin Cheung University of California at Berkeley, Joseph M. Hellerstein University of California, Berkeley Pre-print File Attached | ||
10:40 20mTalk | Egg-smol Python: A Pythonic Library for E-graphs EGRAPHS Link to publication Pre-print |