{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T11:33:00Z","timestamp":1763724780918,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"National Key Research and Development Program of China","award":["2023YFB3001801"],"award-info":[{"award-number":["2023YFB3001801"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62322201 and U23B2020"],"award-info":[{"award-number":["62322201 and U23B2020"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"crossref","award":["YWF-23-L-1121, JKF-20240198 and JK2024-58"],"award-info":[{"award-number":["YWF-23-L-1121, JKF-20240198 and JK2024-58"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>\n            Modern optimizing compilers are able to exploit memory access or computation patterns to generate vectorized codes. However, such patterns in irregular programs are unknown until runtime due to the input dependence. Thus, either compiler\u2019s static optimization or profile-guided optimization cannot represent the patterns for any common input, which leads to suboptimal vectorization. To address the above drawback, we propose\n            <jats:italic toggle=\"yes\">DynVec<\/jats:italic>\n            ,\n            <jats:xref ref-type=\"fn\">\n              <jats:sup>1<\/jats:sup>\n            <\/jats:xref>\n            a framework to automatically exploit regular patterns buried deeply inside irregular programs and apply corresponding optimizations for better vectorization. Due to the integration of workload distribution and the ability to represent instruction features and identify regular patterns with effective feature extraction and data re-arranging methods,\n            <jats:italic toggle=\"yes\">DynVec<\/jats:italic>\n            can generate highly efficient vectorized codes for both serial and parallel irregular programs by replacing\n            <jats:italic toggle=\"yes\">gather<\/jats:italic>\n            \/\n            <jats:italic toggle=\"yes\">scatter<\/jats:italic>\n            \/\n            <jats:italic toggle=\"yes\">reduction<\/jats:italic>\n            operations with optimized operation groups. We evaluate\n            <jats:italic toggle=\"yes\">DynVec<\/jats:italic>\n            on optimizing irregular programs such as SpMV and graph programs with representative sparse matrix datasets. The experiment results show that\n            <jats:italic toggle=\"yes\">DynVec<\/jats:italic>\n            achieves significant speedup compared to the state-of-the-art implementations across a range of X86 and ARM platforms.\n          <\/jats:p>","DOI":"10.1145\/3716874","type":"journal-article","created":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T16:09:29Z","timestamp":1739203769000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Exploiting Dynamic Regular Patterns in Irregular Programs for Efficient Vectorization"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8637-4182","authenticated-orcid":false,"given":"Kelun","family":"Lei","sequence":"first","affiliation":[{"name":"Beihang University","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-0540-0959","authenticated-orcid":false,"given":"Shaokang","family":"Du","sequence":"additional","affiliation":[{"name":"Beihang University","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5163-4607","authenticated-orcid":false,"given":"Xin","family":"You","sequence":"additional","affiliation":[{"name":"Beihang University","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1101-7927","authenticated-orcid":false,"given":"Hailong","family":"Yang","sequence":"additional","affiliation":[{"name":"Beihang University","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7186-0556","authenticated-orcid":false,"given":"Zhongzhi","family":"Luan","sequence":"additional","affiliation":[{"name":"Beihang University","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1829-2817","authenticated-orcid":false,"given":"Yi","family":"Liu","sequence":"additional","affiliation":[{"name":"Beihang University","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5382-1473","authenticated-orcid":false,"given":"Depei","family":"Qian","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Beihang University","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,28]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2903150.2903169"},{"key":"e_1_3_3_3_2","volume-title":"Vectorization for Accelerated Gather\/Scatter and Multibyte Data Formats","author":"Anderson Andrew","year":"2016","unstructured":"Andrew Anderson. 2016. Vectorization for Accelerated Gather\/Scatter and Multibyte Data Formats. Ph.D. Dissertation. Trinity College Dublin."},{"issue":"4","key":"e_1_3_3_4_2","first-page":"1","article-title":"Automatic vectorization of interleaved data revisited","volume":"12","author":"Anderson Andrew","year":"2015","unstructured":"Andrew Anderson, Avinash Malik, and David Gregg. 2015. Automatic vectorization of interleaved data revisited. ACM Trans. Arch. Code Optim. 12, 4 (2015), 1\u201325.","journal-title":"ACM Trans. Arch. Code Optim."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.69"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2597652.2597678"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314615"},{"key":"e_1_3_3_8_2","unstructured":"Satish Balay Shrirang Abhyankar Mark Adams Jed Brown Peter Brune Kris Buschelman Lisandro Dalcin Alp Dener Victor Eijkhout W Gropp et\u00a0al. 2019. PETSc Users Manual."},{"key":"e_1_3_3_9_2","first-page":"119","volume-title":"Proceedings of the 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","author":"Basumallik Ayon","year":"2006","unstructured":"Ayon Basumallik and Rudolf Eigenmann. 2006. Optimizing irregular shared-memory applications for distributed-memory systems. In Proceedings of the 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM, New York, NY, 119\u2013128."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3544559"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1177\/1094342011403516"},{"key":"e_1_3_3_12_2","first-page":"721","volume-title":"Proceedings of the IEEE International Parallel & Distributed Processing Symposium","author":"Buluc Aydin","year":"2011","unstructured":"Aydin Buluc, Samuel Williams, Leonid Oliker, and James Demmel. 2011. Reduced-bandwidth multithreaded algorithms for sparse matrix-vector multiplication. In Proceedings of the IEEE International Parallel & Distributed Processing Symposium. IEEE, Los Alamitos, CA, 721\u2013733."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2015.228"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2004.02.004"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3126908.3126936"},{"key":"e_1_3_3_16_2","first-page":"779","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC\u201918)","author":"Cheshmi Kazem","year":"2018","unstructured":"Kazem Cheshmi, Shoaib Kamil, Michelle Mills Strout, and Maryam Mehri Dehnavi. 2018. ParSy: Inspection and transformation of sparse matrix computations for parallelism. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC\u201918). IEEE\/ACM, Los Alamitos, CA, and New York, NY, 779\u2013793."},{"key":"e_1_3_3_17_2","first-page":"407","volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium","author":"Dalton Steven","year":"2015","unstructured":"Steven Dalton, Sean Baxter, Duane Merrill, Luke Olson, and Michael Garland. 2015. Optimizing sparse matrix operations on gpus using merge path. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium. IEEE, 407\u2013416."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_3_3_19_2","first-page":"292","volume-title":"Proceedings of the 46th International Conference on Parallel Processing (ICPP\u201917)","author":"Elafrou Athena","year":"2017","unstructured":"Athena Elafrou, Georgios Goumas, and Nectarios Koziris. 2017. Performance analysis and optimization of sparse matrix-vector multiplication on modern multi-and many-core processors. In Proceedings of the 46th International Conference on Parallel Processing (ICPP\u201917). IEEE, 292\u2013301."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3134442"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3472456.3472479"},{"key":"e_1_3_3_22_2","first-page":"448","volume-title":"Proceedings of the IEEE\/ACM International Symposium on Code Generation and Optimization (CGO\u201924)","author":"Fu Qiang","year":"2024","unstructured":"Qiang Fu, Thomas B. Rolinger, and H Howie Huang. 2024. JITSPMM: Just-in-time instruction generation for accelerated sparse matrix-matrix multiplication. In Proceedings of the IEEE\/ACM International Symposium on Code Generation and Optimization (CGO\u201924). IEEE, 448\u2013459."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3437801.3441592"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.68"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2006.88"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3295712"},{"key":"e_1_3_3_27_2","unstructured":"IntelligentSoftwareSystems. 2024. Galois: C++ Library for Multi-Core and Multi-Node Parallelization. Retrieved from https:\/\/github.com\/IntelligentSoftwareSystems\/Galois"},{"key":"e_1_3_3_28_2","first-page":"175","volume-title":"Proceedings of the International Symposium on Code Generation and Optimization","author":"Jiang Peng","year":"2018","unstructured":"Peng Jiang and Gagan Agrawal. 2018. Conflict-free vectorization of associative irregular applications with recent SIMD architectural advances. In Proceedings of the International Symposium on Code Generation and Optimization. ACM, New York, NY, 175\u2013187."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11265-022-01821-z"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/DAC18074.2021.9586251"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2751205.2751209"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2464996.2465013"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_3_3_34_2","first-page":"678","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC\u201916)","author":"Merrill Duane","year":"2016","unstructured":"Duane Merrill and Michael Garland. 2016. Merge-based parallel sparse matrix-vector multiplication. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC\u201916). IEEE, 678\u2013689."},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314646"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1654059.1654096"},{"key":"e_1_3_3_37_2","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1145\/3503221.3508431","volume-title":"Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","author":"Niu Yuyao","year":"2022","unstructured":"Yuyao Niu, Zhengyang Lu, Haonan Ji, Shuhui Song, Zhou Jin, and Weifeng Liu. 2022. TileSpGEMM: A tiled algorithm for parallel sparse general matrix-matrix multiplication on GPUs. In Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 90\u2013106."},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/1133255.1133997"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC41406.2024.00054"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2751205.2751244"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2005.29"},{"key":"e_1_3_3_42_2","first-page":"137","volume-title":"International Conference on Computational Science","author":"Strout Michelle Mills","year":"2001","unstructured":"Michelle Mills Strout, Larry Carter, and Jeanne Ferrante. 2001. Rescheduling for locality in sparse matrix computations. In International Conference on Computational Science. Springer, Berlin, 137\u2013146."},{"key":"e_1_3_3_43_2","first-page":"90","volume-title":"International Workshop on Languages and Compilers for Parallel Computing","author":"Strout Michelle Mills","year":"2002","unstructured":"Michelle Mills Strout, Larry Carter, Jeanne Ferrante, Jonathan Freeman, and Barbara Kreaseck. 2002. Combining performance aspects of irregular gauss-seidel via sparse tiling. In International Workshop on Languages and Compilers for Parallel Computing. Springer, Berlin, 90\u2013110."},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2018.2857721"},{"key":"e_1_3_3_45_2","article-title":"Graphmat: High performance graph analytics made productive","author":"Sundaram Narayanan","year":"2015","unstructured":"Narayanan Sundaram, Nadathur Rajagopalan Satish, Md Mostofa Ali Patwary, Subramanya R. Dulloor, Satya Gautam Vadlamudi, Dipankar Das, and Pradeep Dubey. 2015. Graphmat: High performance graph analytics made productive. arXiv:1503.07241. Retrieved from https:\/\/arxiv.org\/abs\/1503.07241","journal-title":"arXiv:1503.07241"},{"key":"e_1_3_3_46_2","first-page":"27","volume-title":"Proceedings of the IEEE\/ACM 7th Workshop on the LLVM Compiler Infrastructure in HPC (LLVM-HPC\u201921)","author":"Tian Ruiqin","year":"2021","unstructured":"Ruiqin Tian, Luanzheng Guo, Jiajia Li, Bin Ren, and Gokcen Kestor. 2021. A high performance sparse tensor algebra compiler in MLIR. In Proceedings of the IEEE\/ACM 7th Workshop on the LLVM Compiler Infrastructure in HPC (LLVM-HPC\u201921). IEEE, 27\u201338."},{"issue":"6","key":"e_1_3_3_47_2","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1145\/2813885.2738003","article-title":"Loop and data transformations for sparse matrix code","volume":"50","author":"Venkat Anand","year":"2015","unstructured":"Anand Venkat, Mary Hall, and Michelle Strout. 2015. Loop and data transformations for sparse matrix code. ACM SIGPLAN Not. 50, 6 (2015), 521\u2013532.","journal-title":"ACM SIGPLAN Not."},{"key":"e_1_3_3_48_2","first-page":"14","volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201924)","author":"Wang Luhan","year":"2024","unstructured":"Luhan Wang, Haipeng Jia, Lei Xu, Cunyang Wei, Kun Li, Xianmeng Jiang, and Yunquan Zhang. 2024. VNEC: A vectorized non-empty column format for SpMV on CPUs. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201924). IEEE, 14\u201325."},{"key":"e_1_3_3_49_2","first-page":"149","volume-title":"Proceedings of the International Symposium on Code Generation and Optimization","author":"Xie Biwei","year":"2018","unstructured":"Biwei Xie, Jianfeng Zhan, Xu Liu, Wanling Gao, Zhen Jia, Xiwen He, and Lixin Zhang. 2018. Cvr: Efficient vectorization of spmv on x86 processors. In Proceedings of the International Symposium on Code Generation and Optimization. ACM, New York, NY, 149\u2013162."},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3330345.3330354"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC41406.2024.00065"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3545008.3545042"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3716874","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T11:52:40Z","timestamp":1751111560000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3716874"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,28]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3716874"],"URL":"https:\/\/doi.org\/10.1145\/3716874","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2025,6,28]]},"assertion":[{"value":"2024-07-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-25","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}