The DOI matches its Crossref record; 39 of the 39 references it cites were found in a registry or an index.
OuterSPACE: An Outer Product Based Sparse Matrix Multiplication Accelerator
Abstract
Sparse matrices are widely used in graph and data analytics, machine learning, engineering and scientific applications. This paper describes and analyzes OuterSPACE, an accelerator targeted at applications that involve large sparse matrices. OuterSPACE is a highly-scalable, energy-efficient, reconfigurable design, consisting of massively parallel Single Program, Multiple Data (SPMD)-style processing units, distributed memories, high-speed crossbars and High Bandwidth Memory (HBM). We identify redundant memory accesses to non-zeros as a key bottleneck in traditional sparse matrix-matrix multiplication algorithms. To ameliorate this, we implement an outer product based matrix multiplication technique that eliminates redundant accesses by decoupling multiplication from accumulation. We demonstrate that traditional architectures, due to limitations in their memory hierarchies and ability to harness parallelism in the algorithm, are unable to take advantage of this reduction without incurring significant overheads. OuterSPACE is designed to specifically overcome these challenges. We simulate the key components of our architecture using gem5 on a diverse set of matrices from the University of Florida's SuiteSparse collection and the Stanford Network Analysis Project and show a mean speedup of 7.9× over Intel Math Kernel Library on a Xeon CPU, 13.0× against cuSPARSE and 14.0× against CUSP when run on an NVIDIA K40 GPU, while achieving an average throughput of 2.9 GFLOPS within a 24 W power budget in an area of 87 mm2.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
Binkert, N., Beckmann, B., Black, G., Reinhardt, S. K., Saidi, A., Basu, A., Hestness, J., Hower, D. R., Krishna, T., Sardashti, S., et al. (2011) · ACM SIGARCH Computer Architecture News · doi:10.1145/2024716.2024718 · Cited by 4,930
The 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
Graph 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
CACTI 6.0: A Tool to Model Large Caches
Muralimanohar, N., Balasubramonian, R., & Jouppi, N. P. (2009) · Cited by 836
Ecient Sparse Matrix-Vector Multiplication on CUDA
Bell, N., & Garland, M. (2008) · Cited by 574
SUMMA: scalable universal matrix multiplication algorithm
Van De Geijn, R. A., & Watts, J. (1997) · Concurrency: Practice and Experience · doi:10.1002/(sici)1096-9128(199704)9:4<255::aid-cpe250>3.0.co;2-2 · Cited by 477
The Combinatorial BLAS: design, implementation, and applications
Buluç, A., & Gilbert, J. R. (2011) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342011403516 · Cited by 415
GraphMat: high performance graph analytics made productive
Sundaram, N., Satish, N., Patwary, M. M. A., Dulloor, S. R., Anderson, M. J., Vadlamudi, S. G., Das, D., & Dubey, P. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2809974.2809983 · Cited by 282
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 215
On the representation and multiplication of hypersparse matrices
Buluc, A., & Gilbert, J. R. (2008) · 2008 IEEE International Symposium on Parallel and Distributed Processing · doi:10.1109/ipdps.2008.4536313 · Cited by 201
DeNovo: Rethinking the Memory Hierarchy for Disciplined Parallelism
Choi, B., Komuravelli, R., Sung, H., Smolinski, R., Honarmand, N., Adve, S. V., Adve, V. S., Carter, N. P., & Chou, C.-T. (2011) · 2011 International Conference on Parallel Architectures and Compilation Techniques · doi:10.1109/pact.2011.21 · Cited by 179
Navigating the maze of graph analytics frameworks using massive graph datasets
Satish, N., Sundaram, N., Patwary, M. M. A., Seo, J., Park, J., Hassaan, M. A., Sengupta, S., Yin, Z., & Dubey, P. (2014) · Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2588555.2610518 · Cited by 176
Duff, I., Heroux, M. A., & Pozo, R. (2002) · ACM Transactions on Mathematical Software · doi:10.1145/567806.567810 · Cited by 163
Fast Sparse Matrix-Vector Multiplication by Exploiting Variable Block Structure
Vuduc, R. W., & Moon, H.-J. (2005) · Lecture notes in computer science · doi:10.1007/11557654_91 · Cited by 153
Optimizing Sparse Matrix—Matrix Multiplication for the GPU
Dalton, S., Olson, L. N., & Bell, N. (2015) · ACM Transactions on Mathematical Software · doi:10.1145/2699470 · Cited by 138
Performance Evaluation of Sparse Matrix Multiplication Kernels on Intel Xeon Phi
Saule, É., Kaya, K., & Çatalyürek, Ü. V. (2014) · Lecture notes in computer science · doi:10.1007/978-3-642-55224-3_52 · Cited by 134
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
Maximum 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
A framework for general sparse matrix–matrix multiplication on GPUs and heterogeneous processors
Liu, W., & Vinter, B. (2015) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2015.06.010 · Cited by 110
Accelerating sparse matrix-matrix multiplication with 3D-stacked logic-in-memory hardware
Zhu, Q., Graf, T., Sumbul, H. E., Pileggi, L., & Franchetti, F. (2013) · IEEE High Performance Extreme Computing Conference · doi:10.1109/hpec.2013.6670336 · Cited by 105
Graph Theoretic and Spectral Analysis of Enron Email Data
Chapanond, A., Krishnamoorthy, M. S., & Yener, B. (2005) · Computational and Mathematical Organization Theory · doi:10.1007/s10588-005-5381-4 · Cited by 104
ViennaCL---Linear Algebra Library for Multi- and Many-Core Architectures
Rupp, K., Tillet, P., Rudolf, F., Weinbub, J., Morhammer, A., Grasser, T., Jüngel, A., & Selberherr, S. (2016) · SIAM Journal on Scientific Computing · doi:10.1137/15m1026419 · Cited by 95
GPU-Accelerated Sparse Matrix-Matrix Multiplication by Iterative Row Merging
Gremse, F., Höfter, A., Schwen, L. O., Kiessling, F. M., & Naumann, U. (2015) · SIAM Journal on Scientific Computing · doi:10.1137/130948811 · Cited by 82
Swizzle-Switch Networks for Many-Core Systems
Sewell, K., Dreslinski, R., Manville, T., Satpathy, S. K., Pinckney, N., Blake, G. W., Cieslak, M., Das, R., Wenisch, T. F., Sylvester, D., et al. (2012) · IEEE Journal on Emerging and Selected Topics in Circuits and Systems · doi:10.1109/jetcas.2012.2193936 · Cited by 82
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
Komuravelli, R., Sinclair, M. D., Alsop, J., et al. (2015) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/2749469.2750374 · Cited by 63
Detecting short directed cycles using rectangular matrix multiplication and dynamic programming
Yuster, R., & Zwick, U. (2004) · doi:10.5555/982792.982828 · Cited by 62
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
Colored intersection searching via sparse rectangular matrix multiplication
Kaplan, H. Y., Sharir, M., & Verbin, E. (2006) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/1137856.1137866 · Cited by 52
Caching-efficient multithreaded fast multiplication of sparse matrices
Sulatycke, P. D., & Ghose, K. (2002) · doi:10.1109/ipps.1998.669899 · Cited by 47
Optimal 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 45
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
Alvarez, L., Vilanova, L., Moretó, M., Casas, M., González, M., Martorell, X., Navarro, N., Ayguadé, E., & Valero, M. (2015) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/2749469.2750411 · Cited by 37
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 34
Multilinear algebra and parallel programming
Johnson, R. W., Huang, C., & Johnson, J. R. (1991) · The Journal of Supercomputing · doi:10.1007/bf00127843 · Cited by 30
Gilbert, J. R., & Shah, V. B. (2007) · Cited by 27
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
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
AWB-GCN: A Graph Convolutional Network Accelerator with Runtime Workload Rebalancing
Geng, T., Li, A., Shi, R., Wu, C., Wang, T., Li, Y., Haghi, P., Tumeo, A., Che, S., Reinhardt, S., et al. (2020) · 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1109/micro50266.2020.00079 · Cited by 301
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
- Pal, S., Beaumont, J., Park, D.-H., Amarnath, A., Feng, S., Chakrabarti, C., Kim, H.-S., Blaauw, D., Mudge, T., & Dreslinski, R.
- Venue
- 2018 IEEE International Symposium on High Performance Computer Architecture (HPCA)
- Publisher
- IEEE
- Published
- 2018-02
- Pages
- 724-736
- ISSN
- 1530-0897 (ISSN-L)
- OpenAlex
- W2794952988
- Cited by
- 292
- References
- 39
- FWCI
- 18.50
- 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.