{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:06:28Z","timestamp":1784199988886,"version":"3.55.0"},"reference-count":43,"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"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2216964"],"award-info":[{"award-number":["CCF-2216964"]}],"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,10,9]]},"abstract":"<jats:p>We introduce REPTILE, a compiler that performs tiling optimizations for programs expressed as mathematical recurrence equations. REPTILE recursively decomposes a recurrence program into a set of unique tiles and then simplifies each into a different set of recurrences. Given declarative user specifications of recurrence equations, optimizations, and optional mappings of recurrence subexpressions to external libraries calls, REPTILE generates C code that composes compiler-generated loops with calls to external hand-optimized libraries. We show that for direct linear solvers expressible as recurrence equations, the generated C code matches and often exceeds the performance of standard hand-optimized libraries. We evaluate REPTILE\u2019s generated C code against hand-optimized implementations of linear solvers in Intel MKL, as well as two nonsolver recurrences from bioinformatics: Needleman-Wunsch and Smith-Waterman. When the user provides good tiling specifications, REPTILE achieves parity with MKL, achieving between 0.79\u22121.27x speedup for the LU decomposition, 0.97\u22121.21x speedup for the Cholesky decomposition, 1.61x\u22122.72x for lower triangular matrix inversion, 1.01\u22121.14x speedup for triangular solve with multiple right-hand sides, and 1.14\u22121.73x speedup over handwritten implementations of the bioinformatics recurrences.<\/jats:p>","DOI":"10.1145\/3763074","type":"journal-article","created":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T08:49:50Z","timestamp":1759999790000},"page":"670-696","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["REPTILE: Performant Tiling of Recurrences"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-1588-0271","authenticated-orcid":false,"given":"Muhammad Usman","family":"Tariq","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5228-1295","authenticated-orcid":false,"given":"Shiv","family":"Sundram","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2267-903X","authenticated-orcid":false,"given":"Fredrik","family":"Kjolstad","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_3_1_2_1","unstructured":"Accessed 2024. OpenBLAS: An Optimized BLAS Library. https:\/\/www.openblas.net\/. Accessed: 2024-11-15."},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","unstructured":"Emmanuel Agullo Jim Demmel Jack Dongarra Bilel Hadri Jakub Kurzak Julien Langou Hatem Ltaief Piotr Luszczek and Stanimire Tomov. 2009. Numerical linear algebra on emerging architectures: The PLASMA and MAGMA projects. Journal of Physics: Conference Series 180 (08 2009) 012037. https:\/\/doi.org\/10.1088\/1742-6596\/180\/1\/01203710.1088\/1742-6596\/180\/1\/012037","DOI":"10.1088\/1742-6596\/180\/1\/012037"},{"key":"e_1_3_1_4_1","doi-asserted-by":"crossref","unstructured":"Edward Anderson Zhaojun Bai Christian Bischof L Susan Blackford James Demmel Jack Dongarra Jeremy Du Croz Anne Greenbaum Sven Hammarling Alan McKenney et al. 1999. LAPACK users\u2019 guide. SIAM.","DOI":"10.1137\/1.9780898719604"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","unstructured":"Manya Bansal Olivia Hsu Kunle Olukotun and Fredrik Kjolstad. 2023. Mosaic: An Interoperable Compiler for Tensor Algebra. Proc. ACM Program. Lang. 7 PLDI Article 122 (June 2023) 26 pages. https:\/\/doi.org\/10.1145\/359123610.1145\/3591236","DOI":"10.1145\/3591236"},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","unstructured":"Paolo Bientinesi John A. Gunnels Margaret E. Myers Enrique S. Quintana-Ort\u00ed and Robert A. van de Geijn. 2005. The science of deriving dense linear algebra algorithms. ACM Trans. Math. Softw. 31 1 (March 2005) 1\u201326. https:\/\/doi.org\/10.1145\/1055531.105553210.1145\/1055531.1055532","DOI":"10.1145\/1055531.1055532"},{"key":"e_1_3_1_7_1","unstructured":"Aart J.C. Bik Bixia Zheng Fredrik Kjolstad Nicolas Vasilache Penporn Koanantakool and Tatiana Shpeisman. 2022. Compiler Support for Sparse Tensor Computations in MLIR. ACM Transactions on Architecture and Code Optimization (2022)."},{"key":"e_1_3_1_8_1","doi-asserted-by":"crossref","unstructured":"George Bosilca Aurelien Bouteiller Anthony Danalis Mathieu Faverge Azzam Haidar Thomas Herault Jakub Kurzak Julien Langou Pierre Lemarinier Hatem Ltaief et al. 2011. Flexible development of dense linear algebra algorithms on massively parallel architectures with DPLASMA. In 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum. IEEE 1432\u20131441.","DOI":"10.1109\/IPDPS.2011.299"},{"key":"e_1_3_1_9_1","doi-asserted-by":"crossref","unstructured":"George Bosilca Aurelien Bouteiller Anthony Danalis Mathieu Faverge Thomas H\u00e9rault and Jack J Dongarra. 2013. Parsec: Exploiting heterogeneity to enhance scalability. Computing in Science & Engineering 15 6 (2013) 36\u201345.","DOI":"10.1109\/MCSE.2013.98"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-61763-8_3"},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","unstructured":"Steve Carr and Ken Kennedy. 1994. Improving the ratio of memory operations to floating-point operations in loops. ACM Trans. Program. Lang. Syst. 16 6 (Nov. 1994) 1768\u20131810. https:\/\/doi.org\/10.1145\/197320.19736610.1145\/197320.197366","DOI":"10.1145\/197320.197366"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3126908.3126936"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392486"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","unstructured":"J. Choi J. J. Dongarra R. Pozo and D.W. Walker. 1992. ScaLAPACK: a scalable linear algebra library for distributed memory concurrent computers. In [Proceedings 1992] The Fourth Symposium on the Frontiers of Massively Parallel Computation. 120\u2013127. https:\/\/doi.org\/10.1109\/FMPC.1992.23489810.1109\/FMPC.1992.234898","DOI":"10.1109\/FMPC.1992.234898"},{"key":"e_1_3_1_15_1","doi-asserted-by":"crossref","unstructured":"Stephen Chou Fredrik Kjolstad and Saman Amarasinghe. 2018. Format Abstraction for Sparse Tensor Algebra Compilers. Proc. ACM Program. Lang. 2 OOPSLA Article 123 (October 2018) 30 pages.","DOI":"10.1145\/3276493"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","unstructured":"Jeffrey A. Daily. 2016. Parasail: SIMD C library for global semi-global and local pairwise sequence alignments. BMC Bioinformatics 17 (2 2016). https:\/\/doi.org\/10.1186\/s12859-016-0930-z10.1186\/s12859-016-0930-z","DOI":"10.1186\/s12859-016-0930-z"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","unstructured":"J. J. Dongarra Jermey Du Cruz Sven Hammarling and I. S. Duff. 1990. Algorithm 679: A set of level 3 basic linear algebra subprograms: model implementation and test programs. ACM Trans. Math. Softw. 16 1 (March 1990) 18\u201328. https:\/\/doi.org\/10.1145\/77626.7762710.1145\/77626.77627","DOI":"10.1145\/77626.77627"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.728"},{"key":"e_1_3_1_19_1","doi-asserted-by":"crossref","unstructured":"Jack J Dongarra Cleve Barry Moler James R Bunch and Gilbert W Stewart. 1979. LINPACK users\u2019 guide. SIAM.","DOI":"10.1137\/1.9781611971811"},{"key":"e_1_3_1_20_1","doi-asserted-by":"crossref","unstructured":"Jason Eisner Eric Goldlust and Noah A Smith. 2004. Dyna: A declarative language for implementing dynamic programs. In Proc. of ACL.","DOI":"10.3115\/1219044.1219076"},{"key":"e_1_3_1_21_1","doi-asserted-by":"crossref","unstructured":"Paul Feautrier. 1991. Dataflow Analysis of Array and Scalar References. International fournal of Parallel Programming 20 1 (1991) 23\u201353.","DOI":"10.1007\/BF01407931"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","unstructured":"John A. Gunnels Fred G. Gustavson Greg M. Henry and Robert A. van de Geijn. 2001. FLAME: Formal Linear Algebra Methods Environment. ACM Trans. Math. Softw. 27 4 (Dec. 2001) 422\u2013455. https:\/\/doi.org\/10.1145\/504210.50421310.1145\/504210.504213","DOI":"10.1145\/504210.504213"},{"key":"e_1_3_1_23_1","doi-asserted-by":"crossref","unstructured":"Yuka Ikarashi Gilbert Louis Bernstein Alex Reinking Hasan Genc and Jonathan Ragan-Kelley. 2022. Exocompilation for productive programming of hardware accelerators. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation. 703\u2013718.","DOI":"10.1145\/3519939.3523446"},{"issue":"1967","key":"e_1_3_1_24_1","first-page":"563","article-title":"The Organization of Computations for Uniform Recurrence Equations","volume":"3","author":"Karp Richard M","year":"1967","unstructured":"Richard M Karp, Raymond E Miller, and Shmuel Winograd. 1967. The Organization of Computations for Uniform Recurrence Equations. 7. ACM 14, 3 (1967), 563\u2013590.","journal-title":"7. ACM 14"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","unstructured":"Fredrik Kjolstad 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_1_26_1","doi-asserted-by":"publisher","unstructured":"Fredrik Kjolstad Shoaib Kamil Stephen Chou David Lugato and Saman Amarasinghe. 2017. The tensor algebra compiler. Proc. ACM Program. Lang. 1 OOPSLA Article 77 (Oct. 2017) 29 pages. https:\/\/doi.org\/10.1145\/313390110.1145\/3133901","DOI":"10.1145\/3133901"},{"key":"e_1_3_1_27_1","unstructured":"Fredrik Berg Kj\u00f8lstad. 2020. Sparse tensor algebra compilation. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3458817.3476167"},{"key":"e_1_3_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/360827.360844"},{"key":"e_1_3_1_30_1","doi-asserted-by":"crossref","unstructured":"Chuck L Lawson Richard J. Hanson David R Kincaid and Fred T. Krogh. 1979. Basic linear algebra subprograms for Fortran usage. ACM Transactions on Mathematical Software (TOMS) 5 3 (1979) 308\u2013323.","DOI":"10.1145\/355841.355847"},{"key":"e_1_3_1_31_1","doi-asserted-by":"publisher","unstructured":"Vijay Menon Keshav Pingali and Nikolay Mateev. 2003. Fractal symbolic analysis. ACM Trans. Program. Lang. Syst. 25 6 (Nov. 2003) 776\u2013813. https:\/\/doi.org\/10.1145\/945885.94588810.1145\/945885.945888","DOI":"10.1145\/945885.945888"},{"key":"e_1_3_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(88)90035-X"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(88)90036-1"},{"key":"e_1_3_1_34_1","unstructured":"E Peise and P Bientinesi. 2016. Recursive algorithms for dense linear algebra: the ReLAPACK collection. ArXiv e-prints (Feb. arXiv preprint cs.MS\/1602.06763 2016)."},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","unstructured":"Ryan Senanayake Changwan Hong Ziheng Wang Amalee Wilson Stephen Chou Shoaib Kamil Saman Amarasinghe and Fredrik Kjolstad. 2020. A Sparse Iteration Space Transformation Framework for Sparse Tensor Algebra. Proc. ACM Program. Lang. 4 OOPSLA Article 158 (Nov. 2020) 30 pages. https:\/\/doi.org\/10.1145\/342822610.1145\/3428226","DOI":"10.1145\/3428226"},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","unstructured":"Shiv Sundram Muhammad Usman Tariq and Fredrik Kjolstad. 2024. Compiling Recurrences over Dense and Sparse Arrays. Proc. ACM Program. Lang. 8 OOPSLA1 Article 103 (April 2024) 26 pages. https:\/\/doi.org\/10.1145\/364982010.1145\/3649820","DOI":"10.1145\/3649820"},{"key":"e_1_3_1_37_1","doi-asserted-by":"publisher","unstructured":"Muhammad Usman Tariq Shiv Sundram and Fredrik Kjolstad. 2025. REPTILE artifact. https:\/\/doi.org\/10.5281\/zenodo.1576169110.5281\/zenodo.15761691","DOI":"10.5281\/zenodo.15761691"},{"key":"e_1_3_1_38_1","doi-asserted-by":"crossref","unstructured":"Ruiqin Tian Luanzheng Guo Jiajia Li Bin Ren and Gokcen Kestor. 2021. A High Performance Sparse Tensor Algebra Compiler in MLIR. (12 2021).","DOI":"10.1109\/LLVMHPC54804.2021.00009"},{"key":"e_1_3_1_39_1","doi-asserted-by":"publisher","unstructured":"Field G. Van Zee Tyler M. Smith Bryan Marker Tze Meng Low Robert A. Van De Geijn Francisco D.Igual Mikhail Smelyanskiy Xianyi Zhang Michael Kistler Vernon Austel John A. Gunnels and Lee Killough. 2016. The BLIS Framework: Experiments in Portability. ACM Trans. Math. Softw. 42 2 Article 12 (June 2016) 19 pages. https:\/\/doi.org\/10.1145\/275556110.1145\/2755561","DOI":"10.1145\/2755561"},{"key":"e_1_3_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764454"},{"key":"e_1_3_1_41_1","doi-asserted-by":"crossref","unstructured":"Endong Wang Qing Zhang Bo Shen Guangyong Zhang Xiaowei Lu Qing Wu Yajuan Wang Endong Wang Qing Zhang Bo Shen et al. 2014. Intel math kernel library. High-Performance Computing on the Intel\u00ae Xeon Phi \u2122 : How to Fully Exploit MIC Architectures (2014) 167\u2013188.","DOI":"10.1007\/978-3-319-06486-4_7"},{"key":"e_1_3_1_42_1","doi-asserted-by":"crossref","unstructured":"R Clint Whaley Antoine Petitet and Jack J Dongarra. 2001. Automated empirical optimizations of software and the ATLAS project. Parallel computing 27 1-2 (2001) 3\u201335.","DOI":"10.1016\/S0167-8191(00)00087-9"},{"key":"e_1_3_1_43_1","doi-asserted-by":"publisher","unstructured":"Tobias Wicky Edgar Solomonik and Torsten Hoefler. 2017. Communication-Avoiding Parallel Algorithms for Solving Triangular Systems of Linear Equations. In 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 678\u2013687. https:\/\/doi.org\/10.1109\/IPDPS.2017.10410.1109\/IPDPS.2017.104","DOI":"10.1109\/IPDPS.2017.104"},{"key":"e_1_3_1_44_1","unstructured":"Qing Yi and Ken Kennedy. 2002. Transforming complex loop nests for locality. Ph. D. Dissertation. USA. AAI3047379."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763074","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763074","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:07:44Z","timestamp":1784196464000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763074"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":43,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2025,10,9]]}},"alternative-id":["10.1145\/3763074"],"URL":"https:\/\/doi.org\/10.1145\/3763074","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"}}]}}