The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Optimization of sparse matrix–vector multiplication on emerging multicore platforms
Open accessAbstract
We are witnessing a dramatic change in computer architecture due to the multicore paradigm shift, as every electronic device from cell phones to supercomputers confronts parallelism of unprecedented scale. To fully unleash the potential of these systems, the HPC community must develop multicore specific optimization methodologies for important scientific computations. In this work, we examine sparse matrix-vector multiply (SpMV) - one of the most heavily used kernels in scientific computing - across a broad spectrum of multicore designs. Our experimental platform includes the homogeneous AMD dual-core and Intel quad-core designs, the heterogeneous STI Cell, as well as the first scientific study of the highly multithreaded Sun Niagara2. We present several optimization strategies especially effective for the multicore environment, and demonstrate significant performance improvements compared to existing state-of-the-art serial and parallel SpMV implementations. Additionally, we present key insights into the architectural tradeoffs of leading multicore design strategies, in the context of demanding memory-bound numerical algorithms.
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
Efficient Management of Parallelism in Object-Oriented Numerical Software Libraries
Balay, S., Gropp, W. D., McInnes, L. C., & Smith, B. F. (1997) · Modern Software Tools for Scientific Computing · doi:10.1007/978-1-4612-1986-6_8 · Cited by 2,009
Design challenges of technology scaling
Borkar, S. (1999) · IEEE Micro · doi:10.1109/40.782564 · Cited by 1,164
OSKI: A library of automatically tuned sparse matrix kernels
Vuduc, R., Demmel, J. W., & Yelick, K. A. (2005) · Journal of Physics: Conference Series · doi:10.1088/1742-6596/16/1/071 · Cited by 490
Self-citationRose, D. J. (1972) · Elsevier eBooks · doi:10.1016/b978-1-4832-3187-7.50018-0 · Cited by 449
Synergistic Processing in Cell's Multicore Architecture
Gschwind, M. K., Hofstee, H. P., Flachs, B., Hopkins, M. E., Watanabe, Y., & Yamazaki, T. (2006) · IEEE Micro · doi:10.1109/mm.2006.41 · Cited by 403
Sparsity: Optimization Framework for Sparse Matrix Kernels
Im, E.-J., Yelick, K., & Vuduc, R. (2004) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342004041296 · Cited by 339
Self-citationA Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication
Vastenhouw, B., & Bisseling, R. H. (2005) · SIAM Review · doi:10.1137/s0036144502409019 · Cited by 274
Improving performance of sparse matrix-vector multiplication
Pinar, A., & Heath, M. T. (1999) · Proceedings of the 1999 ACM/IEEE conference on Supercomputing · doi:10.1145/331532.331562 · Cited by 250
Improving the memory-system performance of sparse-matrix vector multiplication
Toledo, S. (1997) · IBM Journal of Research and Development · doi:10.1147/rd.416.0711 · Cited by 207
Accelerating sparse matrix computations via data compression
Willcock, J. J., & Lumsdaine, A. (2006) · International Conference on Supercomputing · doi:10.1145/1183401.1183444 · Cited by 142
Chip multiprocessing and the cell broadband engine
Gschwind, M. K. (2006) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/1128022.1128023 · Cited by 133
When cache blocking of sparse matrix vector multiply works and why
Nishtala, R., Vuduc, R. W., Demmel, J. W., & Yelick, K. (2007) · Applicable Algebra in Engineering Communication and Computing · doi:10.1007/s00200-007-0038-9 · Cited by 103
Self-citationCharacterizing the behavior of sparse algorithms on caches
Temam, O., & Jalby, W. (1992) · doi:10.5555/147877.148091 · Cited by 83
Sparse Tiling for Stationary Iterative Methods
Strout, M. M., Carter, L., Jeanne Ferrante, Y., & Kreaseck, B. (2004) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342004041294 · Cited by 67
Scientific Computing Kernels on the Cell Processor
Williams, S., Shalf, J. M., Oliker, L., Kamil, S. A., Husbands, P., & Yelick, K. (2007) · International Journal of Parallel Programming · doi:10.1007/s10766-007-0034-5 · Cited by 62
Self-citationPerformance models for evaluation and automatic tuning of symmetric sparse matrix-vector multiply
Lee, B. C., Vuduc, R. W., Demmel, J. W., & Yelick, K. (2004) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2004.1327917 · Cited by 32
Self-citationAutomatic Performance Tuning and Analysis of Sparse Triangular Solve
Shoaib, R. V., Hsu, K. J., Nishtala, R., Demmel, J. W., & Yelick, K. (2002) · Cited by 28
Self-citationMemory Hierarchy Optimizations and Performance Bounds for Sparse A T Ax
Vuduc, R. W., Gyulassy, A. G., Demmel, J. W., & Yelick, K. (2003) · Lecture notes in computer science · doi:10.1007/3-540-44863-2_69 · Cited by 20
Self-citation
Research works printed but not linked: 6
- Kourtis, 2008, Optimizing sparse matrix–vector multiplication using index and value compression, In Conf. Computing Frontiers, 87
- J. Mellor-Crummey, J. Garvin, Optimizing sparse matrix vector multiply using unroll-and-jam, in: Proceedings of the LACSI Symposium, Santa Fe, NM, USA, October 2002.
- R. Vuduc, Automatic performance tuning of sparse matrix kernels, PhD Thesis, University of California, Berkeley, Berkeley, CA, USA, December 2003.
- J.B. White, P. Sadayappan, On improving the performance of sparse matrix–vector multiplication, in: Proceedings of the International Conference on High-Performance Computing, 1997.
- J.W. Willenbring, A.A. Anda, M. Heroux, Improving sparse matrix–vector product kernel performance and availabillity, in: Proceedings of the Midwest Instruction and Computing Symposium, Mt. Pleasant, IA, 2006.
- S. Williams, L. Oliker, R. Vuduc, J. Shalf, K. Yelick, J. Demmel, Optimization of sparse matrix–vector multiplication on emerging multicore platforms, in: Proceedings of the Supercomputing, 2007. · DOI · Paper page
Cited by
Williams, S., Waterman, A., & Patterson, D. A. (2009) · Communications of the ACM · doi:10.1145/1498765.1498785 · Cited by 2,798
Self-citationImplementing sparse matrix-vector multiplication on throughput-oriented processors
Bell, N., & Garland, M. (2009) · Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis · doi:10.1145/1654059.1654078 · Cited by 900
Optimization of sparse matrix-vector multiplication on emerging multicore platforms
Williams, S., Oliker, L., Vuduc, R., Shalf, J., Yelick, K., & Demmel, J. (2007) · Proceedings of the 2007 ACM/IEEE conference on Supercomputing · doi:10.1145/1362622.1362674 · Cited by 791
Self-citationDebunking the 100X GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU
Lee, V. W., Kim, C., Chhugani, J., Deisher, M., Kim, D., Nguyen, A. D., Satish, N., Smelyanskiy, M., Chennupaty, S., Hammarlund, P., et al. (2010) · Proceedings of the 37th annual international symposium on Computer architecture · doi:10.1145/1815961.1816021 · Cited by 640
A view of the parallel computing landscape
Asanovic, K., Bodik, R., Demmel, J., Keaveny, T., Keutzer, K., Kubiatowicz, J., Morgan, N., Patterson, D., Sen, K., Wawrzynek, J., et al. (2009) · Communications of the ACM · doi:10.1145/1562764.1562783 · Cited by 627
Self-citation
Metadata
- Authors
- Williams, S., Oliker, L., Vuduc, R., Shalf, J., Yelick, K., & Demmel, J.
- Venue
- Parallel Computing
- Publisher
- Elsevier BV
- Published
- 2009-03
- Volume
- 35
- Issue
- 3
- Pages
- 178-194
- ISSN
- 0167-8191 (ISSN-L)
- OpenAlex
- W1527464046
- Cited by
- 789
- References
- 18
- FWCI
- 94.34
- Type
- journal article
- Language
- en
- Open access
- green
- Licence
- www.elsevier.com/tdm/userlicense/1.0/ (tdm)
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.