{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T13:17:29Z","timestamp":1765977449565,"version":"3.48.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>Recent efforts of applying e-graphs in logic synthesis have shown promising results. Nevertheless, e-graph-based gate-level logic optimization suffers from inefficiency and limited extraction quality. In this article, we propose a fast parallel e-matching algorithm for speeding up e-graph rewriting, and an efficient netlist extraction framework with high quality of results in both area and delay. Experiments show that e-graph rewriting can be accelerated by up to 8.3\u00d7 over a high-performance e-graph library, and our extraction framework achieves 11.0% and 1.0% improvements in size and level on average, compared to the best results of the state-of-the-art netlist extraction method.<\/jats:p>","DOI":"10.1145\/3774883","type":"journal-article","created":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T11:45:17Z","timestamp":1762343117000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient and Effective E-graph-based Logic Optimization"],"prefix":"10.1145","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-2204-280X","authenticated-orcid":false,"given":"Tianji","family":"Liu","sequence":"first","affiliation":[{"name":"Computer Science and Engineering, The Chinese University of Hong Kong","place":["Shatin, Hong Kong"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-4332-0567","authenticated-orcid":false,"given":"Nutdranai","family":"Jaruthikorn","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, The Chinese University of Hong Kong","place":["Shatin, Hong Kong"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6556-7038","authenticated-orcid":false,"given":"Shiju","family":"Lin","sequence":"additional","affiliation":[{"name":"Thrust of Microelectronics, The Hong Kong University of Science and Technology - Guangzhou Campus","place":["Guangzhou, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8163-3114","authenticated-orcid":false,"given":"Bentian","family":"Jiang","sequence":"additional","affiliation":[{"name":"Huawei Design Automation Lab, Hong Kong","place":["Shatin, Hong Kong"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7318-4010","authenticated-orcid":false,"given":"Guannan","family":"Guo","sequence":"additional","affiliation":[{"name":"Huawei Design Automation Lab, Hong Kong","place":["Shatin, Hong Kong"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-0810-2042","authenticated-orcid":false,"given":"Weihua","family":"Sheng","sequence":"additional","affiliation":[{"name":"Huawei Design Automation Lab, Hong Kong","place":["Shatin, Hong Kong"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0623-1590","authenticated-orcid":false,"given":"Evangeline F.Y.","family":"Young","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, The Chinese University of Hong Kong","place":["Shatin, Hong Kong"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,12,17]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Proceedings of the IWLS","author":"Amar\u00fa Luca","year":"2015","unstructured":"Luca Amar\u00fa, Pierre-Emmanuel Gaillardon, and Giovanni De Micheli. 2015. The EPFL combinational benchmark suite. In Proceedings of the IWLS."},{"key":"e_1_3_2_3_2","volume-title":"Proceedings of the CAV","author":"Brayton Robert K.","year":"2010","unstructured":"Robert K. Brayton and Alan Mishchenko. 2010. ABC: An academic industrial-strength verification tool. In Proceedings of the CAV."},{"key":"e_1_3_2_4_2","first-page":"677","volume-title":"Proceedings of the ISCAS","author":"Brglez F.","year":"1985","unstructured":"F. Brglez and H. Fujiwara. 1985. A neutral netlist of 10 combinational benchmark circuits and a target translator in fortran. In Proceedings of the ISCAS. 677\u2013692."},{"key":"e_1_3_2_5_2","first-page":"410","volume-title":"Proceedings of the ASP-DAC","author":"Calvino Alessandro Tempia","year":"2022","unstructured":"Alessandro Tempia Calvino, Heinz Riener, Shubham Rai, Akash Kumar, and Giovanni De Micheli. 2022. A versatile mapping approach for technology mapping and graph optimization. In Proceedings of the ASP-DAC. 410\u2013416."},{"key":"e_1_3_2_6_2","volume-title":"Proceedings of the DAC","author":"Chen Chen","year":"2024","unstructured":"Chen Chen, Guangyu Hu, Dongsheng Zuo, Cunxi Yu, Yuzhe Ma, and Hongce Zhang. 2024. E-Syn: E-graph rewriting with technology-aware cost functions for logic synthesis. In Proceedings of the DAC. Article 124, 6 pages."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.mejo.2016.04.006"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/54.867894"},{"key":"e_1_3_2_9_2","first-page":"1","volume-title":"Proceedings of the DAC","author":"Coward Samuel","year":"2023","unstructured":"Samuel Coward, George A. Constantinides, and Theo Drane. 2023. Automating constraint-aware datapath optimization using e-graphs. In Proceedings of the DAC. 1\u20136."},{"key":"e_1_3_2_10_2","article-title":"ROVER: RTL optimization via verified e-graph rewriting","author":"Coward Samuel","year":"2024","unstructured":"Samuel Coward, Theo Drane, and George A. Constantinides. 2024. ROVER: RTL optimization via verified e-graph rewriting. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 43, 12 (2024), 4687\u20134700.","journal-title":"IEEE Trans. Comput.-Aided Design Integr. Circuits Syst."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2024.3483096"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_3_2_13_2","first-page":"974","volume-title":"Proceedings of the IPDPS","author":"Huang Tsung-Wei","year":"2019","unstructured":"Tsung-Wei Huang, Chun-Xun Lin, Guannan Guo, and Martin Wong. 2019. Cpp-taskflow: Fast task-based parallel programming using modern C++. In Proceedings of the IPDPS. 974\u2013983."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2002.804386"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2023.3256341"},{"key":"e_1_3_2_16_2","first-page":"392","volume-title":"Proceedings of the ASP-DAC","author":"Liu Tianji","year":"2024","unstructured":"Tianji Liu, Lei Chen, Xing Li, Mingxuan Yuan, and Evangeline F.Y. Young. 2024. FineMap: A fine-grained GPU-parallel LUT mapping engine. In Proceedings of the ASP-DAC. 392\u2013397."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2024.3429079"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.882119"},{"key":"e_1_3_2_19_2","volume-title":"Proceedings of the IWLS","author":"Mishchenko Alan","year":"2006","unstructured":"Alan Mishchenko and Robert K. Brayton. 2006. Scalable logic synthesis using a simple circuit structure. In Proceedings of the IWLS."},{"key":"e_1_3_2_20_2","first-page":"532","volume-title":"Proceedings of the DAC","author":"Mishchenko Alan","year":"2006","unstructured":"Alan Mishchenko, Satrajit Chatterjee, and Robert Brayton. 2006. DAG-aware AIG rewriting: A fresh look at combinational logic synthesis. In Proceedings of the DAC. 532\u2013535."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.887925"},{"key":"e_1_3_2_22_2","first-page":"354","volume-title":"Proceedings of the ICCAD","author":"Mishchenko Alan","year":"2007","unstructured":"Alan Mishchenko, Sungmin Cho, Satrajit Chatterjee, and Robert Brayton. 2007. Combinational and sequential mapping with priority cuts. In Proceedings of the ICCAD. 354\u2013361."},{"key":"e_1_3_2_23_2","first-page":"183","volume-title":"Proceedings of the CADE (CADE-21)","author":"Moura Leonardo","year":"2007","unstructured":"Leonardo Moura and Nikolaj Bj\u00f8rner. 2007. Efficient e-matching for SMT solvers. In Proceedings of the CADE (CADE-21). 183\u2013198."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/909447"},{"key":"e_1_3_2_25_2","first-page":"264","volume-title":"Proceedings of the POPL (POPL\u201909)","author":"Tate Ross","year":"2009","unstructured":"Ross Tate, Michael Stepp, Zachary Tatlock, and Sorin Lerner. 2009. Equality saturation: A new approach to optimization. In Proceedings of the POPL (POPL\u201909). 264\u2013276."},{"key":"e_1_3_2_26_2","first-page":"23","article-title":"Egg: Fast and extensible equality saturation","volume":"5","author":"Willsey Max","year":"2021","unstructured":"Max Willsey, Chandrakana Nandi, Yisu Remy Wang, Oliver Flatt, Zachary Tatlock, and Pavel Panchekha. 2021. Egg: Fast and extensible equality saturation. Proc. ACM Program. Lang. 5, POPL, Article 23 (Jan.2021), 1\u201329.","journal-title":"Proc. ACM Program. Lang."},{"key":"e_1_3_2_27_2","volume-title":"Logic Synthesis and Optimization Benchmarks User Guide: Version 3.0","author":"Yang S.","year":"1991","unstructured":"S. Yang. 1991. Logic Synthesis and Optimization Benchmarks User Guide: Version 3.0. Technical Report. MCNC Technical Report."},{"key":"e_1_3_2_28_2","first-page":"125","article-title":"Better together: Unifying datalog and equality saturation","volume":"7","author":"Zhang Yihong","year":"2023","unstructured":"Yihong Zhang, Yisu Remy Wang, Oliver Flatt, David Cao, Philip Zucker, Eli Rosenthal, Zachary Tatlock, and Max Willsey. 2023. Better together: Unifying datalog and equality saturation. Proc. ACM Program. Lang. 7, PLDI, Article 125 (June2023), 468\u2013492.","journal-title":"Proc. ACM Program. Lang."},{"key":"e_1_3_2_29_2","first-page":"35","article-title":"Relational e-matching","volume":"6","author":"Zhang Yihong","year":"2022","unstructured":"Yihong Zhang, Yisu Remy Wang, Max Willsey, and Zachary Tatlock. 2022. Relational e-matching. Proc. ACM Program. Lang. 6, POPL, Article 35 (Jan.2022), 1\u201322.","journal-title":"Proc. ACM Program. Lang."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3774883","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T13:15:23Z","timestamp":1765977323000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3774883"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,17]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1145\/3774883"],"URL":"https:\/\/doi.org\/10.1145\/3774883","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2025,12,17]]},"assertion":[{"value":"2025-02-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-19","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}