The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
SpArch: Efficient Architecture for Sparse Matrix Multiplication
Open accessAbstract
Generalized Sparse Matrix-Matrix Multiplication (SpGEMM) is a ubiquitous task in various engineering and scientific applications. However, inner product based SpGEMM introduces redundant input fetches for mismatched nonzero operands, while outer product based approach suffers from poor output locality due to numerous partial product matrices. Inefficiency in the reuse of either inputs or outputs data leads to extensive and expensive DRAM access. To address this problem, this paper proposes an efficient sparse matrix multiplication accelerator architecture, SpArch, which jointly optimizes the data locality for both input and output matrices. We first design a highly parallelized streaming-based merger to pipeline the multiply and merge stage of partial matrices so that partial matrices are merged on chip immediately after produced. We then propose a condensed matrix representation that reduces the number of partial matrices by three orders of magnitude and thus reduces DRAM access by 5.4x. We further develop a Huffman tree scheduler to improve the scalability of the merger for larger sparse matrices, which reduces the DRAM access by another 1.8x. We also resolve the increased input matrix read induced by the new representation using a row prefetcher with near-optimal buffer replacement policy, further reducing the DRAM access by 1.5x. Evaluated on 20 benchmarks, SpArch reduces the total DRAM access by 2.8x over previous state-of-the-art. On average, SpArch achieves 4x, 19x, 18x, 17x, 1285x speedup and 6x, 164x, 435x, 307x, 62x energy savings over OuterSpace, MKL, cuSPARSE, CUSP, and ARM Armadillo, respectively.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Hochreiter, S., & Schmidhuber, J. (1997) · Neural Computation · doi:10.1162/neco.1997.9.8.1735 · Cited by 102,318
Cramming More Components onto Integrated Circuits (1965)
Moore, G. (2021) · Ideas That Created the Future · doi:10.7551/mitpress/12274.003.0027 · Cited by 6,241
Han, S., Mao, H., & Dally, W. J. (2015) · arXiv · doi:10.48550/arxiv.1510.00149 · Cited by 4,662
Self-citationThe university of Florida sparse matrix collection
Davis, T. A., & Hu, Y. (2011) · ACM Transactions on Mathematical Software · doi:10.1145/2049662.2049663 · Cited by 3,630
Kung (1982) · Computer · doi:10.1109/mc.1982.1653825 · Cited by 2,272
EIE: efficient inference engine on compressed deep neural network
Han, S., Liu, X., Mao, H., Pu, J., Pedram, A., Horowitz, M. A., & Dally, W. J. (2016) · ACM SIGARCH Computer Architecture News · doi:10.1145/3007787.3001163 · Cited by 1,937
Self-citationGraph Clustering by Flow Simulation
van Dongen, S. M. (2000) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · Cited by 1,595
AMC: AutoML for Model Compression and Acceleration on Mobile Devices
He, Y., Lin, J., Liu, Z., Wang, H., Li, L.-J., & Han, S. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-01234-2_48 · Cited by 1,400
Self-citationEIE: Efficient Inference Engine on Compressed Deep Neural Network
Han, S., Liu, X., Mao, H., Pu, J., Pedram, A., Horowitz, M. A., & Dally, W. J. (2016) · 2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA) · doi:10.1109/isca.2016.30 · Cited by 1,077
Self-citationSCNN: An Accelerator for Compressed-sparse Convolutional Neural Networks
Parashar, A., Rhu, M., Mukkara, A., Puglielli, A., Venkatesan, R., Khailany, B., Emer, J., Keckler, S. W., & Dally, W. J. (2017) · Proceedings of the 44th Annual International Symposium on Computer Architecture · doi:10.1145/3079856.3080254 · Cited by 896
Self-citationArmadillo: a template-based C++ library for linear algebra
Sanderson, C., & Curtin, R. (2016) · The Journal of Open Source Software · doi:10.21105/joss.00026 · Cited by 623
ESE: Efficient Speech Recognition Engine with Sparse LSTM on FPGA
Han, S., Kang, J., Mao, H., Hu, Y., Li, X., Li, Y., Xie, D., Luo, H., Yao, S., Wang, Y., et al. (2017) · Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays · doi:10.1145/3020078.3021745 · Cited by 591 · cited 1×
“[54] further extended the efficient SpMV architecture to LSTM[55], a kind of recurrent neural networks.”
BackgroundSelf-citationTwo Fast Algorithms for Sparse Matrices: Multiplication and Permuted Transposition
Gustavson, F. G. (1978) · ACM Transactions on Mathematical Software · doi:10.1145/355791.355796 · Cited by 410
Performance comparison of FPGA, GPU and CPU in image processing
Asano, S., Maruyama, T., & Yamaguchi, Y. (2009) · 2009 International Conference on Field Programmable Logic and Applications · doi:10.1109/fpl.2009.5272532 · Cited by 300
OuterSPACE: An Outer Product Based Sparse Matrix Multiplication Accelerator
Pal, S., Beaumont, J., Park, D.-H., Amarnath, A., Feng, S., Chakrabarti, C., Kim, H.-S., Blaauw, D., Mudge, T., & Dreslinski, R. (2018) · 2018 IEEE International Symposium on High Performance Computer Architecture (HPCA) · doi:10.1109/hpca.2018.00067 · Cited by 292
SparTen: A Sparse Tensor Accelerator for Convolutional Neural Networks
Gondimalla, A., Chesnut, N., Thottethodi, M., & Vijaykumar, T. N. (2019) · Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture · doi:10.1145/3352460.3358291 · Cited by 278
Exposing Fine-Grained Parallelism in Algebraic Multigrid Methods
Bell, N., Dalton, S., & Olson, L. N. (2012) · SIAM Journal on Scientific Computing · doi:10.1137/110838844 · Cited by 252
ExTensor: An Accelerator for Sparse Tensor Algebra
Hegde, K., Asghari-Moghaddam, H., Pellauer, M., Crago, N., Jaleel, A., Solomonik, E., Emer, J., & Fletcher, C. W. (2019) · Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture · doi:10.1145/3352460.3358275 · Cited by 235
Sparse Matrix-Vector multiplication on FPGAs
Zhuo, L., & Prasanna, V. K. (2005) · Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays · doi:10.1145/1046192.1046202 · Cited by 225
Zhu, M., Zhang, T., Gu, Z., & Xie, Y. (2019) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1145/3352460.3358269 · Cited by 199
An Efficient GPU General Sparse Matrix-Matrix Multiplication for Irregular Data
Liu, W., & Vinter, B. (2014) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2014.47 · Cited by 134
Energy-Efficient Floating-Point Unit Design
Galal, S., & Horowitz, M. (2010) · IEEE Transactions on Computers · doi:10.1109/tc.2010.121 · Cited by 132
Understanding Performance Differences of FPGAs and GPUs
Cong, J., Fang, Z., Lo, M., Wang, H., Xu, J., & Zhang, S. (2018) · IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM) · doi:10.1109/fccm.2018.00023 · Cited by 132
Self-citationMaximum matchings in general graphs through randomization
Rabin, M. O., & Vazirani, V. V. (1989) · Journal of Algorithms · doi:10.1016/0196-6774(89)90005-9 · Cited by 125
Learning to Design CircuitsPreprint
Wang, H., Yang, J., Lee, H.-S., & Han, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1812.02734 · Cited by 117
Self-citationExploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication
Azad, A., Ballard, G., Buluç, A., Demmel, J. W., Grigori, L., Schwartz, O., Toledo, S., & Williams, S. (2016) · SIAM Journal on Scientific Computing · doi:10.1137/15m104253x · Cited by 116
Park: An Open Platform for Learning-Augmented Computer Systems
Mao, H., Negi, P., Narayan, A., Wang, H., Yang, J., Wang, H., Marcus, R., Addanki, R., Shirkoohi, M. K., He, S., et al. (2019) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 114
Self-citationAo, N., Zhang, F., Wu, D., Stones, D. S., Wang, G., Liu, X., Liu, J., & Lin, S. (2011) · Proceedings of the VLDB Endowment · doi:10.14778/2002974.2002975 · Cited by 94
Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions
Han, S., Zou, L., & Yu, J. X. (2018) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3183713.3196924 · Cited by 77
Self-citationA Unified Framework for Numerical and Combinatorial Computing
Gilbert, J. R., Reinhardt, S., & Shah, V. B. (2008) · Computing in Science & Engineering · doi:10.1109/mcse.2008.45 · Cited by 76
Understanding the Performance of Sparse Matrix-Vector Multiplication
Goumas, G., Kourtis, K., Anastopoulos, N., Karakasis, V., & Koziris, N. (2008) · Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP) · doi:10.1109/pdp.2008.41 · Cited by 76
(2018) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca.2018.00011 · Cited by 74
Sparse matrix-matrix multiplication on modern architectures
Matam, K. K., Indarapu, S. B., & Kothapalli, K. (2012) · IEEE International Conference on High Performance Computing, Data, and Analytics · doi:10.1109/hipc.2012.6507483 · Cited by 54
A Highly Scalable Parallel Implementation of Balancing Domain Decomposition by Constraints
Badia, S., Martín, A. F., & Príncipe, J. (2014) · SIAM Journal on Scientific Computing · doi:10.1137/130931989 · Cited by 47
Efficient transitive closure of sparse matrices over closed semirings
Penn, G. (2005) · Theoretical Computer Science · doi:10.1016/j.tcs.2005.11.008 · Cited by 41
Optimising Sparse Matrix Vector multiplication for large scale FEM problems on FPGA
Grigoras, P., Burovskiy, P., Luk, W. W., & Sherwin, S. J. (2016) · International Conference on Field Programmable Logic and Applications (FPL) · doi:10.1109/fpl.2016.7577352 · Cited by 35
Cited by
SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning
Wang, H., Zhang, Z., & Han, S. (2021) · 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA) · doi:10.1109/hpca51647.2021.00018 · Cited by 427
“However, it is not friendly to CPUs and GPUs and requires dedicated hardware [23], [24] to support sparse matrix multiplication, which may consume extra efforts for design”
BackgroundSelf-citationHoefler, T., Alistarh, D., Ben-Nun, T., Dryden, N., & Peste, A. (2021) · ETH Zurich · doi:10.3929/ethz-b-000519202 · Cited by 423
Wang, H., Wang, K., Yang, J., Shen, L., Sun, N., Lee, H.-S., & Han, S. (2020) · 2020 57th ACM/IEEE Design Automation Conference (DAC) · doi:10.1109/dac18072.2020.9218757 · Cited by 320
Self-citationHAT: Hardware-Aware Transformers for Efficient Natural Language Processing
Wang, H., Wu, Z., Liu, Z., Cai, H., Zhu, L., Gan, C., & Han, S. (2020) · Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics · doi:10.18653/v1/2020.acl-main.686 · Cited by 227
Self-citationViTCoD: Vision Transformer Acceleration via Dedicated Algorithm and Accelerator Co-Design
You, H., Sun, Z., Shi, H., Yu, Z., Zhao, Y., Zhang, Y., Li, C., Li, B., & Lin, Y. (2023) · 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA) · doi:10.1109/hpca56546.2023.10071027 · Cited by 138
Metadata
- Authors
- Zhang, Z., Wang, H., Han, S., & Dally, W. J.
- Venue
- 2020 IEEE International Symposium on High Performance Computer Architecture (HPCA)
- Publisher
- IEEE
- Published
- 2020-02
- Pages
- 261-274
- ISSN
- 1530-0897 (ISSN-L)
- OpenAlex
- W3016832937
- Cited by
- 277
- References
- 36
- FWCI
- 26.68
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.