{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:13:53Z","timestamp":1773278033146,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"SRC","award":["JUMP 2.0 PRISM"],"award-info":[{"award-number":["JUMP 2.0 PRISM"]}]},{"name":"NSF","award":["CCF-2216964, GRFP"],"award-info":[{"award-number":["CCF-2216964, GRFP"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,4,29]]},"abstract":"<jats:p>We present a framework for compiling recurrence equations into native code. In our framework, users specify a system of recurrences, the types of data structures that store inputs and outputs, and scheduling commands for optimization. Our compiler then lowers these specifications into native code that respects the dependencies in the recurrence equations. Our compiler can generate code over both sparse and dense data structures, and determines if the recurrence system is solvable with the provided scheduling primitives. We evaluate the performance and correctness of the generated code on several recurrences, from domains as diverse as dense and sparse matrix solvers, dynamic programming, graph problems, and sparse tensor algebra. We demonstrate that the generated code has competitive performance to hand-optimized implementations in libraries. However, these handwritten libraries target specific recurrences, specific data structures, and specific optimizations. Our system, on the other hand, automatically generates implementations from recurrences, data formats, and schedules, giving our system more generality than library approaches.<\/jats:p>","DOI":"10.1145\/3649820","type":"journal-article","created":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T17:53:50Z","timestamp":1714413230000},"page":"250-275","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Compiling Recurrences over Dense and Sparse Arrays"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5228-1295","authenticated-orcid":false,"given":"Shiv","family":"Sundram","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-1588-0271","authenticated-orcid":false,"given":"Muhammad Usman","family":"Tariq","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2267-903X","authenticated-orcid":false,"given":"Fredrik","family":"Kjolstad","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,4,29]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Dynamic programming","author":"Bellman Richard E","unstructured":"Richard E Bellman. 2010. Dynamic programming. Princeton university press."},{"key":"e_1_2_1_2_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."},{"key":"e_1_2_1_3_1","volume-title":"The Boost Graph Library: User Guide and Reference Manual","year":"2017","unstructured":"Boost. 2002. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley Longman Publishing Co., Inc., USA. isbn:0201729148"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 7th conference on high-performance graphics. 85\u201394","author":"Chaurasia Gaurav","year":"2015","unstructured":"Gaurav Chaurasia, Jonathan Ragan-Kelley, Sylvain Paris, George Drettakis, and Fredo Durand. 2015. Compiling high performance recursive filters. In Proceedings of the 7th conference on high-performance graphics. 85\u201394."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1\u201313","author":"Cheshmi Kazem","year":"2017","unstructured":"Kazem Cheshmi, Shoaib Kamil, Michelle Mills Strout, and Maryam Mehri Dehnavi. 2017. Sympiler: transforming sparse matrix codes by decoupling symbolic analysis. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1\u201313."},{"key":"e_1_2_1_6_1","volume-title":"Proc. ACM Program. Lang., 2, OOPSLA","author":"Chou Stephen","year":"2018","unstructured":"Stephen Chou, Fredrik Kjolstad, and Saman Amarasinghe. 2018. Format Abstraction for Sparse Tensor Algebra Compilers. Proc. ACM Program. Lang., 2, OOPSLA (2018), Article 123, oct, 30 pages. https:\/\/doi.org\/10.1145\/3276493 10.1145\/3276493"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-016-0930-z"},{"key":"e_1_2_1_8_1","unstructured":"T. A. Davis. 2006. CXSparse: a Concise eXtended Sparse Matrix Package. https:\/\/github.com\/DrTimothyAldenDavis\/SuiteSparse\/tree\/dev\/CXSparse"},{"key":"e_1_2_1_9_1","volume-title":"Direct Methods for Sparse Linear Systems","author":"Davis T. A.","unstructured":"T. A. Davis. 2006. Direct Methods for Sparse Linear Systems. SIAM, Philadelphia, PA."},{"key":"e_1_2_1_10_1","volume-title":"Annual Meeting of the Association for Computational Linguistics.","author":"Eisner Jason","unstructured":"Jason Eisner, Eric Goldlust, and Noah A. Smith. 2004. Dyna: a declarative language for implementing dynamic programs. In Annual Meeting of the Association for Computational Linguistics."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF01407931","article-title":"Dataflow Analysis of Array and Scalar References","volume":"20","author":"Feautrier Paul","year":"1991","unstructured":"Paul Feautrier. 1991. Dataflow Analysis of Array and Scalar References. International Journal of Parallel Programming, 20, 1 (1991), 23\u201353.","journal-title":"International Journal of Parallel Programming"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Gautam and S. Rajopadhye. 2006. Simplifying Reductions. SIGPLAN Not. 41 1 (2006) jan 30\u201341. issn:0362-1340","DOI":"10.1145\/1111320.1111041"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1137\/S0895479887139455","article-title":"Predicting structure in sparse matrix computations","volume":"15","author":"Gilbert John R","year":"1994","unstructured":"John R Gilbert. 1994. Predicting structure in sparse matrix computations. SIAM J. Matrix Anal. Appl., 15, 1 (1994), 62\u201379.","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/504210.504213"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the ACM on Programming Languages, 5, OOPSLA","author":"Henry Rawn","year":"2021","unstructured":"Rawn Henry, Olivia Hsu, Rohan Yadav, Stephen Chou, Kunle Olukotun, Saman Amarasinghe, and Fredrik Kjolstad. 2021. Compilation of sparse array programming models. Proceedings of the ACM on Programming Languages, 5, OOPSLA (2021), 1\u201329."},{"key":"e_1_2_1_16_1","unstructured":"Liang Huang. 2008. Advanced dynamic programming in semiring and hypergraph frameworks. Coling 2008: Advanced Dynamic Programming in Computational Linguistics: Theory Algorithms and Applications-Tutorial notes 1\u201318."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1145\/321406.321418","article-title":"The Organization of Computations for Uniform Recurrence Equations","volume":"14","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. J. ACM, 14, 3 (1967), 563\u2013590.","journal-title":"J. ACM"},{"key":"e_1_2_1_18_1","volume-title":"2016 IEEE High Performance Extreme Computing Conference (HPEC). 1\u20139.","author":"Kepner Jeremy","year":"2016","unstructured":"Jeremy Kepner, Peter Aaltonen, David Bader, Aydin Bulu\u00e7, Franz Franchetti, John Gilbert, Dylan Hutchison, Manoj Kumar, Andrew Lumsdaine, and Henning Meyerhenke. 2016. Mathematical foundations of the GraphBLAS. In 2016 IEEE High Performance Extreme Computing Conference (HPEC). 1\u20139."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 2019 IEEE\/ACM International Symposium on Code Generation and Optimization (CGO","author":"Kjolstad Fredrik","year":"2019","unstructured":"Fredrik Kjolstad, Peter Ahrens, Shoaib Kamil, and Saman Amarasinghe. 2019. Tensor Algebra Compilation with Workspaces. In Proceedings of the 2019 IEEE\/ACM International Symposium on Code Generation and Optimization (CGO 2019). IEEE Press, 180\u2013192. isbn:9781728114361"},{"key":"e_1_2_1_20_1","volume-title":"Proc. ACM Program. Lang., 1, OOPSLA","author":"Kjolstad Fredrik","year":"2017","unstructured":"Fredrik Kjolstad, Shoaib Kamil, Stephen Chou, David Lugato, and Saman P. Amarasinghe. 2017. The tensor algebra compiler. Proc. ACM Program. Lang., 1, OOPSLA (2017), 77:1\u201377:29."},{"key":"e_1_2_1_21_1","volume-title":"Sparse tensor algebra compilation. Ph. D. Dissertation","author":"Kj\u00f8lstad Fredrik Berg","unstructured":"Fredrik Berg Kj\u00f8lstad. 2020. Sparse tensor algebra compilation. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_2_1_22_1","volume-title":"Encyclopedia of Computer Science. 1017\u20131031.","author":"Kowalski Robert","unstructured":"Robert Kowalski and Keith L Clark. 2003. Logic programming. In Encyclopedia of Computer Science. 1017\u20131031."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/360827.360844","article-title":"The Parallel Execution of DO","volume":"17","author":"Lamport Leslie","year":"1974","unstructured":"Leslie Lamport. 1974. The Parallel Execution of DO Loops. Commun. ACM, 17, 2 (1974), 83\u201393.","journal-title":"Loops. Commun. ACM"},{"key":"e_1_2_1_24_1","unstructured":"R Sherman Lehman. 1960. DYNAMIC PROGRAMMING AND GAUSSIAN ELIMINATION.. RAND CORP SANTA MONICA CALIF."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1145\/6497.6499","article-title":"A compact row storage scheme for Cholesky factors using elimination trees","volume":"12","author":"Liu Joseph W","year":"1986","unstructured":"Joseph W Liu. 1986. A compact row storage scheme for Cholesky factors using elimination trees. ACM Transactions on Mathematical Software (TOMS), 12, 2 (1986), 127\u2013148.","journal-title":"ACM Transactions on Mathematical Software (TOMS)"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1137\/1034004","article-title":"The Multifrontal Method for Sparse Matrix Solution: Theory and Practice","volume":"34","author":"Liu Joseph W. H.","year":"1992","unstructured":"Joseph W. H. Liu. 1992. The Multifrontal Method for Sparse Matrix Solution: Theory and Practice. SIAM Rev., 34 (1992), 82\u2013109.","journal-title":"SIAM Rev."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1023\/B:IJPP.0000042084.99636.a0","article-title":"Look left, look right, look left again: An application of fractal symbolic analysis to linear algebra code restructuring","volume":"32","author":"Menon Vijay","year":"2004","unstructured":"Vijay Menon and Keshav Pingali. 2004. Look left, look right, look left again: An application of fractal symbolic analysis to linear algebra code restructuring. International Journal of Parallel Programming, 32 (2004), 501\u2013523.","journal-title":"International Journal of Parallel Programming"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0914048"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0167-8191(88)90035-X","article-title":"The ijk forms of factorization methods I. Vector computers","volume":"7","author":"Ortega James M.","year":"1988","unstructured":"James M. Ortega. 1988. The ijk forms of factorization methods I. Vector computers. Parallel Comput., 7 (1988), 135\u2013147.","journal-title":"Parallel Comput."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0167-8191(88)90036-1","article-title":"The ijk forms of factorization methods II. Vector computers","volume":"7","author":"Ortega James M.","year":"1988","unstructured":"James M. Ortega. 1988. The ijk forms of factorization methods II. Vector computers. Parallel Comput., 7 (1988), 149\u2013162.","journal-title":"Parallel Comput."},{"key":"e_1_2_1_31_1","unstructured":"Louis-Noel Pouchet. 2016. PolyBench. http:\/\/web.cs.ucla.edu\/~pouchet\/software\/polybench\/"},{"key":"e_1_2_1_32_1","volume-title":"ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI \u201913","author":"Ragan-Kelley Jonathan","year":"2013","unstructured":"Jonathan Ragan-Kelley, Connelly Barnes, Andrew Adams, Sylvain Paris, Fr\u00e9do Durand, and Saman P. Amarasinghe. 2013. Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI \u201913, Seattle, WA, USA, June 16-19, 2013, Hans-Juergen Boehm and Cormac Flanagan (Eds.). ACM, 519\u2013530."},{"key":"e_1_2_1_33_1","first-page":"1","article-title":"M\u00e9thodes de calcul diff\u00e9rentiel absolu et leurs applications","volume":"54","author":"Ricci MMG","year":"1900","unstructured":"MMG Ricci and Tullio Levi-Civita. 1900. M\u00e9thodes de calcul diff\u00e9rentiel absolu et leurs applications. Math. Ann., 54, 1-2 (1900), 125\u2013201.","journal-title":"Math. Ann."},{"key":"e_1_2_1_34_1","volume-title":"Bellman\u2019s GAP\u2014a language and compiler for dynamic programming in sequence analysis. Bioinformatics, 29, 5","author":"Sauthoff Georg","year":"2013","unstructured":"Georg Sauthoff, Mathias M\u00f6hl, Stefan Janssen, and Robert Giegerich. 2013. Bellman\u2019s GAP\u2014a language and compiler for dynamic programming in sequence analysis. Bioinformatics, 29, 5 (2013), 01, 551\u2013560. issn:1367-4803 arxiv:https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/5\/551\/16919063\/btt022.pdf."},{"key":"e_1_2_1_35_1","volume-title":"Proc. ACM Program. Lang., 4, OOPSLA","author":"Senanayake Ryan","year":"2020","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 (2020), Article 158, nov, 30 pages. https:\/\/doi.org\/10.1145\/3428226 10.1145\/3428226"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","first-page":"1921","DOI":"10.1109\/JPROC.2018.2857721","article-title":"The sparse polyhedral framework: Composing compiler-generated inspector-executor code","volume":"106","author":"Strout Michelle Mills","year":"2018","unstructured":"Michelle Mills Strout, Mary Hall, and Catherine Olschanowsky. 2018. The sparse polyhedral framework: Composing compiler-generated inspector-executor code. Proc. IEEE, 106, 11 (2018), 1921\u20131934.","journal-title":"Proc. IEEE"},{"key":"e_1_2_1_37_1","volume-title":"Artifact for OOPSLA 2024 Paper: Compiling Recurrences over Dense and Sparse Arrays (version 1). https:\/\/doi.org\/10","author":"Sundram Shiv","year":"2024","unstructured":"Shiv Sundram, Muhammad Usman Tariq, and Fredrik Kjolstad. 2024. Artifact for OOPSLA 2024 Paper: Compiling Recurrences over Dense and Sparse Arrays (version 1). https:\/\/doi.org\/10.5281\/zenodo.10774458 10.5281\/zenodo.10774458"},{"key":"e_1_2_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.","DOI":"10.1109\/LLVMHPC54804.2021.00009"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1967.1054010"},{"key":"e_1_2_1_40_1","volume-title":"Proc. ACM Program. Lang., 5, POPL","author":"Yang Cambridge","year":"2021","unstructured":"Cambridge Yang, Eric Atkinson, and Michael Carbin. 2021. Simplifying Dependent Reductions in the Polyhedral Model. Proc. ACM Program. Lang., 5, POPL (2021), Article 20, jan, 33 pages."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems","volume":"3","author":"Ye Zihao","year":"2023","unstructured":"Zihao Ye, Ruihang Lai, Junru Shao, Tianqi Chen, and Luis Ceze. 2023. SparseTIR: Composable abstractions for sparse compilation in deep learning. In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3. 660\u2013678."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649820","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3649820","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:54:06Z","timestamp":1750287246000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649820"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,29]]},"references-count":41,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2024,4,29]]}},"alternative-id":["10.1145\/3649820"],"URL":"https:\/\/doi.org\/10.1145\/3649820","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,29]]},"assertion":[{"value":"2024-04-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}