{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T15:43:36Z","timestamp":1784389416429,"version":"3.55.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T00:00:00Z","timestamp":1782345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62272474"],"award-info":[{"award-number":["62272474"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Exploiting matrix symmetry to halve memory footprint offers a substantial opportunity for accelerating memory-bound computations like Sparse Matrix-Vector Multiplication (SpMV). However, symmetric SpMV incurs data conflicts when concurrently writing the output vector. Previous approaches fail to address this issue efficiently, i.e., either are non-scalable or yield poor performance for large high-bandwidth irregular matrices.<\/jats:p>\n                  <jats:p\/>\n                  <jats:p>\n                    This article extends\n                    <jats:italic toggle=\"yes\">DCS-SpMV<\/jats:italic>\n                    , a\n                    <jats:underline>D<\/jats:underline>\n                    ivide-and-\n                    <jats:underline>C<\/jats:underline>\n                    onquer (DC) based shared-memory implementation of\n                    <jats:underline>S<\/jats:underline>\n                    ymmetric SpMV. The key idea of DCS-SpMV is to recursively divide and reorder the matrix-induced\n                    <jats:italic toggle=\"yes\">conflict graph<\/jats:italic>\n                    into independent subgraphs for parallel execution, and construct separate subgraphs to avoid data conflicts. The DC approach naturally transforms the input matrix into a low-conflict part and a high-conflict part, which motivates us to design a conflict-aware hybrid solution\n                    <jats:italic toggle=\"yes\">DCH-SpMV<\/jats:italic>\n                    that executes these two parts using DCS-SpMV and the standard SpMV, respectively. We also develop a machine learning model for DCH-SpMV to predict the optimal number of DC recursions on a given matrix and architecture.\n                  <\/jats:p>\n                  <jats:p\/>\n                  <jats:p>\n                    In this work, we further optimize the hybrid DC implementation by reducing data conflicts before the DC preprocessing. First, we present a\n                    <jats:italic toggle=\"yes\">conflict-pruning<\/jats:italic>\n                    strategy to decouple certain highly dense columns or rows from the conflict graph of a symmetric matrix. Second, we implement a heuristic to adaptively select the lower or upper triangular part of a symmetric matrix, leading to fewer data conflicts. Our optimizations not only facilitate the DC preprocessing, but also improve the performance of DCH-SpMV.\n                  <\/jats:p>\n                  <jats:p\/>\n                  <jats:p>\n                    We evaluate our work on both x86 and ARM multi-core CPUs using 298 symmetric sparse matrices from the SuiteSparse Matrix Collection. Our new optimizations improve the performance of previous version [\n                    <jats:xref ref-type=\"bibr\">42<\/jats:xref>\n                    ] by up to 4.89\u00d7, demonstrating significant speedup over the state-of-the-art approaches including the vendor-tuned Intel oneMKL library.\n                  <\/jats:p>","DOI":"10.1145\/3803015","type":"journal-article","created":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T11:06:09Z","timestamp":1776078369000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Towards Efficient Symmetric Sparse Matrix-Vector Multiplication on Multi-Cores"],"prefix":"10.1145","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-0434-8075","authenticated-orcid":false,"given":"Haozhong","family":"Qiu","sequence":"first","affiliation":[{"name":"National University of Defense Technology College of Computer Science and Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4876-2368","authenticated-orcid":false,"given":"Chuanfu","family":"Xu","sequence":"additional","affiliation":[{"name":"College of Computer Science and Technology, Laboratory of Digitizing Software for Frontier Equipment, National University of Defense Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-8323-8440","authenticated-orcid":false,"given":"Qingsong","family":"Wang","sequence":"additional","affiliation":[{"name":"National University of Defense Technology College of Computer Science and Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3542-4869","authenticated-orcid":false,"given":"Jianbin","family":"Fang","sequence":"additional","affiliation":[{"name":"National University of Defense Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7676-7609","authenticated-orcid":false,"given":"Jian","family":"Zhang","sequence":"additional","affiliation":[{"name":"China Aerodynamics Research and Development Center","place":["Mianyang, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1444-4588","authenticated-orcid":false,"given":"Liang","family":"Deng","sequence":"additional","affiliation":[{"name":"China Aerodynamics Research and Development Center","place":["Mianyang, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-1025-5238","authenticated-orcid":false,"given":"Yue","family":"Ding","sequence":"additional","affiliation":[{"name":"National University of Defense Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-7571-7048","authenticated-orcid":false,"given":"Yue","family":"Wang","sequence":"additional","affiliation":[{"name":"National University of Defense Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9522-601X","authenticated-orcid":false,"given":"Zhimeng","family":"Han","sequence":"additional","affiliation":[{"name":"National University of Defense Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6906-4940","authenticated-orcid":false,"given":"Yonggang","family":"Che","sequence":"additional","affiliation":[{"name":"College of Computer Science and Technology, Laboratory of Digitizing Software for Frontier Equipment, National University of Defense Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,25]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3399732"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.6512"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2597652.2597678"},{"key":"e_1_3_2_5_2","unstructured":"Junjie Bai Fang Lu and Ke Zhang. 2019. ONNX: Open Neural Network Exchange. Retrieved from https:\/\/github.com\/onnx\/onnx"},{"key":"e_1_3_2_6_2","unstructured":"Vicente H. F. Batista George O. Ainsworth and Fernando L. B. Ribeiro. 2010. Parallel structurally-symmetric sparse matrix-vector products on multi-core processors. (2010) 17. arXiv:1003.0952. Retrieved from https:\/\/arxiv.org\/abs\/1003.0952"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.73"},{"key":"e_1_3_2_8_2","first-page":"12","volume-title":"Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures","author":"Bulu\u00e7 Aydin","year":"2009","unstructured":"Aydin Bulu\u00e7, Jeremy T. Fineman, Matteo Frigo, John R. Gilbert, and Charles E. Leiserson. 2009. Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures. 12 pages."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/800195.805928"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_3_2_11_2","first-page":"10","volume-title":"Proceedings of the of 2009 Dagstuhl Seminar on Combinatorial Scientific Computing","author":"Devine K.D.","year":"2009","unstructured":"K.D. Devine, E.G. Boman, L.A. Riesen, U.V. Catalyurek, and C. Chevalier. 2009. Getting started with zoltan: A short tutorial. In Proceedings of the of 2009 Dagstuhl Seminar on Combinatorial Scientific Computing. 10 pages. Also available as Sandia National Labs Tech Report SAND2009-0578C.."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1155\/2001\/569670"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC41404.2022.00071"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356148"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3134442"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0117"},{"key":"e_1_3_2_18_2","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1109\/IPDPS.2013.43","article-title":"Improving the performance of the symmetric sparse matrix-vector multiplication in multicore","author":"Gkountouvas Theo","year":"2013","unstructured":"Theo Gkountouvas, Vasileios P. Karakasis, Kornilios Kourtis, Georgios I. Goumas, and Nectarios Koziris. 2013. Improving the performance of the symmetric sparse matrix-vector multiplication in multicore. 2013 IEEE 27th International Symposium on Parallel and Distributed Processing (2013), 273\u2013283.","journal-title":"2013 IEEE 27th International Symposium on Parallel and Distributed Processing"},{"key":"e_1_3_2_19_2","article-title":"Some useful optimisations for unstructured computational fluid dynamics codes on multicore and manycore architectures","author":"Hadade I.","year":"2018","unstructured":"I. Hadade, F. Wang, M. Carnevale, and L. D. Mare. 2018. Some useful optimisations for unstructured computational fluid dynamics codes on multicore and manycore architectures. Computer Physics Communications 235, 1 (2018), 305\u2013323.","journal-title":"Computer Physics Communications"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/2784051.2784319"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676280"},{"key":"e_1_3_2_22_2","article-title":"Enabling High-Bandwidth Memory for HPC and AI Applications for the Next Generation of Processors","author":"Corporation Intel","year":"2023","unstructured":"Intel Corporation. 2023. Enabling High-Bandwidth Memory for HPC and AI Applications for the Next Generation of Processors. Intel Community Blog. Retrieved July 24, 2025 from https:\/\/community.intel.com\/t5\/Blogs\/Products-and-Solutions\/HPC\/Enabling-High-Bandwidth-Memory-for-HPC-and-AI-Applications-for\/post\/1335100","journal-title":"Intel Community Blog"},{"key":"e_1_3_2_23_2","volume-title":"Intel oneAPI Math Kernel Library (oneMKL)","author":"Corporation Intel","year":"2024","unstructured":"Intel Corporation. 2024. Intel oneAPI Math Kernel Library (oneMKL). Intel Corporation. Retrieved March 25, 2024 from https:\/\/www.intel.com\/content\/www\/us\/en\/developer\/tools\/oneapi\/onemkl.html"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.51"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(94)90004-3"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/305219.305248"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.2172\/7093021"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.matcom.2023.09.016"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/1941553.1941587"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/130930352"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/130930352"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTER52292.2023.00025"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3545008.3545042"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2015.04.004"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2014.03.008"},{"issue":"7","key":"e_1_3_2_36_2","article-title":"Stream benchmark","volume":"22","author":"McCalpin John D.","year":"1995","unstructured":"John D. McCalpin. 1995. Stream benchmark. Link: www. cs. virginia. edu\/stream\/Reference html# what 22, 7 (1995), 49\u201362.","journal-title":"Link: www. cs. virginia. edu\/stream\/Reference html# what"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2016.05.304"},{"key":"e_1_3_2_38_2","unstructured":"Guillermo Oyarzun Daniel Peyrolon Carlos \u00c1lvarez and Xavier Martorell. 2021. An FPGA cached sparse matrix vector product (SpMV) for unstructured computational fluid dynamics simulations. (2021) 14 pages. arXiv:2107.12371. Retrieved from https:\/\/arxiv.org\/abs\/2107.12371"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/356616.356618"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3627535.3638473"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/DAC63849.2025.11133082"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3746233"},{"key":"e_1_3_2_43_2","first-page":"761","volume-title":"Proceedings of the SC24: International Conference for High Performance Computing, Networking, Storage and Analysis","author":"Qiu Haozhong","year":"2024","unstructured":"Haozhong Qiu, Chuanfu Xu, Jianbin Fang, Jian Zhang, Liang Deng, Yue Ding, Qingsong Wang, Shizhao Chen, Yonggang Che, and Jie Liu. 2024. A conflict-aware divide-and-conquer algorithm for symmetric sparse matrix-vector multiplication. In Proceedings of the SC24: International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Computer Society, 761\u2013775."},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503287"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970739"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3218176.3218232"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688517"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/10.1.85"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1498765.1498785"},{"key":"e_1_3_2_50_2","unstructured":"Jonathan Wong Ellen Kuhl and Eric F. Darve. 2015. A new sparse matrix vector multiplication GPU algorithm designed for finite element problems. (2015) 35. arXiv:1501.00324. Retrieved from https:\/\/arxiv.org\/abs\/1501.00324"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2021.3085578"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3090328"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3776752"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS54959.2023.00046"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3803015","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T15:54:59Z","timestamp":1782402899000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3803015"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,25]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3803015"],"URL":"https:\/\/doi.org\/10.1145\/3803015","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,25]]},"assertion":[{"value":"2025-07-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-21","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}