{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T16:50:00Z","timestamp":1771951800676,"version":"3.50.1"},"reference-count":83,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,12,16]],"date-time":"2022-12-16T00:00:00Z","timestamp":1671148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Exascale Computing Project","award":["17-SC-20-SC"],"award-info":[{"award-number":["17-SC-20-SC"]}]},{"name":"National Science Foundation","award":["CCF-2107556"],"award-info":[{"award-number":["CCF-2107556"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2023,3,31]]},"abstract":"<jats:p>\n            This article presents a code generator for sparse tensor contraction computations. It leverages a mathematical representation of loop nest computations in the sparse polyhedral framework (SPF), which extends the polyhedral model to support non-affine computations, such as those that arise in sparse tensors. SPF is extended to perform layout specification, optimization, and code generation of sparse tensor code: (1) We develop a polyhedral layout specification that decouples iteration spaces for layout and computation; and (2) we develop efficient co-iteration of sparse tensors by combining polyhedra scanning over the layout of one sparse tensor with the synthesis of code to\n            <jats:italic>find<\/jats:italic>\n            corresponding elements in other tensors through an SMT solver.\n          <\/jats:p>\n          <jats:p>We compare the generated code with that produced by a state-of-the-art tensor compiler, TACO. We achieve on average 1.63\u00d7 faster parallel performance than TACO on sparse-sparse co-iteration and describe how to improve that to 2.72\u00d7 average speedup by switching the find algorithms. We also demonstrate that decoupling iteration spaces of layout and computation enables additional layout and computation combinations to be supported.<\/jats:p>","DOI":"10.1145\/3566054","type":"journal-article","created":{"date-parts":[[2022,10,25]],"date-time":"2022-10-25T13:24:21Z","timestamp":1666704261000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Polyhedral Specification and Code Generation of Sparse Tensor Contraction with Co-iteration"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6347-7135","authenticated-orcid":false,"given":"Tuowen","family":"Zhao","sequence":"first","affiliation":[{"name":"University of Utah, Salt Lake City, UT, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5944-1570","authenticated-orcid":false,"given":"Tobi","family":"Popoola","sequence":"additional","affiliation":[{"name":"Boise State University, Boise, ID, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3058-7573","authenticated-orcid":false,"given":"Mary","family":"Hall","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, UT, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1764-385X","authenticated-orcid":false,"given":"Catherine","family":"Olschanowsky","sequence":"additional","affiliation":[{"name":"Boise State University, Boise, ID, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7646-4766","authenticated-orcid":false,"given":"Michelle","family":"Strout","sequence":"additional","affiliation":[{"name":"University of Arizona, Tucson, AZ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,12,16]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"265","volume-title":"Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201916)","author":"Abadi Martin","year":"2016","unstructured":"Martin Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. 2016. TensorFlow: A system for large-scale machine learning. In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201916). 265\u2013283."},{"key":"e_1_3_2_3_2","unstructured":"NVIDIA Corporation & affiliates. 2021. Parallel Thread Execution ISA Version 7.5. Retrieved from https:\/\/docs.nvidia.com\/cuda\/parallel-thread-execution\/index.html."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/FMCAD.2013.6679385"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2697055"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/109625.109631"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1080\/00268970500275780"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314615"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-046-9_8"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2019.8661197"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11970-5_16"},{"key":"e_1_3_2_12_2","volume-title":"Compiler Support for Sparse Matrix Computations","author":"Bik Aart J. C.","year":"1996","unstructured":"Aart J. C. Bik. 1996. Compiler Support for Sparse Matrix Computations. PhD Dissertation. Leiden University."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/165939.166023"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375595"},{"key":"e_1_3_2_15_2","first-page":"427","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"Bradley Aaron R.","year":"2006","unstructured":"Aaron R. Bradley, Zohar Manna, and Henny B. Sipma. 2006. What\u2019s decidable about arrays? In Verification, Model Checking, and Abstract Interpretation. Springer Berlin, 427\u2013442."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2008.4536313"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487677"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254123"},{"key":"e_1_3_2_19_2","volume-title":"CHiLL: A Framework for Composing High-level Loop Transformations","author":"Chen Chun","year":"2008","unstructured":"Chun Chen, Jacqueline Chame, and Mary Hall. 2008. CHiLL: A Framework for Composing High-level Loop Transformations. Technical Report. Citeseer."},{"key":"e_1_3_2_20_2","first-page":"579","volume-title":"Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation (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 (OSDI\u201918). USENIX Association, 579\u2013594."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276493"},{"key":"e_1_3_2_22_2","article-title":"Low-rank tensor networks for dimensionality reduction and large-scale optimization problems: Perspectives and challenges PART 1","author":"Cichocki A.","year":"2016","unstructured":"A. Cichocki, N. Lee, I. V. Oseledets, A. Phan, Q. Zhao, and D. Mandic. 2016. Low-rank tensor networks for dimensionality reduction and large-scale optimization problems: Perspectives and challenges PART 1. ArXiv E-prints (Sept.2016). arxiv:1609.00893","journal-title":"ArXiv E-prints"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/SHPCC.1994.296675"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3322125"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1002\/andp.19163540702"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407931"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01379404"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-006-0012-3"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.1998.727179"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2743016"},{"key":"e_1_3_2_34_2","unstructured":"Ga\u00ebl Guennebaud Beno\u00eet Jacob et\u00a0al. 2010. Eigen v3. Retrieved from http:\/\/eigen.tuxfamily.org."},{"key":"e_1_3_2_35_2","article-title":"Compilation of sparse array programming models","volume":"5","author":"Hentry Rawn","year":"2021","unstructured":"Rawn Hentry, Olivia Hsu, Rohan Yadav, Stephen Chou, Kunle Olukotun, Saman Amarasinghe, and Fredrik Kjolstad. 2021. Compilation of sparse array programming models. Proc. ACM Program. Lang 5, OOPSLA (Oct.2021).","journal-title":"Proc. ACM Program. Lang"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.5555\/645455.653756"},{"key":"e_1_3_2_37_2","unstructured":"Intel Corporation. 2022. Intel oneAPI Math Kernel Library. Retrieved from https:\/\/www.intel.com\/content\/www\/us\/en\/developer\/tools\/oneapi\/onemkl.html."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73588"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113355"},{"key":"e_1_3_2_40_2","volume-title":"Optimization within a Unified Transformation Framework","author":"Kelly Wayne","year":"1998","unstructured":"Wayne Kelly. 1998. Optimization within a Unified Transformation Framework. PhD Dissertation. University of Maryland."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2400682.2400690"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133901"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1137\/07070111x"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/263580.263630"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.5555\/866909"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0002751"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2401575"},{"key":"e_1_3_2_48_2","unstructured":"Chris Lattner Mehdi Amini Uday Bondhugula Albert Cohen Andy Davis Jacques Pienaar River Riddle Tatiana Shpeisman Nicolas Vasilache and Oleksandr Zinenko. 2020. MLIR: A Compiler Infrastructure for the End of Moore\u2019s Law. arxiv:2002.11054 [cs.PL]"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(98)00029-5"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3330345.3330366"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/335231.335240"},{"key":"e_1_3_2_52_2","unstructured":"Asit Mishra Jorge Albericio Latorre Jeff Pool Darko Stosic Dusan Stosic Ganesh Venkatesh Chong Yu and Paulius Micikevicius. 2021. Accelerating Sparse Deep Neural Networks. arxiv:2104.08378 [cs.LG]"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-34627-0_7"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314646"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48319-5_14"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/365151.365152"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007554627716"},{"key":"e_1_3_2_58_2","first-page":"179","volume-title":"Proceedings of the International Conference on Parallel Processing","author":"Ramanujam J.","year":"1992","unstructured":"J. Ramanujam and P. Sadayappan. 1992. Tiling of iteration spaces for multicomputers. In Proceedings of the International Conference on Parallel Processing. 179\u2013186."},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01454201"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/2967938.2967943"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3428226"},{"key":"e_1_3_2_63_2","volume-title":"Proceedings of the Mid-Atlantic Student Workshop on Programming Languages and Systems (MASPLAS)","author":"Shen Tina","year":"1998","unstructured":"Tina Shen and David Wonnacott. 1998. Automatic memory remapping for time skewing. In Proceedings of the Mid-Atlantic Student Workshop on Programming Languages and Systems (MASPLAS)."},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2017.2690524"},{"key":"e_1_3_2_65_2","volume-title":"FROSTT: The Formidable Repository of Open Sparse Tensors and Tools","author":"Smith Shaden","year":"2017","unstructured":"Shaden Smith, Jee W. Choi, Jiajia Li, Richard Vuduc, Jongsoo Park, Xing Liu, and George Karypis. 2017. FROSTT: The Formidable Repository of Open Sparse Tensors and Tools. Retrieved from http:\/\/frostt.io\/."},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.27"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168907"},{"key":"e_1_3_2_68_2","volume-title":"A Relational Approach to the Automatic Generation of Sequential Sparse Matrix Codes","author":"Stodghill Paul Vinson","year":"1997","unstructured":"Paul Vinson Stodghill. 1997. A Relational Approach to the Automatic Generation of Sequential Sparse Matrix Codes. Ph. D. Dissertation. Cornell University."},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781142"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/291069.291015"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2018.2857721"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2016.02.004"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/1286821.1286825"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1109\/LLVMHPC54804.2021.00009"},{"key":"e_1_3_2_75_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cpc.2010.04.018"},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19595-2_8"},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.1145\/1183401.1183448"},{"key":"e_1_3_2_78_2","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738003"},{"key":"e_1_3_2_79_2","doi-asserted-by":"publisher","DOI":"10.5555\/3014904.3014959"},{"key":"e_1_3_2_80_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686-2"},{"key":"e_1_3_2_81_2","article-title":"Deep graph library: Towards efficient and scalable deep learning on graphs","volume":"1909","author":"Wang Minjie","year":"2019","unstructured":"Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, Ziyue Huang, Qipeng Guo, Hao Zhang, Haibin Lin, Junbo Zhao, Jinyang Li, Alexander J. Smola, and Zheng Zhang. 2019. Deep graph library: Towards efficient and scalable deep learning on graphs. CoRR abs\/1909.01315 (2019).","journal-title":"CoRR"},{"key":"e_1_3_2_82_2","doi-asserted-by":"publisher","DOI":"10.1145\/113445.113449"},{"key":"e_1_3_2_83_2","doi-asserted-by":"publisher","DOI":"10.1145\/76263.76337"},{"key":"e_1_3_2_84_2","doi-asserted-by":"publisher","DOI":"10.1145\/3178372.3179509"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3566054","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3566054","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:33Z","timestamp":1750183713000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3566054"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,16]]},"references-count":83,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3,31]]}},"alternative-id":["10.1145\/3566054"],"URL":"https:\/\/doi.org\/10.1145\/3566054","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,16]]},"assertion":[{"value":"2022-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-30","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}