{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T04:25:08Z","timestamp":1752985508816,"version":"3.41.0"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"1-4","license":[{"start":{"date-parts":[[2023,11,30]],"date-time":"2023-11-30T00:00:00Z","timestamp":1701302400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["U20A20226"],"award-info":[{"award-number":["U20A20226"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Syst."],"published-print":{"date-parts":[[2023,11,30]]},"abstract":"<jats:p>Loop tiling and fusion are two essential transformations in optimizing compilers to enhance the data locality of programs. Existing heuristics either perform loop tiling and fusion in a particular order, missing some of their profitable compositions, or execute ad-hoc implementations for domain-specific applications, calling for a generalized and systematic solution in optimizing compilers.<\/jats:p>\n          <jats:p>\n            In this article, we present a so-called\n            <jats:italic>basteln<\/jats:italic>\n            (an abbreviation for backward slicing of tiled loop nests)\n            <jats:italic>strategy<\/jats:italic>\n            in polyhedral compilation to better model the interplay between loop tiling and fusion. The basteln strategy first groups loop nests by preserving their parallelism\/tilability and next performs rectangular\/parallelogram tiling to the output groups that produce data consumed outside the considered program fragment. The memory footprints required by each tile are then computed, from which the upward exposed data are extracted to determine the tile shapes of the remaining fusion groups. Such a tiling mechanism can construct complex tile shapes imposed by the dependences between these groups, which are further merged by a post-tiling fusion algorithm for enhancing data locality without losing the parallelism\/tilability of the output groups. The basteln strategy also takes into account the amount of redundant computations and the fusion of independent groups, exhibiting a general applicability.\n          <\/jats:p>\n          <jats:p>We integrate the basteln strategy into two optimizing compilers, with one a general-purpose optimizer and the other a domain-specific compiler for deploying deep learning models. The experiments are conducted on CPU, GPU, and a deep learning accelerator to demonstrate the effectiveness of the approach for a wide class of application domains, including deep learning, image processing, sparse matrix computation, and linear algebra. In particular, the basteln strategy achieves a mean speedup of 1.8\u00d7 over cuBLAS\/cuDNN and 1.1\u00d7 over TVM on GPU when used to optimize deep learning models; it also outperforms PPCG and TVM by 11% and 20%, respectively, when generating code for the deep learning accelerator.<\/jats:p>","DOI":"10.1145\/3635305","type":"journal-article","created":{"date-parts":[[2023,12,1]],"date-time":"2023-12-01T11:46:08Z","timestamp":1701431168000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Modeling the Interplay between Loop Tiling and Fusion in Optimizing Compilers Using Affine Relations"],"prefix":"10.1145","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2303-9736","authenticated-orcid":false,"given":"Jie","family":"Zhao","sequence":"first","affiliation":[{"name":"College of Computer Science and Electronic Engineering, Hunan University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6275-2617","authenticated-orcid":false,"given":"Jinchen","family":"Xu","sequence":"additional","affiliation":[{"name":"Information Engineering University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5799-5876","authenticated-orcid":false,"given":"Peng","family":"Di","sequence":"additional","affiliation":[{"name":"Huawei Technologies Co. Ltd., China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9903-8217","authenticated-orcid":false,"given":"Wang","family":"Nie","sequence":"additional","affiliation":[{"name":"Huawei Technologies Co. Ltd., China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4367-0464","authenticated-orcid":false,"given":"Jiahui","family":"Hu","sequence":"additional","affiliation":[{"name":"Huawei Technologies Co. Ltd., China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3486-3731","authenticated-orcid":false,"given":"Yanzhi","family":"Yi","sequence":"additional","affiliation":[{"name":"Huawei Technologies Co. Ltd., China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-5634-398X","authenticated-orcid":false,"given":"Sijia","family":"Yang","sequence":"additional","affiliation":[{"name":"Huawei Technologies Co. Ltd., China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1031-6431","authenticated-orcid":false,"given":"Zhen","family":"Geng","sequence":"additional","affiliation":[{"name":"Huawei Technologies Co. Ltd., China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9744-5676","authenticated-orcid":false,"given":"Renwei","family":"Zhang","sequence":"additional","affiliation":[{"name":"Huawei Technologies Co. Ltd., China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7390-3548","authenticated-orcid":false,"given":"Bojie","family":"Li","sequence":"additional","affiliation":[{"name":"Huawei Technologies Co. Ltd., China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8983-4666","authenticated-orcid":false,"given":"Zhiliang","family":"Gan","sequence":"additional","affiliation":[{"name":"Huawei Technologies Co. Ltd., China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-2487-9402","authenticated-orcid":false,"given":"Xuefeng","family":"Jin","sequence":"additional","affiliation":[{"name":"Huawei Technologies Co. Ltd., China"}]}],"member":"320","published-online":{"date-parts":[[2024,1,15]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI \u201916)","author":"Abadi Mart\u00edn","year":"2016","unstructured":"Mart\u00edn 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. https:\/\/www.usenix.org\/conference\/osdi16\/technical-sessions\/presentation\/abadi"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_2","DOI":"10.1145\/3192366.3192401"},{"doi-asserted-by":"publisher","key":"e_1_3_2_4_2","DOI":"10.1145\/3416510"},{"doi-asserted-by":"publisher","key":"e_1_3_2_5_2","DOI":"10.1145\/3306346.3322967"},{"doi-asserted-by":"publisher","key":"e_1_3_2_6_2","DOI":"10.1145\/2628071.2628092"},{"doi-asserted-by":"publisher","key":"e_1_3_2_7_2","DOI":"10.1109\/CGO.2019.8661197"},{"doi-asserted-by":"publisher","key":"e_1_3_2_8_2","DOI":"10.1016\/S0045-7825(97)00183-7"},{"doi-asserted-by":"publisher","key":"e_1_3_2_9_2","DOI":"10.1109\/PACT.2004.1342537"},{"unstructured":"Somashekaracharya G. Bhaskaracharya Julien Demouth and Vinod Grover. 2020. Automatic kernel generation for Volta tensor cores. arXiv:cs.PL\/2006.12645 (2020).","key":"e_1_3_2_10_2"},{"key":"e_1_3_2_11_2","article-title":"PolyMage Benchmarks","author":"Bondhugula Uday","year":"2015","unstructured":"Uday Bondhugula. 2015. PolyMage Benchmarks. (commit d20264ef). Retrieved December 7, 2023 from https:\/\/github.com\/bondhugula\/polymage-benchmarks","journal-title":"(commit d20264ef)"},{"doi-asserted-by":"publisher","key":"e_1_3_2_12_2","DOI":"10.1109\/TPDS.2016.2615094"},{"doi-asserted-by":"publisher","key":"e_1_3_2_13_2","DOI":"10.1145\/1854273.1854317"},{"doi-asserted-by":"publisher","key":"e_1_3_2_14_2","DOI":"10.1145\/1375581.1375595"},{"key":"e_1_3_2_15_2","volume-title":"Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI \u201918)","author":"Chen Tianqi","year":"2018","unstructured":"Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen Shen, Meghan Cowan, 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 Symposium on Operating Systems Design and Implementation (OSDI \u201918). 578\u2013594. https:\/\/www.usenix.org\/conference\/osdi18\/presentation\/chen"},{"key":"e_1_3_2_16_2","first-page":"3389","volume-title":"Advances in Neural Information Processing Systems","author":"Chen Tianqi","year":"2018","unstructured":"Tianqi Chen, Lianmin Zheng, Eddie Yan, Ziheng Jiang, Thierry Moreau, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018. Learning to optimize tensor programs. In Advances in Neural Information Processing Systems. 3389\u20133400."},{"doi-asserted-by":"publisher","key":"e_1_3_2_17_2","DOI":"10.1145\/2988450.2988454"},{"unstructured":"Sharan Chetlur Cliff Woolley Philippe Vandermersch Jonathan Cohen John Tran Bryan Catanzaro and Evan Shelhamer. 2014. cuDNN: Efficient primitives for deep learning. arXiv:cs.NE\/1410.0759 (2014).","key":"e_1_3_2_18_2"},{"unstructured":"Standard Performance Evaluation Corporation. 2007. SPEC CPU2000 V1.3. Retrieved December 7 2023 from http:\/\/www.spec.org\/cpu2000\/","key":"e_1_3_2_19_2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_20_2","DOI":"10.18653\/v1\/N19-1423"},{"doi-asserted-by":"publisher","key":"e_1_3_2_21_2","DOI":"10.1007\/BF01407931"},{"doi-asserted-by":"publisher","key":"e_1_3_2_22_2","DOI":"10.1007\/978-0-387-09766-4_502"},{"unstructured":"Google. 2017. XLA: Optimizing Compiler for Machine Learning. Retrieved December 7 2023 from https:\/\/www.tensorflow.org\/xla","key":"e_1_3_2_23_2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_24_2","DOI":"10.1145\/2544137.2544160"},{"doi-asserted-by":"publisher","key":"e_1_3_2_25_2","DOI":"10.1142\/S0129626412500107"},{"doi-asserted-by":"publisher","key":"e_1_3_2_26_2","DOI":"10.1145\/2743016"},{"key":"e_1_3_2_27_2","article-title":"Halide Benchmarks","year":"2013","unstructured":"Halide. 2013. Halide Benchmarks (commit 8c23a197). Retrieved December 7, 2023 from https:\/\/github.com\/halide\/Halide","journal-title":"(commit 8c23a197)"},{"doi-asserted-by":"publisher","key":"e_1_3_2_28_2","DOI":"10.5244\/C.2.23"},{"doi-asserted-by":"publisher","key":"e_1_3_2_29_2","DOI":"10.1145\/1542275.1542301"},{"doi-asserted-by":"publisher","key":"e_1_3_2_30_2","DOI":"10.1109\/CVPR.2016.90"},{"unstructured":"Andrew G. Howard Menglong Zhu Bo Chen Dmitry Kalenichenko Weijun Wang Tobias Weyand Marco Andreetto and Hartwig Adam. 2017. MobileNets: Efficient convolutional neural networks for mobile vision applications. arXiv:cs.CV\/1704.04861 (2017).","key":"e_1_3_2_31_2"},{"unstructured":"Huawei. 2020. MindSpore. Retrieved December 7 2023 from https:\/\/www.mindspore.cn\/en","key":"e_1_3_2_32_2"},{"key":"e_1_3_2_33_2","volume-title":"Proceedings of the 32nd International Conference on Machine Learning (ICML \u201915), Vol. 37. 448\u2013456.","author":"Ioffe Sergey","year":"2015","unstructured":"Sergey Ioffe and Christian Szegedy. 2015. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proceedings of the 32nd International Conference on Machine Learning (ICML \u201915), Vol. 37. 448\u2013456."},{"doi-asserted-by":"publisher","key":"e_1_3_2_34_2","DOI":"10.1145\/73560.73588"},{"doi-asserted-by":"publisher","key":"e_1_3_2_35_2","DOI":"10.1145\/3404846"},{"doi-asserted-by":"publisher","key":"e_1_3_2_36_2","DOI":"10.1145\/3410463.3414649"},{"doi-asserted-by":"publisher","key":"e_1_3_2_37_2","DOI":"10.1007\/BF00268497"},{"doi-asserted-by":"publisher","key":"e_1_3_2_38_2","DOI":"10.5555\/645671.665526"},{"doi-asserted-by":"publisher","key":"e_1_3_2_39_2","DOI":"10.1145\/1362622.1362691"},{"doi-asserted-by":"publisher","key":"e_1_3_2_40_2","DOI":"10.1145\/1250734.1250761"},{"doi-asserted-by":"publisher","key":"e_1_3_2_41_2","DOI":"10.1109\/CGO51591.2021.9370308"},{"doi-asserted-by":"publisher","key":"e_1_3_2_42_2","DOI":"10.1109\/5.726791"},{"doi-asserted-by":"publisher","key":"e_1_3_2_43_2","DOI":"10.1109\/HPCA51647.2021.00071"},{"doi-asserted-by":"publisher","key":"e_1_3_2_44_2","DOI":"10.1145\/2541228.2555292"},{"doi-asserted-by":"publisher","key":"e_1_3_2_45_2","DOI":"10.1145\/2694344.2694364"},{"doi-asserted-by":"publisher","key":"e_1_3_2_46_2","DOI":"10.1145\/3453483.3454083"},{"unstructured":"NVIDIA. 2013. cuBLAS. Retrieved December 7 2023 from https:\/\/developer.nvidia.com\/cublas","key":"e_1_3_2_47_2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_48_2","DOI":"10.1145\/2723694"},{"doi-asserted-by":"publisher","key":"e_1_3_2_49_2","DOI":"10.5555\/1795703"},{"key":"e_1_3_2_50_2","first-page":"8026","volume-title":"Advances in Neural Information Processing Systems","author":"Paszke Adam","year":"2019","unstructured":"Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems. 8026\u20138037."},{"doi-asserted-by":"publisher","key":"e_1_3_2_51_2","DOI":"10.1145\/3485539"},{"doi-asserted-by":"publisher","key":"e_1_3_2_52_2","DOI":"10.1145\/1926385.1926449"},{"unstructured":"Louis-No\u00ebl Pouchet and Tomofumi Yuki. 2016. PolyBench\/C 4.2. Retrieved December 7 2023 from https:\/\/sourceforge.net\/projects\/polybench","key":"e_1_3_2_53_2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_54_2","DOI":"10.1007\/3-540-44905-1_11"},{"doi-asserted-by":"publisher","key":"e_1_3_2_55_2","DOI":"10.1145\/2491956.2462176"},{"doi-asserted-by":"publisher","key":"e_1_3_2_56_2","DOI":"10.1145\/2892208.2892228"},{"doi-asserted-by":"publisher","key":"e_1_3_2_57_2","DOI":"10.1109\/CVPR.2017.690"},{"unstructured":"Karen Simonyan and Andrew Zisserman. 2014. Very Deep convolutional networks for large-scale image recognition. arXiv:cs.CV\/1409.1556 (2014).","key":"e_1_3_2_58_2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_59_2","DOI":"10.1145\/2429069.2429127"},{"doi-asserted-by":"publisher","key":"e_1_3_2_60_2","DOI":"10.1145\/3355606"},{"doi-asserted-by":"publisher","key":"e_1_3_2_61_2","DOI":"10.5555\/3295222.3295349"},{"doi-asserted-by":"publisher","key":"e_1_3_2_62_2","DOI":"10.1007\/978-3-642-15582-6_49"},{"doi-asserted-by":"publisher","key":"e_1_3_2_63_2","DOI":"10.1145\/2400682.2400713"},{"key":"e_1_3_2_64_2","article-title":"Scheduling for PPCG","volume":"706","author":"Verdoolaege Sven","year":"2017","unstructured":"Sven Verdoolaege and Gerda Janssens. 2017. Scheduling for PPCG. Report CW 706. KU Leuven.","journal-title":"Report CW"},{"doi-asserted-by":"publisher","key":"e_1_3_2_65_2","DOI":"10.1145\/3369382"},{"doi-asserted-by":"publisher","key":"e_1_3_2_66_2","DOI":"10.1109\/MICRO50266.2020.00044"},{"key":"e_1_3_2_67_2","volume-title":"Proceedings of Machine Learning and Systems","author":"Zhao Jie","year":"2022","unstructured":"Jie Zhao, Xiong Gao, Ruijie Xia, Zhaochuang Zhang, Deshi Chen, Lei Chen, Renwei Zhang, Zhen Geng, Bin Cheng, and Xuefeng Jin. 2022. Apollo: Automatic partition-based operator fusion through layer by layer optimization. In Proceedings of Machine Learning and Systems, Vol. 4. 1\u201319."},{"doi-asserted-by":"publisher","key":"e_1_3_2_68_2","DOI":"10.1145\/3178372.3179509"},{"doi-asserted-by":"publisher","key":"e_1_3_2_69_2","DOI":"10.1145\/3453483.3454106"},{"key":"e_1_3_2_70_2","volume-title":"Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI \u201920)","author":"Zheng Lianmin","year":"2020","unstructured":"Lianmin Zheng, Chengfan Jia, Minmin Sun, Zhao Wu, Cody Hao Yu, Ameer Haj-Ali, Yida Wang, Jun Yang, Danyang Zhuo, Koushik Sen, Joseph E. Gonzalez, and Ion Stoica. 2020. Ansor: Generating high-performance tensor programs for deep learning. In Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI \u201920). 863\u2013879. https:\/\/www.usenix.org\/conference\/osdi20\/presentation\/zheng"},{"doi-asserted-by":"publisher","key":"e_1_3_2_71_2","DOI":"10.1145\/3178372.3179507"}],"container-title":["ACM Transactions on Computer Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3635305","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3635305","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:21Z","timestamp":1750178181000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3635305"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,30]]},"references-count":70,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[2023,11,30]]}},"alternative-id":["10.1145\/3635305"],"URL":"https:\/\/doi.org\/10.1145\/3635305","relation":{},"ISSN":["0734-2071","1557-7333"],"issn-type":[{"type":"print","value":"0734-2071"},{"type":"electronic","value":"1557-7333"}],"subject":[],"published":{"date-parts":[[2023,11,30]]},"assertion":[{"value":"2022-03-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}