{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T21:49:25Z","timestamp":1791236965556,"version":"4.1.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,9,4]],"date-time":"2018-09-04T00:00:00Z","timestamp":1536019200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Key R8D Program of China","award":["2017YFB0202500"],"award-info":[{"award-number":["2017YFB0202500"]}]},{"DOI":"10.13039\/501100001809","name":"National Science Foundation of China","doi-asserted-by":"crossref","award":["61300010 and 61300011"],"award-info":[{"award-number":["61300010 and 61300011"]}],"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":[[2018,9,30]]},"abstract":"<jats:p>The Sparse Matrix-Vector Multiplication (SpMV) kernel dominates the computing cost in numerous scientific applications. Many implementations based on different sparse formats were proposed to improve this kernel on the recent GPU architectures. However, it has been widely observed that there is no \u201cbest-for-all\u201d sparse format for the SpMV kernel on GPU. Indeed, serious performance degradation of an order of magnitude can be observed without a careful selection of the sparse format to use. To address this problem, we propose in this article BestSF (Best Sparse Format), a new learning-based sparse meta-format that automatically selects the most appropriate sparse format for a given input matrix. To do so, BestSF relies on a cost-sensitive classification system trained using Weighted Support Vector Machines (WSVMs) to predict the best sparse format for each input sparse matrix. Our experimental results on two different NVIDIA GPU architectures using a large number of real-world sparse matrices show that BestSF achieved a noticeable overall performance improvement over using a single sparse format. While BestSF is trained to select the best sparse format in terms of performance (GFLOPS), our further experimental investigations revealed that using BestSF also led, in most of the test cases, to the best energy efficiency (MFLOPS\/W). To prove its practical effectiveness, we also evaluate the performance and energy efficiency improvement achieved when using BestSF as a building block in a GPU-based Preconditioned Conjugate Gradient (PCG) iterative solver.<\/jats:p>","DOI":"10.1145\/3226228","type":"journal-article","created":{"date-parts":[[2018,9,4]],"date-time":"2018-09-04T08:37:30Z","timestamp":1536050250000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["BestSF"],"prefix":"10.1145","volume":"15","author":[{"given":"Akrem","family":"Benatia","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Weixing","family":"Ji","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yizhuo","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Feng","family":"Shi","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,9,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Hartwig Anzt Marc Baboulin Jack Dongarra Yvan Fournier Frank Hulsemann Amal Khabou and Yushan Wang. 2016. Accelerating the conjugate gradient algorithm with GPU in CFD simulations. VECPAR.  Hartwig Anzt Marc Baboulin Jack Dongarra Yvan Fournier Frank Hulsemann Amal Khabou and Yushan Wang. 2016. Accelerating the conjugate gradient algorithm with GPU in CFD simulations. VECPAR.","DOI":"10.1007\/978-3-319-61982-8_5"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2017.05.006"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2712386.2712387"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.69"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597652.2597678"},{"key":"e_1_2_1_7_1","volume-title":"Thrust: A productivity-oriented library for CUDA. Retrieved","author":"Bell Nathan","year":"2011"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 45th International Conference on Parallel Processing (ICPP\u201916)","author":"Benatia A."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2016.04.003"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588768.2576783"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01970-8_90"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00450-010-0112-6"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961199"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837853.1693471"},{"key":"e_1_2_1_15_1","volume-title":"Workshop on Green Programming, Computing, and Data Processing (GPCDP\u201914)","author":"Coplin J."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2016.164"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022627411411"},{"key":"e_1_2_1_18_1","volume-title":"Cusp: Generic Parallel Algorithms for Sparse Matrix and Graph Computations. Retrieved","author":"Dalton Steven","year":"2014"},{"key":"e_1_2_1_19_1","unstructured":"John D. Davis and Eric S. Chung. 2012. SpMV: A Memory-Bound Application on the GPU Stuck Between a Rock and a Hard Place. Technical Report Microsoft Research Silicon Valley.  John D. Davis and Eric S. Chung. 2012. SpMV: A Memory-Bound Application on the GPU Stuck Between a Rock and a Hard Place. Technical Report Microsoft Research Silicon Valley."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3017994"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/fld.2462"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2016741.2016744"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.123"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555815.1555775"},{"key":"e_1_2_1_26_1","unstructured":"Chih-Wei Hsu Chih-Chung Chang and Chih-Jen Lin. 2003. A practical guide to support vector classification. Retrieved October 2015 from https:\/\/www.cs.sfu.ca\/people\/Faculty\/teaching\/726\/spring11\/svmguide.pdf.  Chih-Wei Hsu Chih-Chung Chang and Chih-Jen Lin. 2003. A practical guide to support vector classification. Retrieved October 2015 from https:\/\/www.cs.sfu.ca\/people\/Faculty\/teaching\/726\/spring11\/svmguide.pdf."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/72.991427"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00043-X"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/HIPC.2009.5433179"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 4th Annual Symposium on Combinatorial Search.","author":"Kotthoff Lars","year":"2011"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Jakub Kurzak David A. Bader and Jack Dongarra. 2010. Scientific Computing with Multicore and Accelerators. CRC Press.   Jakub Kurzak David A. Bader and Jack Dongarra. 2010. Scientific Computing with Multicore and Accelerators. CRC Press.","DOI":"10.1201\/b10376"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2401575"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-012-0825-3"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-016-1887-4"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2751205.2751209"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/3014904.3014982"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636342"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11515-8_10"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2013.6670319"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2954679.2872411"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.59"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/PADSW.2014.7097819"},{"key":"e_1_2_1_43_1","unstructured":"NVIDIA. NVIDIA Management Library. Retrieved September 2017 from https:\/\/developer.nvidia.com\/nvidia-management-library-nvml.  NVIDIA. NVIDIA Management Library. Retrieved September 2017 from https:\/\/developer.nvidia.com\/nvidia-management-library-nvml."},{"key":"e_1_2_1_44_1","unstructured":"NVIDIA. 2017. CuBLAS: Dense Linear Algebra on GPUs. Retrieved September 2017 from https:\/\/developer.nvidia.com\/cublas.  NVIDIA. 2017. CuBLAS: Dense Linear Algebra on GPUs. Retrieved September 2017 from https:\/\/developer.nvidia.com\/cublas."},{"key":"e_1_2_1_45_1","unstructured":"NVIDIA. 2017. cuSPARSE : Sparse Linear Algebra on GPUs. Retrieved September 2017 from http:\/\/docs.nvidia.com\/cuda\/cusparse.  NVIDIA. 2017. cuSPARSE : Sparse Linear Algebra on GPUs. Retrieved September 2017 from http:\/\/docs.nvidia.com\/cuda\/cusparse."},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Yousef Saad. 2003. Iterative Methods for Sparse Linear Systems. SIAM.   Yousef Saad. 2003. Iterative Methods for Sparse Linear Systems. SIAM.","DOI":"10.1137\/1.9780898718003"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2751205.2751244"},{"key":"e_1_2_1_48_1","unstructured":"Jonathan Richard Shewchuk and others. 1994. An introduction to the conjugate gradient method without the agonizing pain.  Jonathan Richard Shewchuk and others. 1994. An introduction to the conjugate gradient method without the agonizing pain."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2304576.2304624"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/IGCC.2013.6604520"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2012.07.002"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/762761.762822"},{"key":"e_1_2_1_54_1","unstructured":"Richard Wilson Vuduc and James W. Demmel. 2003. Automatic Performance Tuning of Sparse Matrix Kernels. Vol. 1. University of California Berkeley.  Richard Wilson Vuduc and James W. Demmel. 2003. Automatic Performance Tuning of Sparse Matrix Kernels. Vol. 1. University of California Berkeley."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2008.494"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2490"},{"key":"e_1_2_1_57_1","first-page":"57","article-title":"SATzilla2012: Improved algorithm selection based on cost-sensitive classification models","volume":"2012","author":"Xu Lin","year":"2012","journal-title":"Proceedings of SAT Challenge"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/SNPD.2012.20"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2692916.2555255"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001407005703"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3226228","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3226228","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:15:08Z","timestamp":1750266908000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3226228"}},"subtitle":["A Sparse Meta-Format for Optimizing SpMV on GPU"],"short-title":[],"issued":{"date-parts":[[2018,9,4]]},"references-count":58,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9,30]]}},"alternative-id":["10.1145\/3226228"],"URL":"https:\/\/doi.org\/10.1145\/3226228","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,4]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}