ExTensor: An Accelerator for Sparse Tensor Algebra
The DOI matches its Crossref record; 41 of the 41 references it cites were found in a registry or an index.
Abstract
Generalized tensor algebra is a prime candidate for acceleration via customized ASICs. Modern tensors feature a wide range of data sparsity, with the density of non-zero elements ranging from 10-6% to 50%. This paper proposes a novel approach to accelerate tensor kernels based on the principle of hierarchical elimination of computation in the presence of sparsity. This approach relies on rapidly finding intersections---situations where both operands of a multiplication are non-zero---enabling new data fetching mechanisms and avoiding memory latency overheads associated with sparse kernels implemented in software.
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
Deep Residual Learning for Image Recognition
He, K., Zhang, X., Ren, S., & Sun, J. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.90 · Cited by 235,474 · cited 1×
“MTTKRP is used in tensor decompositions [27], 2D Conv is used in image processing applications, and CNN layers are the core kernels in state-of-the-art image recognition [22, 29].”
MethodImageNet classification with deep convolutional neural networks
Krizhevsky, A., Sutskever, I., & Hinton, G. E. (2017) · Communications of the ACM · doi:10.1145/3065386 · Cited by 112,155
TensorFlow: A system for large-scale machine learning
Abadi, M., Barham, P., Chen, J., Chen, Z., Davis, A., Dean, J., Devin, M., Ghemawat, S., Irving, G., Isard, M., et al. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.08695 · Cited by 11,822
Tensor Decompositions and Applications
Kolda, T. G., & Bader, B. W. (2009) · SIAM Review · doi:10.1137/07070111x · Cited by 10,301
In-Datacenter Performance Analysis of a Tensor Processing Unit
Jouppi, N. P., Young, C., Patil, N., Patterson, D., Agrawal, G., Bajwa, R., Bates, S., Bhatia, S., Boden, N., Borchers, A., et al. (2017) · Proceedings of the 44th Annual International Symposium on Computer Architecture · doi:10.1145/3079856.3080246 · Cited by 4,537 · cited 1×
“Accelerator designs targeting tensor algebra [2, 8, 24, 33, 36, 40, 41] and machine learning [4, 12, 13, 21, 25, 32, 42, 44, 51] are receiving signiicant attention.”
BackgroundThe 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
Hidden factors and hidden topics: understanding rating dimensions with review text
McAuley, J., & Leskovec, J. (2013) · Proceedings of the 7th ACM conference on Recommender systems · doi:10.1145/2507157.2507163 · Cited by 1,564 · cited 1×
“Recently, there has been a surge of interest in generalized tensor algebra in the ields of deep learning [1, 15], machine learning [5], data science [7, 9, 27, 35, 48], physical sciences [18], engineering [20, 28], and graph analytics [34].”
BackgroundBennett, J. R., & Lanning, S. (2007) · Cited by 1,466
On the evolution of user interaction in facebook
Viswanath, B., Mislove, A., Cha, M., & Gummadi, K. P. (2009) · Proceedings of the 2nd ACM workshop on Online social networks · doi:10.1145/1592665.1592675 · Cited by 1,461 · cited 1×
“Recently, there has been a surge of interest in generalized tensor algebra in the ields of deep learning [1, 15], machine learning [5], data science [7, 9, 27, 35, 48], physical sciences [18], engineering [20, 28], and graph analytics [34].”
BackgroundIn-Datacenter Performance Analysis of a Tensor Processing Unit
Jouppi, N. P., Young, C., Patil, N., Patterson, D., Agrawal, G., Bajwa, R., Bates, S., Bhatia, S., Boden, N., Borchers, A., et al. (2017) · ACM SIGARCH Computer Architecture News · doi:10.1145/3140659.3080246 · Cited by 1,240
Eyeriss: a spatial architecture for energy-efficient dataflow for convolutional neural networks
Chen, Y.-H., Emer, J., & Sze, V. (2016) · ACM SIGARCH Computer Architecture News · doi:10.1145/3007787.3001177 · Cited by 1,182
Self-citationCACTI 6.0: A Tool to Model Large Caches
Muralimanohar, N., Balasubramonian, R., & Jouppi, N. P. (2009) · Cited by 1,163
Eyeriss v2: A Flexible Accelerator for Emerging Deep Neural Networks on Mobile Devices
Chen, Y.-H., Yang, T.-J., Emer, J. S., & Sze, V. (2019) · IEEE Journal on Emerging and Selected Topics in Circuits and Systems · doi:10.1109/jetcas.2019.2910232 · Cited by 1,106
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
SCNN: 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-citationAn updated set of basic linear algebra subprograms (BLAS)
(2002) · ACM Transactions on Mathematical Software · doi:10.1145/567806.567807 · Cited by 834
Tensor decompositions for learning latent variable models
(2012) · arXiv (Cornell University) · doi:10.5555/2627435.2697055 · Cited by 779 · cited 1×
“Recently, there has been a surge of interest in generalized tensor algebra in the ields of deep learning [1, 15], machine learning [5], data science [7, 9, 27, 35, 48], physical sciences [18], engineering [20, 28], and graph analytics [34].”
BackgroundCnvlutin: ineffectual-neuron-free deep neural network computing
Albericio, J., Judd, P., Hetherington, T., Aamodt, T., Jerger, N. E., & Moshovos, A. (2016) · ACM SIGARCH Computer Architecture News · doi:10.1145/3007787.3001138 · Cited by 614
A literature survey of low‐rank tensor approximation techniques
Grasedyck, L., Kressner, D., & Tobler, C. (2013) · GAMM-Mitteilungen · doi:10.1002/gamm.201310004 · Cited by 577 · cited 1×
“Recently, there has been a surge of interest in generalized tensor algebra in the ields of deep learning [1, 15], machine learning [5], data science [7, 9, 27, 35, 48], physical sciences [18], engineering [20, 28], and graph analytics [34].”
BackgroundWang, E., Zhang, Q., Shen, B., Zhang, G., Lu, X., Wu, Q., & Wang, Y. (2014) · High-Performance Computing on the Intel® Xeon Phi™ · doi:10.1007/978-3-319-06486-4_7 · Cited by 506
Cichocki, A., Lee, N., Oseledets, I., Phan, A.-H., Zhao, Q., & Mandic, D. P. (2016) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000059 · Cited by 456 · cited 1×
“Recently, there has been a surge of interest in generalized tensor algebra in the ields of deep learning [1, 15], machine learning [5], data science [7, 9, 27, 35, 48], physical sciences [18], engineering [20, 28], and graph analytics [34].”
BackgroundKjolstad, F., Kamil, S., Chou, S., Lugato, D., & Amarasinghe, S. (2017) · Proceedings of the ACM on Programming Languages · doi:10.1145/3133901 · Cited by 358 · cited 8×
“The accelerator is not Turing complete, but is designed to compute all algebra equations accepted by the TACO Tensor Algebra Compiler [26].”
MethodInfluentialOuterSPACE: 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 · cited 13×
“We evaluate two variants of GEMM: Sparse-Sparse GEMM (SpMSpM, or SpGEMM): In this kernel, a sparse matrix is multiplied by a sparse matrix.”
BackgroundInfluentialMAERI: Enabling Flexible Dataflow Mapping over DNN Accelerators via Reconfigurable Interconnects
Kwon, H., Samajdar, A., & Krishna, T. (2018) · Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/3173162.3173176 · Cited by 270
PuDianNao: A Polyvalent Machine Learning Accelerator
Liu, D., Chen, T., Liu, S., Zhou, J., Zhou, S., Teman, O., Feng, X., Zhou, X., & Chen, Y. (2015) · Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/2694344.2694358 · Cited by 240
Plasticine: A Reconfigurable Architecture For Parallel Paterns
Prabhakar, R., Zhang, Y., Koeplinger, D., Feldman, M., Zhao, T., Hadjis, S., Pedram, A., Kozyrakis, C., & Olukotun, K. (2017) · Proceedings of the 44th Annual International Symposium on Computer Architecture · doi:10.1145/3079856.3080256 · Cited by 239
Tensor-matrix products with a compressed sparse tensor
Smith, S., & Karypis, G. (2015) · Irregular Applications: Architectures and Algorithms · doi:10.1145/2833179.2833183 · Cited by 147
Format abstraction for sparse tensor algebra compilers
Chou, S., Kjølstad, F., & Amarasinghe, S. P. (2018) · Proceedings of the ACM on Programming Languages · doi:10.1145/3276493 · Cited by 146
Energy-Efficient Floating-Point Unit Design
Galal, S., & Horowitz, M. (2010) · IEEE Transactions on Computers · doi:10.1109/tc.2010.121 · Cited by 132
Buffets: An Efficient and Composable Storage Idiom for Explicit Decoupled Data Orchestration
Pellauer, M., Shao, Y. S., Clemons, J., Crago, N. C., Hegde, K., Venkatesan, R., Keckler, S. W., Fletcher, C. W., & Emer, J. (2019) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/3297858.3304025 · Cited by 114
Self-citationAktulga, H. M., Buluç, A., Williams, S., & Yang, C. (2014) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2014.125 · Cited by 108
Scaling betweenness centrality using communication-efficient sparse matrix multiplication
Solomonik, E., Besta, M., Vella, F., & Hoefler, T. (2017) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/3126908.3126971 · Cited by 105
Self-citationMorph: Flexible Acceleration for 3D CNN-Based Video Understanding
Hegde, K., Agrawal, R., Yao, Y., & Fletcher, C. W. (2018) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1109/micro.2018.00080 · Cited by 95
Self-citationSparse 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 65
Eyeriss v2: A Flexible and High-Performance Accelerator for Emerging Deep Neural NetworksPreprint
Chen, Y., Emer, J., & Sze, V. (2018) · arXiv (Cornell University) · Cited by 63
Self-citationOptimal Sparse Matrix Dense Vector Multiplication in the I/O-Model
Bender, M. A., Brodal, G. S., Fagerberg, R., Jacob, R., & Vicari, E. (2010) · Theory of Computing Systems · doi:10.1007/s00224-010-9285-4 · Cited by 55 · cited 2×
“Accelerator designs targeting tensor algebra [2, 8, 24, 33, 36, 40, 41] and machine learning [4, 12, 13, 21, 25, 32, 42, 44, 51] are receiving signiicant attention.”
BackgroundTensor Decompositions for Learning Latent Variable Models (A Survey for ALT)
Anandkumar, A., Ge, R., Hsu, D., Kakade, S. M., & Telgarsky, M. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-24486-0_2 · Cited by 47
Improving performance of sparse matrix dense matrix multiplication on large-scale parallel systems
Acer, S., Selvitopi, O., & Aykanat, C. (2016) · Parallel Computing · doi:10.1016/j.parco.2016.10.001 · Cited by 40 · cited 2×
“Accelerator designs targeting tensor algebra [2, 8, 24, 33, 36, 40, 41] and machine learning [4, 12, 13, 21, 25, 32, 42, 44, 51] are receiving signiicant attention.”
BackgroundSparse Matrix Multiplication On An Associative Processor
Yavits, L., Morad, A., & Ginosar, R. (2014) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2014.2370055 · Cited by 39
Fine-grained accelerators for sparse machine learning workloads
Mishra, A. K., Nurvitadhi, E., Venkatesh, G., Pearce, J., & Marr, D. (2017) · Asia and South Pacific Design Automation Conference (ASP-DAC) · doi:10.1109/aspdac.2017.7858395 · Cited by 23
High Performance Machine Learning through Codesign and Rooflining
Zhao, H. (2014) · eScholarship (California Digital Library) · Cited by 16
Cited by
SIGMA: A Sparse and Irregular GEMM Accelerator with Flexible Interconnects for DNN Training
Qin, E., Samajdar, A., Kwon, H., Nadella, V., Srinivasan, S., Das, D., Kaul, B., & Krishna, T. (2020) · 2020 IEEE International Symposium on High Performance Computer Architecture (HPCA) · doi:10.1109/hpca47549.2020.00015 · Cited by 487
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
Hoefler, T., Alistarh, D., Ben-Nun, T., Dryden, N., & Peste, A. (2021) · ETH Zurich · doi:10.3929/ethz-b-000519202 · Cited by 423
SpArch: Efficient Architecture for Sparse Matrix Multiplication
Zhang, Z., Wang, H., Han, S., & Dally, W. J. (2020) · 2020 IEEE International Symposium on High Performance Computer Architecture (HPCA) · doi:10.1109/hpca47549.2020.00030 · Cited by 277
ViTCoD: 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
- Hegde, K., Asghari-Moghaddam, H., Pellauer, M., Crago, N., Jaleel, A., Solomonik, E., Emer, J., & Fletcher, C. W.
- Venue
- Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture
- Publisher
- ACM
- Published
- 2019-10-12
- Pages
- 319-333
- ISSN
- 1072-4451 (ISSN-L)
- OpenAlex
- W2979310060
- Cited by
- 235
- References
- 41
- FWCI
- 19.94
- Type
- conference paper
- Language
- en
- Open access
- closed
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.