The DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.
Understanding the efficiency of GPU algorithms for matrix-matrix multiplication
Abstract
Utilizing graphics hardware for general purpose numerical computations has become a topic of considerable interest. The implementation of streaming algorithms, typified by highly parallel computations with little reuse of input data, has been widely explored on GPUs. We relax the streaming model's constraint on input reuse and perform an in-depth analysis of dense matrix-matrix multiplication, which reuses each element of input matrices O(n) times. Its regular data access pattern and highly parallel computational requirements suggest matrix-matrix multiplication as an obvious candidate for efficient evaluation on GPUs but, surprisingly we find even near-optimal GPU implementations are pronouncedly less efficient than current cache-aware CPU approaches. We find the key cause of this inefficiency is that the GPU can fetch less data and yet execute more arithmetic operations per clock than the CPU when both are operating out of their closest caches. The lack of high bandwidth access to cached data will impair the performance of GPU implementations of any computation featuring significant input reuse.
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
Anderson, E., Bai, Z., Bischof, C., Blackford, L. S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., et al. (1999) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719604 · Cited by 4,435
Automated empirical optimizations of software and the ATLAS project
Clint Whaley, R., Petitet, A., & Dongarra, J. J. (2001) · Parallel Computing · doi:10.1016/s0167-8191(00)00087-9 · Cited by 1,317
Brook for GPUs: stream computing on graphics hardware
Buck, I., Foley, T., Horn, D., Sugerman, J., Fatahalian, K., Houston, M., & Hanrahan, P. (2004) · ACM Transactions on Graphics · doi:10.1145/1015706.1015800 · Cited by 1,155
Self-citationSparse matrix solvers on the GPU: conjugate gradients and multigrid
Bolz, J., Farmer, I., Grinspun, E., & Schröder, P. (2005) · ACM SIGGRAPH 2005 Courses on - SIGGRAPH '05 · doi:10.1145/1198555.1198781 · Cited by 741
Linear algebra operators for GPU implementation of numerical algorithms
Krüger, J., & Westermann, R. (2005) · ACM SIGGRAPH 2005 Courses on - SIGGRAPH '05 · doi:10.1145/1198555.1198795 · Cited by 610
The microarchitecture of the Pentium 4 processor
Hinton, G. (2001) · Medical Entomology and Zoology · Cited by 608
Sparse matrix solvers on the GPU: conjugate gradients and multigrid
Bolz, J., Farmer, I., Grinspun, E., & Schröder, P. (2003) · ACM Transactions on Graphics · doi:10.1145/882262.882364 · Cited by 540
Linear algebra operators for GPU implementation of numerical algorithms
Krüger, J., & Westermann, R. (2003) · ACM Transactions on Graphics · doi:10.1145/882262.882363 · Cited by 380
Moreland, K., & Angel, E. S. (2003) · SIGGRAPH/EUROGRAPHICS Conference On Graphics Hardware · doi:10.5555/844174.844191 · Cited by 287
Brook for GPUs: stream computing on graphics hardware
Buck, I., Foley, T., Horn, D., Sugerman, J., Fatahalian, K., Houston, M., & Hanrahan, P. (2004) · ACM SIGGRAPH 2004 Papers · doi:10.1145/1186562.1015800 · Cited by 254
Self-citationFast matrix multiplies using graphics hardware
Larsen, E. S., & McAllister, D. (2001) · Proceedings of the 2001 ACM/IEEE conference on Supercomputing · doi:10.1145/582034.582089 · Cited by 216
LAPACK Users' guide (third ed.)
Anderson, E., Bai, Z., Bischof, C. H., Blackford, L. S., Demmel, J. W., Dongarra, J. J., Croz, J. D., Hammarling, S. J., Greenbaum, A. B., McKenney, A., et al. (1999) · Society for Industrial and Applied Mathematics eBooks · Cited by 178
Physically-based visual simulation on graphics hardware
Harris, M., Coombe, G., Scheuermann, T., & Lastra, A. (2002) · SIGGRAPH/EUROGRAPHICS Conference On Graphics Hardware · doi:10.5555/569046.569061 · Cited by 169
Cache and bandwidth aware matrix multiplication on the GPU
Hall, J. D., Carr, N., & Hart, J. C. (2010) · Cited by 74
Cited by
A Survey of General‐Purpose Computation on Graphics Hardware
Owens, J. D., Luebke, D., Govindaraju, N., Harris, M., Krüger, J., Lefohn, A. E., & Purcell, T. J. (2007) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2007.01012.x · Cited by 2,101
Owens, J. D., Houston, M., Luebke, D., Green, S., Stone, J. E., & Phillips, J. C. (2008) · Proceedings of the IEEE · doi:10.1109/jproc.2008.917757 · Cited by 1,495
Optimization principles and application performance evaluation of a multithreaded GPU using CUDA
Ryoo, S., Rodrigues, C. I., Baghsorkhi, S. S., Stone, S. S., Kirk, D. B., & Hwu, W.-M. W. (2008) · Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming · doi:10.1145/1345206.1345220 · Cited by 903
Benchmarking GPUs to tune dense linear algebra
Volkov, V. M., & Demmel, J. W. (2008) · doi:10.5555/1413370.1413402 · Cited by 701
Hu, M., Strachan, J. P., Li, Z., Grafals, E. M., Davila, N., Graves, C., Lam, S., Ge, N., Yang, J. J., & Williams, R. S. (2016) · Proceedings of the 53rd Annual Design Automation Conference · doi:10.1145/2897937.2898010 · Cited by 686
Metadata
- Authors
- Fatahalian, K., Sugerman, J., & Hanrahan, P.
- Venue
- Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware
- Publisher
- ACM
- Published
- 2004-08-29
- Pages
- 133-137
- OpenAlex
- W2139774022
- Cited by
- 309
- References
- 14
- FWCI
- 11.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.