{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:04:28Z","timestamp":1784199868790,"version":"3.55.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T00:00:00Z","timestamp":1749772800000},"content-version":"vor","delay-in-days":3,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["HR0011-23-C-0101"],"award-info":[{"award-number":["HR0011-23-C-0101"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2217064, CCF-2328543,"],"award-info":[{"award-number":["CCF-2217064, CCF-2328543,"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,6,10]]},"abstract":"<jats:p>Subroutines are essential building blocks in software design: users encapsulate common functionality in libraries and write applications by composing calls to subroutines. Unfortunately, performance may be lost at subroutine boundaries due to reduced locality and increased memory consumption. Operator fusion helps recover the performance lost at composition boundaries. Previous solutions fuse operators by manually rewriting code into monolithic fused subroutines, or by relying on heavy-weight compilers to generate code that performs fusion. Both approaches require a semantic understanding of the entire computation, breaking the decoupling necessary for modularity and reusability of subroutines.<\/jats:p>\n                  <jats:p>In this work, we attempt to identify the minimal ingredients required to fuse computations, enabling composition of subroutines without sacrificing performance or modularity. We find that, unlike previous approaches that require a semantic understanding of the computation, most opportunities for fusion require understanding only data production and consumption patterns. Exploiting this insight, we add fusion on top of black-box subroutines by proposing a lightweight enrichment of subroutine declarations to expose data-dependence patterns. We implement our approach in a system called Fern, and demonstrate Fern\u2019s benefits by showing that it is competitive with state-of-the-art, high-performance libraries with manually fused operators, can fuse across library and domain boundaries for unforeseen workloads, and can deliver speedups of up to 5\u00d7 over unfused code.<\/jats:p>","DOI":"10.1145\/3729292","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"1043-1067","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Lightweight and Locality-Aware Composition of Black-Box Subroutines"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-8570-1947","authenticated-orcid":false,"given":"Manya","family":"Bansal","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7118-7576","authenticated-orcid":false,"given":"Dillon","family":"Sharlet","sequence":"additional","affiliation":[{"name":"Google, Mountain View, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6243-9543","authenticated-orcid":false,"given":"Jonathan","family":"Ragan-Kelley","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7231-7643","authenticated-orcid":false,"given":"Saman","family":"Amarasinghe","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","unstructured":"Corinne Ancourt and Fran\u00e7ois Irigoin. 1991. Scanning polyhedra with DO loops. In Proceedings of the Third ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Williamsburg Virginia USA) (PPOPP \u201991). Association for Computing Machinery New York NY USA 39\u201350. https:\/\/doi.org\/10.1145\/109625.109631 10.1145\/109625.109631","DOI":"10.1145\/109625.109631"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3620665.3640366"},{"key":"e_1_3_2_4_2","unstructured":"Apple Inc. [n. d.]. Apple Developer Documentation: BNNS. https:\/\/developer.apple.com\/documentation\/accelerate\/bnns. Accessed: 2024-05-20."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591236"},{"key":"e_1_3_2_6_2","unstructured":"Kit Barton Johannes Doerfert Hal Finkel and Michael Kruse. 2018. Revisiting Loop Fusion and its place in the loop transformation framework. https:\/\/llvm.org\/devmtg\/2018-10\/slides\/Barton-LoopFusion.pdf LLVM Developers\u2019 Meeting October 2018."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.71"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807271"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1941553.1941561"},{"key":"e_1_3_2_10_2","unstructured":"Chun Chen Jacqueline Chame and Mary W. Hall. 2007. CHiLL : A Framework for Composing High-Level Loop Transformations. Technical Report."},{"key":"e_1_3_2_11_2","first-page":"579","volume-title":"Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation (Carlsbad, CA, USA) (OSDI\u201918)","author":"Chen Tianqi","year":"2018","unstructured":"Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Meghan Cowan, Haichen Shen, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018. TVM: An Automated End-to-End Optimizing Compiler for Deep Learning. In Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation (Carlsbad, CA, USA) (OSDI\u201918). USENIX Association, USA, 579\u2013594."},{"key":"e_1_3_2_12_2","unstructured":"Zhuoming Chen Avner May Ruslan Svirschevski Yuhsun Huang Max Ryabinin Zhihao Jia and Beidi Chen. 2024. Sequoia: Scalable Robust and Hardware-aware Speculative Decoding. arXiv:2402.12374 [cs.CL] https:\/\/arxiv.org\/abs\/2402.12374"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276493"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1291151.1291199"},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","unstructured":"Tri Dao Daniel Y. Fu Stefano Ermon Atri Rudra and Christopher R\u00e9. 2022. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness. arXiv:2205.14135 [cs.LG] https:\/\/arxiv.org\/abs\/2205.14135","DOI":"10.52202\/068431-1189"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199461"},{"key":"e_1_3_2_18_2","volume-title":"A View of Programming Languages (Addison-Wesley Series in Computer Science and Information Pr)","author":"Galler and Perlis","year":"1976","unstructured":"Galler and Perlis. 1976. A View of Programming Languages (Addison-Wesley Series in Computer Science and Information Pr). Addison-Wesley Longman Publishing Co., Inc., USA."},{"key":"e_1_3_2_19_2","volume-title":"GEOS coordinate transformation software library","author":"GEOS contributors","year":"2021","unstructured":"GEOS contributors. 2021. GEOS coordinate transformation software library. Open Source Geospatial Foundation. https:\/\/libgeos.org\/"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","unstructured":"Sean Gillies Casper van der Wel Joris Van den Bossche Mike W. Taves Joshua Arnott Brendan C. Ward. and others. 2024. Shapely. https:\/\/doi.org\/10.5281\/zenodo.5597138 10.5281\/zenodo.5597138","DOI":"10.5281\/zenodo.5597138"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/1538674"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3410463.3414632"},{"key":"e_1_3_2_23_2","unstructured":"Apple Inc. [n. d.]. Accelerate Framework. https:\/\/developer.apple.com\/documentation\/accelerate. Accessed: 2024-06-10."},{"key":"e_1_3_2_24_2","volume-title":"Intel Math Kernel Library. Reference Manual","year":"2009","unstructured":"2009. Intel Math Kernel Library. Reference Manual. Intel Corporation, Santa Clara. Accessed: 2024-06-10."},{"key":"e_1_3_2_25_2","volume-title":"Intel Advanced Vector Extensions Programming Reference","year":"2011","unstructured":"2011. Intel Advanced Vector Extensions Programming Reference. Intel Corporation, Santa Clara, USA. https:\/\/www.intel.com\/content\/dam\/develop\/external\/us\/en\/documents\/36945"},{"key":"e_1_3_2_26_2","unstructured":"Intel Corporation. 2024. Intel Implicit SPMD Program Compiler (ISPC). https:\/\/ispc.github.io\/ispc.html. Accessed: 2024-06-10."},{"key":"e_1_3_2_27_2","unstructured":"Intel Corporation. 2024. Memory Format Propagation. https:\/\/www.intel.com\/content\/www\/us\/en\/docs\/onednn\/developer-guide-reference\/2024-1\/memory-format-propagation.html. Accessed: 2024-06-10."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","unstructured":"Fredrik Kj\u00f8lstad Peter Ahrens Shoaib Kamil and Saman Amarasinghe. 2019. Tensor Algebra Compilation with Workspaces. In 2019 IEEE\/ACM International Symposium on Code Generation and Optimization (CGO). 180\u2013192. https:\/\/doi.org\/10.1109\/CGO.2019.8661185 10.1109\/CGO.2019.8661185","DOI":"10.1109\/CGO.2019.8661185"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/355841.355847"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","unstructured":"S.T. Leutenegger M.A. Lopez and J. Edgington. 1997. STR: a simple and efficient algorithm for R-tree packing. In Proceedings 13th International Conference on Data Engineering. 497\u2013506. https:\/\/doi.org\/10.1109\/ICDE.1997.582015 10.1109\/ICDE.1997.582015","DOI":"10.1109\/ICDE.1997.582015"},{"key":"e_1_3_2_31_2","unstructured":"Arm Limited. [n. d.]. Arm Performance Libraries. https:\/\/developer.arm.com\/downloads\/-\/arm-performance-libraries."},{"key":"e_1_3_2_32_2","unstructured":"Chao Liu Jing Zhang Letao Qin Qianfeng Zhang Liang Huang Shaojie Wang Anthony Chang Chunyu Lai Illia Silin Adam Osewski Poyen Chen Rosty Geyyer Hanwen Chen Tejash Shah Xiaoyan Zhou and Jianfeng Yan. [n. d.]. Composable Kernel. https:\/\/github.com\/ROCm\/composable_kernel"},{"key":"e_1_3_2_33_2","unstructured":"NVIDIA. 2022. CUTLASS. NVIDIA. https:\/\/developer.nvidia.com\/blog\/cutlass-linear-algebra-cuda\/"},{"key":"e_1_3_2_34_2","unstructured":"oneDNN Contributors. [n. d.]. oneAPI Deep Neural Network Library (oneDNN). https:\/\/github.com\/oneapi-src\/oneDNN Accessed: 2024-06-10."},{"key":"e_1_3_2_35_2","article-title":"Weld: Rethinking the Interface Between Data-Intensive Applications","author":"Palkar Shoumik","year":"2017","unstructured":"Shoumik Palkar, James Thomas, Deepak Narayanan, Anil Shanbhag, Rahul Palamuttam, Holger Pirk, Malte Schwarzkopf, Saman P. Amarasinghe, Samuel Madden, and Matei Zaharia. 2017. Weld: Rethinking the Interface Between Data-Intensive Applications. CoRR abs\/1709.06416 (2017). arXiv:1709.06416 http:\/\/arxiv.org\/abs\/1709.06416","journal-title":"CoRR"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359652"},{"key":"e_1_3_2_37_2","unstructured":"LLVM Project. 2024. Affine Loop Fusion - MLIR Documentation. https:\/\/mlir.llvm.org\/docs\/Passes\/#-affine-loop-fusion Accessed: 2024-06-20."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185528"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3150211"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462176"},{"key":"e_1_3_2_41_2","unstructured":"Amit Sabne. 2020. XLA : Compiling Machine Learning for Peak Performance."},{"key":"e_1_3_2_42_2","unstructured":"Christian Sarofeen Piotr Bialecki Jie Jiang Kevin Stephano Masaki Kozuki Neal Vaidya and Stas Bekman. 2022. Introducing nvFuser A Deep Learning Compiler for PyTorch. https:\/\/pytorch.org\/blog\/introducing-nvfuser-a-deep-learning-compiler-for-pytorch\/."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3572848.3577509"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3652605"},{"key":"e_1_3_2_45_2","unstructured":"TileDB Inc. 2024. TileDB: The Universal Storage Engine. https:\/\/github.com\/TileDB-Inc\/TileDB. Accessed: 2024-06-10."},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/2764454"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90147-A"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90147-A"},{"key":"e_1_3_2_49_2","unstructured":"Robert Alan Wagner. 1968. Some techniques for algorithm optimization with application to matrix arithmetic expressions. Ph. D. Dissertation. USA. AAI6907907."},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3620666.3651322"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3669940.3707216"},{"key":"e_1_3_2_52_2","first-page":"10","volume-title":"Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing (Boston, MA) (HotCloud\u201910)","author":"Zaharia Matei","year":"2010","unstructured":"Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: cluster computing with working sets. In Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing (Boston, MA) (HotCloud\u201910). USENIX Association, USA, 10."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729292","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729292","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:04:27Z","timestamp":1784196267000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729292"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":51,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729292"],"URL":"https:\/\/doi.org\/10.1145\/3729292","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-11-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}