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.
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
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 587
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-citation
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
Towards dense linear algebra for hybrid GPU accelerated manycore systems
Tomov, S., Dongarra, J., & Baboulin, M. (2010) · Parallel Computing · doi:10.1016/j.parco.2009.12.005 · Cited by 451
Program optimization space pruning for a multithreaded gpu
Ryoo, S., Rodrigues, C. I., Stone, S. S., Baghsorkhi, S. S., Ueng, S.-Z., Stratton, J. A., & Hwu, W.-M. W. (2008) · Proceedings of the 6th annual IEEE/ACM international symposium on Code generation and optimization · doi:10.1145/1356058.1356084 · Cited by 285
Program optimization carving for GPU computing
Ryoo, S., Rodrigues, C. I., Stone, S. S., Stratton, J. A., Ueng, S.-Z., Baghsorkhi, S. S., & Hwu, W.-M. W. (2008) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2008.05.011 · Cited by 126
Bandwidth-Optimal Random Shuffling for GPUs
Mitchell, R., Stokes, D., Frank, E., & Holmes, G. (2022) · ACM Transactions on Parallel Computing · doi:10.1145/3505287 · Cited by 6
“Notable examples are matrix multiplication [10, 16, 26], image processing [9, 44], deep neural networks [11, 12, 46], and sorting [22, 56].”
Background
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Understanding the efficiency of GPU algorithms for matrix-matrix multiplication. https://app.cochat.ai/papers/10.1145/1058129.1058148
- The paper
- Fatahalian, K., Sugerman, J., & Hanrahan, P. (2004). Understanding the efficiency of GPU algorithms for matrix-matrix multiplication. Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware. https://doi.org/10.1145/1058129.1058148
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.
