{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T15:05:54Z","timestamp":1758121554569,"version":"3.41.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,9,16]],"date-time":"2022-09-16T00:00:00Z","timestamp":1663286400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>Sparse linear algebra is an important kernel in many different applications. Among various sparse general matrix-matrix multiplication (SpGEMM) algorithms, Gustavson\u2019s column-wise SpGEMM has good locality when reading input matrix and can be easily parallelized by distributing the computation of different columns of an output matrix to different processors. However, the sparse accumulation (SPA) step in column-wise SpGEMM, which merges partial sums from each of the multiplications by the row indices, is still a performance bottleneck. The state-of-the-art software implementation uses a hash table for partial sum search in the SPA, which makes SPA the largest contributor to the execution time of SpGEMM. There are three reasons that cause the SPA to become the bottleneck: (1) hash probing requires data-dependent branches that are difficult for a branch predictor to predict correctly; (2) the accumulation of partial sum is dependent on the results of the hash probing, which makes it difficult to hide the hash probing latency; and (3) hash collision requires time-consuming linear search and optimizations to reduce these collisions require an accurate estimation of the number of non-zeros in each column of the output matrix.<\/jats:p>\n          <jats:p>This work proposes ASA architecture to accelerate the SPA. ASA overcomes the challenges of SPA by (1) executing the partial sum search and accumulate with a single instruction through ISA extension to eliminate data-dependent branches in hash probing, (2) using a dedicated on-chip cache to perform the search and accumulation in a pipelined fashion, (3) relying on the parallel search capability of a set-associative cache to reduce search latency, and (4) delaying the merging of overflowed entries. As a result, ASA achieves an average of 2.25\u00d7 and 5.05\u00d7 speedup as compared to the state-of-the-art software implementation of a Markov clustering application and its SpGEMM kernel, respectively. As compared to a state-of-the-art hashing accelerator design, ASA achieves an average of 1.95\u00d7 speedup in the SpGEMM kernel.<\/jats:p>","DOI":"10.1145\/3543068","type":"journal-article","created":{"date-parts":[[2022,6,11]],"date-time":"2022-06-11T22:37:42Z","timestamp":1654987062000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["ASA:\n            <u>A<\/u>\n            ccelerating\n            <u>S<\/u>\n            parse\n            <u>A<\/u>\n            ccumulation in Column-wise SpGEMM"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7892-5113","authenticated-orcid":false,"given":"Chao","family":"Zhang","sequence":"first","affiliation":[{"name":"Lehigh University"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5940-3432","authenticated-orcid":false,"given":"Maximilian","family":"Bremer","sequence":"additional","affiliation":[{"name":"Lawrence Berkeley National Laboratory"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6881-827X","authenticated-orcid":false,"given":"Cy","family":"Chan","sequence":"additional","affiliation":[{"name":"Lawrence Berkeley National Laboratory"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0608-3690","authenticated-orcid":false,"given":"John","family":"Shalf","sequence":"additional","affiliation":[{"name":"Lawrence Berkeley National Laboratory"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7704-0412","authenticated-orcid":false,"given":"Xiaochen","family":"Guo","sequence":"additional","affiliation":[{"name":"Lehigh University"}]}],"member":"320","published-online":{"date-parts":[[2022,9,16]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M104253X"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkx1313"},{"issue":"1","key":"e_1_3_2_4_2","first-page":"161","article-title":"Cyber-physical systems","volume":"12","author":"Baheti Radhakisan","year":"2011","unstructured":"Radhakisan Baheti and Helen Gill. 2011. Cyber-physical systems. Impact Contr. Technol. 12, 1 (2011), 161\u2013166.","journal-title":"Impact Contr. Technol."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3085572"},{"key":"e_1_3_2_6_2","article-title":"Social networks","volume":"4","author":"Banks David L.","year":"2008","unstructured":"David L. Banks and Nicholas Hengartner. 2008. Social networks. Encyc. Quantit. Risk Anal. Assess. 4 (2008).","journal-title":"Encyc. Quantit. Risk Anal. Assess."},{"key":"e_1_3_2_7_2","volume-title":"Bioinformatics","author":"Baxevanis Andreas D.","year":"2020","unstructured":"Andreas D. Baxevanis, Gary D. Bader, and David S. Wishart. 2020. Bioinformatics. John Wiley & Sons."},{"key":"e_1_3_2_8_2","article-title":"The GAP benchmark suite","author":"Beamer Scott","year":"2015","unstructured":"Scott Beamer, Krste Asanovi\u0107, and David Patterson. 2015. The GAP benchmark suite. arXiv preprint arXiv:1508.03619 (2015).","journal-title":"arXiv preprint arXiv:1508.03619"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2014.03.012"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2008.4536313"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1177\/1094342011403516"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/110848244"},{"key":"e_1_3_2_13_2","volume-title":"GraphBLAS.org","author":"Buluc Aydin","year":"2017","unstructured":"Aydin Buluc, Timothy Mattson, Scott McMillan, Jos\u00e9 Moreira, and Carl Yang. 2017. The GraphBLAS C API Specification. Technical Report. GraphBLAS.org."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICFPT51103.2020.00034"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1177\/1094342015593158"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2019.8916378"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1168918.1168880"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC49654.2021.9622866"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/0613024"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400216"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976830.12"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA47549.2020.00047"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/355791.355796"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA51647.2021.00017"},{"key":"e_1_3_2_25_2","unstructured":"Intel. 2022. Intel i7-6700 (Skylake) 4.0 GHz (Turbo Boost) 14 nm. Retrieved February 2022 from https:\/\/www.intel.com\/content\/www\/us\/en\/processors\/core\/desktop-6th-gen-core-family-datasheet-vol-1.html."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3352460.3358286"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2898361"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1669112.1669172"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl158"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/VLSIT.2018.8510634"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/MIC.2003.1167344"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2751205.2751209"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/1064978.1065034"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s12010-017-2568-3"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/13093426X"},{"key":"e_1_3_2_36_2","unstructured":"Micron. 2021. 8Gb: x4 x8 x16 DDR4 SDRAM Features. Micron Technology Inc. Retrieved September 2021 from https:\/\/www.micron.com\/-\/media\/client\/global\/documents\/products\/data-sheet\/dram\/ddr4\/8gb_ddr4_sdram.pdf."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3352460.3358254"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3229710.3229720"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2018.00067"},{"key":"e_1_3_2_40_2","volume-title":"Sparse Matrix Technology-electronic Edition","author":"Pissanetzky Sergio","year":"1984","unstructured":"Sergio Pissanetzky. 1984. Sparse Matrix Technology-electronic Edition. Academic Press."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA47549.2020.00015"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3352460.3358330"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2508148.2485963"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.59"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS47924.2020.00022"},{"key":"e_1_3_2_46_2","first-page":"135","volume-title":"ACM SIGPLAN Notices","author":"Shun Julian","year":"2013","unstructured":"Julian Shun and Guy E. Blelloch. 2013. Ligra: A lightweight graph processing framework for shared memory. In ACM SIGPLAN Notices, Vol. 48. ACM, 135\u2013146."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3436730"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3355396"},{"key":"e_1_3_2_49_2","first-page":"2007","volume-title":"IEEE international conference on Microelectronic Systems Education (MSE\u201907)","author":"Stine James E.","year":"2007","unstructured":"James E. Stine, Ivan Castellanos, Michael Wood, Jeff Henson, Fred Love, W. Rhett Davis, Paul D. Franzon, Michael Bucher, Sunil Basavarajaiah, Julie Oh, et\u00a0al. 2007. FreePDK: An open-source variation-aware design kit. IEEE international conference on Microelectronic Systems Education (MSE\u201907). IEEE, 2007."},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW52791.2021.00046"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA51647.2021.00061"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.5555\/3433701.3433794"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/192724.192753"},{"key":"e_1_3_2_54_2","volume-title":"Graph Clustering by Flow Simulation","author":"Dongen Stijn Marinus van","year":"2000","unstructured":"Stijn Marinus van Dongen. 2000. Graph Clustering by Flow Simulation. Ph. D. Dissertation. University of Utrecht."},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465371"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/11557654_91"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/1362622.1362674"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/2830772.2830807"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/3445814.3446702"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3352460.3358272"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA47549.2020.00030"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2013.6670336"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543068","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3543068","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:32Z","timestamp":1750182572000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543068"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,16]]},"references-count":61,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3543068"],"URL":"https:\/\/doi.org\/10.1145\/3543068","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2022,9,16]]},"assertion":[{"value":"2021-11-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}