{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,30]],"date-time":"2026-08-30T21:50:23Z","timestamp":1788126623079,"version":"build-2803163510"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T00:00:00Z","timestamp":1731974400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Postdoctoral Fellowship Program of China Postdoctoral Science Foundation","award":["GZC20230261"],"award-info":[{"award-number":["GZC20230261"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61972033"],"award-info":[{"award-number":["61972033"]}],"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. Archit. Code Optim."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>Sparse matrix-vector multiplication (SpMV) is one of the important kernels of many iterative algorithms for solving sparse linear systems. The limited storage and computational resources of individual GPUs restrict both the scale and speed of SpMV computing in problem-solving. As real-world engineering problems continue to increase in complexity, the imperative for collaborative execution of iterative solving algorithms across multiple GPUs is increasingly apparent. Although the multi-GPU-based SpMV takes less kernel execution time, it also introduces additional data transmission overhead, which diminishes the performance gains derived from parallelization across multi-GPUs. Based on the non-zero elements distribution characteristics of sparse matrices and the tradeoff between redundant computations and data transfer overhead, this article introduces a series of SpMV optimization techniques tailored for multi-GPU environments and effectively enhances the execution efficiency of iterative algorithms on multiple GPUs. First, we propose a two-level non-zero elements-based matrix partitioning method to increase the overlap of kernel execution and data transmission. Then, considering the irregular non-zero elements distribution in sparse matrices, a long-row-aware matrix partitioning method is proposed to hide more data transmissions. Finally, an optimization using redundant and inexpensive short-row execution to exchange costly data transmission is proposed. Our experimental evaluation demonstrates that, compared with the SpMV on a single GPU, the proposed method achieves an average speedup of 2.00\u00d7 and 1.85\u00d7 on platforms equipped with two RTX 3090 and two Tesla V100-SXM2, respectively. The average speedup of 2.65\u00d7 is achieved on a platform equipped with four Tesla V100-SXM2.<\/jats:p>","DOI":"10.1145\/3676847","type":"journal-article","created":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T10:59:19Z","timestamp":1720436359000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Optimization of Large-Scale Sparse Matrix-Vector Multiplication on Multi-GPU Systems"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3828-0015","authenticated-orcid":false,"given":"Jianhua","family":"Gao","sequence":"first","affiliation":[{"name":"School of Artificial Intelligence, Beijing Normal University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3250-0435","authenticated-orcid":false,"given":"Weixing","family":"Ji","sequence":"additional","affiliation":[{"name":"School of Artificial Intelligence, Beijing Normal University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1288-331X","authenticated-orcid":false,"given":"Yizhuo","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,11,19]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48096-0_46"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3380930"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.69"},{"issue":"0812","key":"e_1_3_3_5_2","article-title":"Optimizing sparse matrix-vector multiplication on GPUs","author":"Baskaran Muthu Manikandan","year":"2009","unstructured":"Muthu Manikandan Baskaran and Rajesh Bordawekar. 2009. Optimizing sparse matrix-vector multiplication on GPUs. IBM Research Report RC24704W0812\u2013047 (2009).","journal-title":"IBM Research Report RC24704"},{"key":"e_1_3_3_6_2","volume-title":"Efficient Sparse Matrix-vector Multiplication on CUDA","author":"Bell Nathan","year":"2008","unstructured":"Nathan Bell and Michael Garland. 2008. Efficient Sparse Matrix-vector Multiplication on CUDA. NVIDIA Technical Report NVR-2008-004. NVIDIA Corporation."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1654059.1654078"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2016.64"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3226228"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2925426.2926278"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01970-8_90"},{"key":"e_1_3_3_12_2","article-title":"MSREP: A fast yet light sparse matrix framework for multi-GPU systems","volume":"2209","author":"Chen Jieyang","year":"2022","unstructured":"Jieyang Chen, Chenhao Xie, Jesun Sahariar Firoz, Jiajia Li, Shuaiwen Leon Song, Kevin J. Barker, Mark Raugas, and Ang Li. 2022. MSREP: A fast yet light sparse matrix framework for multi-GPU systems. CoRR abs\/2209.07552 (2022).","journal-title":"CoRR"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.INS.2020.03.020"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCC\/SMARTCITY\/DSS.2019.00142"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2015.55"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1687399.1687501"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC41404.2022.00071"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1177\/1094342021990738"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3149704.3149767"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICPADS53394.2021.00058"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2023.104799"},{"key":"e_1_3_3_23_2","article-title":"A systematic literature survey of sparse matrix-vector multiplication","author":"Gao Jianhua","year":"2024","unstructured":"Jianhua Gao, Bingjie Liu, Weixing Ji, and Hua Huang. 2024. A systematic literature survey of sparse matrix-vector multiplication. arXiv preprint arXiv:2404.06047 (2024).","journal-title":"arXiv preprint arXiv:2404.06047"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1002\/CPE.3936"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2990849"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.PARCO.2017.04.003"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.68"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.123"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/SBAC-PADW.2016.20"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2015.07.005"},{"key":"e_1_3_3_31_2","first-page":"533","volume-title":"Federated Conference on Computer Science and Information Systems (FedCSIS\u201912)","author":"Karwacki Marek","year":"2012","unstructured":"Marek Karwacki, Beata Bylina, and Jaroslaw Bylina. 2012. Multi-GPU implementation of the uniformization method for solving Markov models. In Federated Conference on Computer Science and Information Systems (FedCSIS\u201912), Maria Ganzha, Leszek A. Maciaszek, and Marcin Paprzycki (Eds.). 533\u2013537. https:\/\/fedcsis.org\/proceedings\/2012\/pliks\/377.pdf"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/120900216"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417763"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462181"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2014.2308221"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/S11432-014-5254-X"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/S11227-016-1887-4"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2751205.2751209"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2016.57"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/1365490.1365500"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS49936.2021.00016"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/InPar.2012.6339602"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161068"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/SASP.2010.5521144"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.PARCO.2012.07.002"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/2555243.2555255"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.CAMWA.2016.06.027"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCSE.2012.28"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178495"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3676847","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3676847","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:19:12Z","timestamp":1750295952000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3676847"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,19]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3676847"],"URL":"https:\/\/doi.org\/10.1145\/3676847","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,19]]},"assertion":[{"value":"2024-01-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-22","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}