egg: Easy, Efficient, and Extensible E-graphs
egg: Easy, Efficient, and Extensible E-graphs
复制标题
Egg：简单、高效、可扩展的电子图
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Zachary Tatlock
中科院分区：
文献类型：
--
作者：
Max Willsey;Y. Wang;Oliver Flatt;Chandrakana Nandi;P. Panchekha;Zachary Tatlock
E-图是一种数据结构，它可以有效地编码等价关系在许多表达式上的同余闭包。E-图用于定理证明器中，用于在理论之间传达等式。另一系列的工作提出了他们使用重写驱动的程序优化技术称为平等饱和。在这项工作中，我们扩大了平等饱和的想法，并重新提出E-图作为一个解决方案，以各种各样的优化问题，解决过去的工作中发现的问题。我们介绍重建，一个新的，更简单的手段，保持全等闭合，比目前的技术快得多。我们提出了元数据，一种机制，使语义分析的E-图除了语法重写集成。我们实现了这些技术在鸡蛋，一个简单，高效，可扩展的电子图形库。我们重点介绍了在广泛的面向优化的应用程序中使用egg的已发表作品。
An E-graph is a data structure that can efficiently encode the congruence closure of an equivalence relation over many expressions. E-graphs are used in theorem provers for communicating equalities among theories. Another strand of work proposed their use for rewrite-driven program optimization with a technique called equality saturation. In this work, we expand on the idea of equality saturation and re-propose E-graphs as a solution to a diverse set of optimization problems, addressing issues identified by past work. We introduce rebuilding, a new, simpler means of maintaining congruence closure that is much faster than current techniques. We propose metadata, a mechanism that enables integration of semantic analyses to the E-graph in addition to syntactic rewrites. We realize these techniques in egg, an easy, efficient, and extensible E-graph library. We highlight published works that use egg across a wide range of optimization-oriented applications.
DOI：
--
发表时间：
2017-07
期刊：
ArXiv
影响因子：
--
作者：
Kevin Ellis;Daniel Ritchie;Armando Solar-Lezama;J. Tenenbaum
通讯作者：
Kevin Ellis;Daniel Ritchie;Armando Solar-Lezama;J. Tenenbaum
DOI：
10.1145/3355089.3356518
发表时间：
2019-11
期刊：
ACM Transactions on Graphics (TOG)
影响因子：
--
作者：
Chenming Wu;Haisen Zhao;Chandrakana Nandi;J. Lipton;Zachary Tatlock;Adriana Schulz
通讯作者：
Chenming Wu;Haisen Zhao;Chandrakana Nandi;J. Lipton;Zachary Tatlock;Adriana Schulz
通过等式饱和和逆变换综合结构化 CAD 模型
DOI：
10.1145/3385412.3386012
发表时间：
2020
期刊：
PLDI 2020: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Nandi, Chandrakana;Willsey, Max;Anderson, Adam;Wilcox, James R.;Darulova, Eva;Grossman, Dan;Tatlock, Zachary
通讯作者：
Tatlock, Zachary