{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:12:08Z","timestamp":1784200328523,"version":"3.55.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T00:00:00Z","timestamp":1759968000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,10,9]]},"abstract":"<jats:p>Modern optimizing compilers generate efficient code but rarely achieve theoretical optimality, often necessitating manual fine-tuning. This is especially the case for processors with vector instructions, which can grow the instruction set by an order of magnitude. Super-optimizers can synthesize optimal code, but they face a fundamental scalability constraint: as the size of the instruction set increases, the length of the longest synthesizable program decreases rapidly.<\/jats:p>\n                  <jats:p>\n                    To help super-optimizers deal with large instruction sets, we introduce\n                    <jats:sc>HieraSynth<\/jats:sc>\n                    , a parallel framework for super-optimization that decomposes the problem by hierarchically partitioning the space of candidate programs, effectively decreasing the instruction set size. It also prunes search branches when the solver proves unrealizability, and explores independent subspaces in parallel, achieving near-linear speedup.\n                    <jats:sc>HieraSynth<\/jats:sc>\n                    is sufficiently efficient to run to completeness even on many hard problems, which means that it exhaustively explores the program space. This ensures that the synthesized program is optimal according to a cost model.\n                  <\/jats:p>\n                  <jats:p>\n                    We implement\n                    <jats:sc>HieraSynth<\/jats:sc>\n                    as a library and demonstrate its effectiveness with a RISC-V Vector superoptimizer capable of handling instruction sets with up to 700 instructions while synthesizing 7\u20138-instruction programs. This is a significant advancement over previous approaches that were limited to\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                        <mml:mrow>\n                          <mml:mn>1<\/mml:mn>\n                          <mml:mo>\u2212<\/mml:mo>\n                          <mml:mn>3<\/mml:mn>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    instructions with similar instruction set sizes. Specifically,\n                    <jats:sc>HieraSynth<\/jats:sc>\n                    can handle instruction sets up to 10.66\u00d7 larger for a given program size, or synthesize up to 4.75\u00d7 larger programs for a fixed instruction set. Evaluations show that\n                    <jats:sc>HieraSynth<\/jats:sc>\n                    can synthesize code surpassing human-expert optimizations and significantly reduce synthesis time, making super-optimization more practical for modern vector architectures.\n                  <\/jats:p>","DOI":"10.1145\/3763162","type":"journal-article","created":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T08:51:31Z","timestamp":1759999891000},"page":"3120-3147","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["HieraSynth: A Parallel Framework for Complete Super-Optimization with Hierarchical Space Decomposition"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2757-7603","authenticated-orcid":false,"given":"Sirui","family":"Lu","sequence":"first","affiliation":[{"name":"University of Washington, Seattle, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6639-1647","authenticated-orcid":false,"given":"Rastislav","family":"Bod\u00edk","sequence":"additional","affiliation":[{"name":"Google DeepMind, Mountain View, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"2024. Highway API synopsis\/quick reference. https:\/\/web.archive.org\/web\/20240615094120\/https:\/\/web.archive.org\/web\/20240615094120\/https:\/\/github.com\/google\/highway\/blob\/master\/g3doc\/quick_reference.md"},{"key":"e_1_3_1_3_2","unstructured":"2024. RISC-V vector extension for integer workloads: An informal gap analysis. https:\/\/web.archive.org\/web\/20241113090818\/https:\/\/gist.github.com\/camel-cdr\/99a41367d6529f390d25e36ca3e4b626"},{"key":"e_1_3_1_4_2","unstructured":"2025. SiFive Intelligence X200 Series. https:\/\/web.archive.org\/web\/20250629211746\/https:\/\/www.sifive.com\/cores\/intelligence-x200-series"},{"key":"e_1_3_1_5_2","unstructured":"2025. SiFive Performance P600-Series. https:\/\/web.archive.org\/web\/20250629195319\/https:\/\/www.sifive.com\/cores\/performance-p600"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","unstructured":"Rajeev Alur Rastislav Bodik Garvit Juniwal Milo M. K. Martin Mukund Raghothaman Sanjit A. Seshia Rishabh Singh Armando Solar-Lezama Emina Torlak and Abhishek Udupa. 2013. Syntax-guided synthesis. In 2013 Formal Methods in Computer-Aided Design. 1\u20138. doi:10.1109\/FMCAD.2013.6679385","DOI":"10.1109\/FMCAD.2013.6679385"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168906"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442529"},{"key":"e_1_3_1_9_2","unstructured":"Mark Blacher Joachim Giesen Peter Sanders and Jan Wassenberg. 2022. Vectorized and performance-portable Quicksort. arXiv:2205.05982 [cs.IR] https:\/\/arxiv.org\/abs\/2205.05982"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1706299.1706339"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837666"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535859"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3729336"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454080"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062351"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993506"},{"key":"e_1_3_1_17_2","unstructured":"Highway Developers. 2024. Highway. https:\/\/github.com\/google\/highway"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-71294-4_1"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3563943"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3472749.3474740"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385979"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386027"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21668-3_22"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-017-0269-8"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806799.1806833"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512566"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/1186632.1186633"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3571216"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535857"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3689766"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3571209"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","unstructured":"Sirui Lu and Rastislav Bod\u00edk. 2025. OOPSLA 2025 Artifact: HieraSynth. Zenodo. doi:10.5281\/zenodo.16923496","DOI":"10.5281\/zenodo.16923496"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/36206.36194"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/364995.365000"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322198"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-37703-7_1"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32033-3_33"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2980024.2872387"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908093"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814310"},{"key":"e_1_3_1_41_2","unstructured":"Raimondas Sasnauskas Yang Chen Peter Collingbourne Jeroen Ketema Gratian Lup Jubi Taneja and John Regehr. 2018. Souper: A Synthesizing Superoptimizer. arXiv:1711.04422 [cs.PL] https:\/\/arxiv.org\/abs\/1711.04422"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451150"},{"key":"e_1_3_1_43_2","volume-title":"Program Synthesis by Sketching. Ph. D. Dissertation","author":"Solar-Lezama Armando","year":"2008","unstructured":"Armando Solar-Lezama. 2008. Program Synthesis by Sketching. Ph. D. Dissertation. University of California, Berkeley, USA. Advisor(s) Bodik, Rastislav. AAI3353225."},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168907"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1_59"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480915"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591274"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3445814.3446707"},{"key":"e_1_3_1_49_2","volume-title":"Hacker\u2019s delight","author":"Warren Henry S","year":"2013","unstructured":"Henry S Warren. 2013. Hacker\u2019s delight. Pearson Education."},{"key":"e_1_3_1_50_2","doi-asserted-by":"crossref","unstructured":"Andrew Waterman Yunsup Lee David A. Patterson and Krste Asanovi\u0107. 2014. The RISC-V Instruction Set Manual Volume I: User-Level ISA Version 2.0. Technical Report UCB\/EECS-2014-54. http:\/\/www2.eecs.berkeley.edu\/Pubs\/TechRpts\/2014\/EECS-2014-54.html","DOI":"10.21236\/ADA605735"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434304"},{"key":"e_1_3_1_52_2","first-page":"255","article-title":"Equality Saturation for Tensor Graph Superoptimization","volume":"3","author":"Yang Yichen","year":"2021","unstructured":"Yichen Yang, Phitchaya Phothilimthana, Yisu Wang, Max Willsey, Sudip Roy, and Jacques Pienaar. 2021. Equality Saturation for Tensor Graph Superoptimization. In Proceedings of Machine Learning and Systems, A. Smola, A. Dimakis, and I. Stoica (Eds.), Vol. 3. 255\u2013268. https:\/\/proceedings.mlsys.org\/paper_files\/paper\/2021\/file\/cc427d934a7f6c0663e5923f49eba531-Paper.pdf","journal-title":"Proceedings of Machine Learning and Systems"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763162","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763162","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:17:36Z","timestamp":1784197056000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763162"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":51,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2025,10,9]]}},"alternative-id":["10.1145\/3763162"],"URL":"https:\/\/doi.org\/10.1145\/3763162","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,9]]},"assertion":[{"value":"2025-03-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}