Sun 18 Jun 2023 16:20 - 16:40 at Magnolia 18 - EGRAPHS: Binding & Extraction

Term extraction is a crucial workload in \texttt{egg} for determining the desired terms to be extracted. Some prior works have formulated term extraction as integer linear programming (ILP) problems in order to cope with common sub-expressions for optimality that could not be handled by greedy algorithms. Although ILP-based extraction algorithms ensure optimality, these formulations offload a topological sorting problem to the ILP solver to avoid extracting cyclic terms, which does not scale well with the complexity of cycles in the e-graph. Instead of enforcing topological orders with constraints, we propose to explicitly identify the cycles and encode them to \textit{Acyclic constraints}. This approach enables us to formulate term extraction problems in terms of Weighted Partial MAXSAT problems and improve the solving speed of the current ILP formulation. Our evaluation of term extraction for equality saturation on real-world Deep Learning (DL) workloads shows that using the improved formulation yields up to $\sim$3x speed-up on the total extraction time compared with using the state-of-the-art ILP encoding.

slides (presentation.pdf)2.96MiB

Sun 18 Jun

Displayed time zone: Eastern Time (US & Canada) change

16:00 - 17:50
EGRAPHS: Binding & ExtractionEGRAPHS at Magnolia 18

#egraphs-sun-magnolia18 Discord icon small YouTube icon small

16:00
20m
Talk
Optimizing Beta-Reduction in E-Graphs
EGRAPHS
Emmanuel Anaya Gonzalez UCSD, Cole Kurashige UCSD, Aditya Giridharan UCSD, Nadia Polikarpova University of California at San Diego
File Attached
16:20
20m
Talk
Improving Term Extraction with Acyclic Constraints
EGRAPHS
Deyuan (Mike) He Princeton University, Haichen Dong Princeton University, Sharad Malik Princeton University, Aarti Gupta Princeton University
File Attached
16:40
20m
Talk
E-graph Extraction Using ZDDs
EGRAPHS