{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,22]],"date-time":"2026-07-22T23:21:01Z","timestamp":1784762461604,"version":"3.55.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T00:00:00Z","timestamp":1728345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2216978, CCF-1919197 and CCF-19085"],"award-info":[{"award-number":["CCF-2216978, CCF-1919197 and CCF-19085"]}],"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":[[2024,10,8]]},"abstract":"<jats:p>Automated code generation and performance enhancements for sparse tensor algebra have become essential in many real-world applications, such as quantum computing, physical simulations, computational chemistry, and machine learning. General sparse tensor algebra compilers are not always versatile enough to generate asymptotically optimal code for sparse tensor contractions. This paper shows how to generate asymptotically better schedules for complex sparse tensor expressions using kernel fission and fusion. We present generalized loop restructuring transformations to reduce asymptotic time complexity and memory footprint.<\/jats:p>\n                  <jats:p>Furthermore, we present an auto-scheduler that uses a partially ordered set (poset)-based cost model that uses both time and auxiliary memory complexities to prune the search space of schedules. In addition, we highlight the use of Satisfiability Module Theory (SMT) solvers in sparse auto-schedulers to approximate the Pareto frontier of better schedules to the smallest number of possible schedules, with user-defined constraints available at compile-time. Finally, we show that our auto-scheduler can select better-performing schedules and generate code for them. Our results show that the auto-scheduler provided schedules achieve orders of-magnitude speedup compared to the code generated by the Tensor Algebra Compiler (TACO) for several computations on different real-world tensors.<\/jats:p>","DOI":"10.1145\/3689730","type":"journal-article","created":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T03:23:04Z","timestamp":1728357784000},"page":"527-556","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["SparseAuto: An Auto-scheduler for Sparse Tensor Computations using Recursive Loop Nest Restructuring"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3500-7547","authenticated-orcid":false,"given":"Adhitha","family":"Dias","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-5572-726X","authenticated-orcid":false,"given":"Logan","family":"Anderson","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6384-062X","authenticated-orcid":false,"given":"Kirshanthan","family":"Sundararajah","sequence":"additional","affiliation":[{"name":"Virginia Tech, Blacksburg, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8334-8106","authenticated-orcid":false,"given":"Artem","family":"Pelenitsyn","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6827-345X","authenticated-orcid":false,"given":"Milind","family":"Kulkarni","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,10,8]]},"reference":[{"key":"e_1_3_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2016.05.302"},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523442"},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2006.1639717"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/00268970500275780"},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3544559"},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/165939.166023"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00066"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276493"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2003.1213121"},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","unstructured":"Adhitha Dias Logan Anderson Kirshanthan Sundararajah Artem Pelenitsyn and Milind Kulkarni. 2024. SparseAuto: An Auto-Scheduler for Sparse Tensor Computations Using Recursive Loop Nest Restructuring. https:\/\/doi.org\/10.5281\/zenodo.12764370 10.5281\/zenodo.12764370","DOI":"10.5281\/zenodo.12764370"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3524059.3532386"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2021-03-15-410"},{"key":"e_1_3_1_15_1","first-page":"1024","article-title":"Inductive representation learning on large graphs","volume":"30","author":"Hamilton Will","year":"2017","unstructured":"Will Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems 30 (2017), 1024\u20131034.","journal-title":"Advances in neural information processing systems"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1021\/jp9051215"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1021\/jp034596z"},{"key":"e_1_3_1_18_1","first-page":"13","article-title":"FeatGraph: A Flexible and Efficient Backend for Graph Neural Network Systems","author":"Hu Yuwei","year":"2020","unstructured":"Yuwei Hu, Zihao Ye, Minjie Wang, Jiali Yu, Da Zheng, Mu Li, Zheng Zhang, Zhiru Zhang, and Yida Wang. 2020. FeatGraph: A Flexible and Efficient Backend for Graph Neural Network Systems. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (Atlanta, Georgia) (SC \u201820). IEEE Press, Article 71, 13 pages.","journal-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (Atlanta, Georgia) (SC \u201820)"},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","unstructured":"Raghavendra Kanakagari and Edgar Solomonik. 2023. Minimum Cost Loop Nests for Contraction of a Sparse Tensor with a Tensor Network. https:\/\/doi.org\/10.48550\/arXiv.2307.05740 10.48550\/arXiv.2307.05740","DOI":"10.48550\/arXiv.2307.05740"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2019.8661182"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/3314872.3314894"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133901"},{"key":"e_1_3_1_23_1","article-title":"Tensor Contraction Layers for Parsimonious Deep Nets","author":"Kossaifi Jean","year":"2017","unstructured":"Jean Kossaifi, Aran Khanna, Zachary Lipton, Tommaso Furlanello, and Anima Anandkumar. 2017. Tensor Contraction Layers for Parsimonious Deep Nets. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops.","journal-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/646662.699553"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626497000176"},{"key":"e_1_3_1_26_1","unstructured":"Alan LaMielle and Michelle Mills Strout. 2010. Enabling Code Generation within the Sparse Polyhedral Framework."},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","unstructured":"Richard Lippmann David Fried Isaac Graf Joshua Haines Kristopher Kendall David McClung Dan Weber Seth Webster Daniel Wyschogrod Robert Cunningham and Marc Zissman. 2000. Evaluating intrusion detection systems: the 1998 DARPA off-line intrusion detection evaluation. 2 (02 2000) 12 \u2013 26 vol.2. https:\/\/doi.org\/10.1109\/DISCEX.2000.821506 10.1109\/DISCEX.2000.821506","DOI":"10.1109\/DISCEX.2000.821506"},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447818.3460355"},{"key":"e_1_3_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3437801.3441581"},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/050644756"},{"key":"e_1_3_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2015.106"},{"key":"e_1_3_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS49936.2021.00034"},{"key":"e_1_3_1_33_1","article-title":"Review of tensor network contraction approaches","author":"Ran Shi-Ju","year":"2017","unstructured":"Shi-Ju Ran, Emanuele Tirrito, Cheng Peng, Xi Chen, Gang Su, and Maciej Lewenstein. 2017. Review of tensor network contraction approaches. arXiv preprint arXiv:1708.09213 (2017).","journal-title":"arXiv preprint arXiv:1708.09213"},{"key":"e_1_3_1_34_1","doi-asserted-by":"publisher","unstructured":"Shi-Ju Ran Emanuele Tirrito Cheng Peng Xi Chen Luca Tagliacozzo Gang Su and Maciej Lewenstein. 2020. Tensor Network Contractions: Methods and Applications to Quantum Many-Body Systems. Springer Nature. https:\/\/doi.org\/10.1007\/978-3-030-34489-4 10.1007\/978-3-030-34489-4","DOI":"10.1007\/978-3-030-34489-4"},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","unstructured":"Luca Rossi Nesreen K. Ahmed Jennifer Neville and Keith Henderson. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. 42 1 (2015). https:\/\/doi.org\/10.1145\/2740908 10.1145\/2740908","DOI":"10.1145\/2740908"},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2005.35"},{"key":"e_1_3_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428226"},{"key":"e_1_3_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_3_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2018.2857721"},{"key":"e_1_3_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2016.02.004"},{"key":"e_1_3_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/LLVMHPC54804.2021.00009"},{"key":"e_1_3_1_42_1","doi-asserted-by":"publisher","unstructured":"Ledyard R. Tucker. 1966. Some Mathematical Notes on Three-Mode Factor Analysis. Psychometrika 31 3 (1966) 279\u2013311. https:\/\/doi.org\/10.1007\/BF02289464 10.1007\/BF02289464","DOI":"10.1007\/BF02289464"},{"key":"e_1_3_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738003"},{"key":"e_1_3_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3582016.3582047"},{"key":"e_1_3_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3559009.3569685"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689730","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3689730","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T09:07:44Z","timestamp":1770196064000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689730"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,8]]},"references-count":44,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2024,10,8]]}},"alternative-id":["10.1145\/3689730"],"URL":"https:\/\/doi.org\/10.1145\/3689730","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,8]]},"assertion":[{"value":"2024-04-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}