The DOI matches its Crossref record; 21 of the 23 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
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
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 · cited 15×
“When the matrix has dense block substructure, as is common .nite element method-based applications, practitioners employ a blocked variant of CSR (BCSR), which stores a single column index for each r × c block, rather than one per non-zero as in CSR. 2.1 OSKI, OSKI-PETSc, and RelatedWork Wecompareour multicoreSpMV op…”
BackgroundInfluentialDesign challenges of technology scaling
Borkar, S. (1999) · IEEE Micro · doi:10.1109/40.782564 · Cited by 1,164 · cited 1×
“Industry has moved to chip multiprocessor (CMP) system design in order to better manage trade-offs among performance, energy efficiency, and reliability [5, 9].”
BackgroundOptimization of sparse matrix–vector multiplication on emerging multicore platforms
Williams, S., Oliker, L., Vuduc, R., Shalf, J., Yelick, K., & Demmel, J. (2009) · Parallel Computing · doi:10.1016/j.parco.2008.12.006 · Cited by 789
Self-citationOSKI: 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 · cited 5×
“, symmetry, advanced register blocking, A methods [20]) as a key algorithmic optimization .”
BackgroundMethodResultInfluentialSelf-citationRose, D. J. (1972) · Elsevier eBooks · doi:10.1016/b978-1-4832-3187-7.50018-0 · Cited by 449 · cited 1×
“Besides classical bandwidth-reducing reordering techniques [15], recent work has proposed sophisticated 2-D partitioning schemes with theoretical guarantees on communication volume [18], and traveling salesman-based reordering to create dense block substructure [14].”
MethodSynergistic 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 · cited 1×
“Cell adopts a heterogeneous approach to multicore, with one conventional processor core (Power Processing Element / PPE) to handle OS and control functions, combined with up to eight simpler SIMD cores (Synergistic Processing Elements / SPEs) for the computationally intensive work [7, 8].”
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 · cited 6×
“These patterns include blocks [10], variable or mixtures of differently-sized blocks [6] diagonals, which may be especially well-suited to machines with SIMD and vector units [19], dense subtriangles arising in sparse triangular solve [22], and symmetry [11], and combinations.”
BackgroundMethodInfluentialSelf-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 · cited 1×
“Besides classical bandwidth-reducing reordering techniques [15], recent work has proposed sophisticated 2-D partitioning schemes with theoretical guarantees on communication volume [18], and traveling salesman-based reordering to create dense block substructure [14].”
MethodImproving 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 · cited 1×
“Recent work on low-level tuning of SpMV by unroll-and-jam [12], software pipelining [6], and prefetching [ 17 ] influence our work.”
Background
Research works printed but not linked: 7
- 10.5555/266469.266486 · doi:10.5555/266469.266486
- J. L. Hennessy and D. A. Patterson . Computer Architecture: A Quantitative Approach ; fourth edition. Morgan Kaufmann , San Francisco , 2006 . J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach; fourth edition. Morgan Kaufmann, San Francisco, 2006.
- 10.5555/1018425.1020284 · doi:10.5555/1018425.1020284
- J. Mellor-Crummey and J. Garvin . Optimizing sparse matrix vector multiply using unroll-and-jam . In Proc. LACSI Symposium , Santa Fe, NM, USA , October 2002 . J. Mellor-Crummey and J. Garvin. Optimizing sparse matrix vector multiply using unroll-and-jam. In Proc. LACSI Symposium, Santa Fe, NM, USA, October 2002.
- R. Vuduc , A. Gyulassy , J. W. Demmel , and K. A. Yelick . Memory hierarchy optimizations and bounds for sparse ATAx . In Proceedings of the ICCS Workshop on Parallel Linear Algebra , volume LNCS, Melbourne, Australia, June 2003 . Springer. R. Vuduc, A. Gyulassy, J. W. Demmel, and K. A. Yelick. Memory hierarchy optimizations and bounds for sparse ATAx. In Proceedings of the ICCS Workshop on Parallel Linear Algebra, volume LNCS, Melbourne, Australia, June 2003. Springer.
- J. W. Willenbring , A. A. Anda , and M. Heroux . Improving sparse matrix-vector product kernel performance and availabillity . In Proc. Midwest Instruction and Computing Symposium, Mt . Pleasant, IA , 2006 . J. W. Willenbring, A. A. Anda, and M. Heroux. Improving sparse matrix-vector product kernel performance and availabillity. In Proc. Midwest Instruction and Computing Symposium, Mt. Pleasant, IA, 2006.
- 10.1017/s10766-007-0034-5 · doi:10.1017/s10766-007-0034-5
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
“All of our experiments are run on a system comprised of an NVIDIA GTX 285 GPU paired with an Intel Core i7 965 CPU.”
BackgroundInfluentialDebunking 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
“SpMV (SpMV) [50, 8, 47] Sparse Solver Gather Across non-zero BW bound for typical large matrices”
BackgroundA 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-citationEcient Sparse Matrix-Vector Multiplication on CUDA
Bell, N., & Garland, M. (2008) · Cited by 574
Metadata
- Authors
- Williams, S., Oliker, L., Vuduc, R., Shalf, J., Yelick, K., & Demmel, J.
- Affiliations
- Lawrence Berkeley National Laboratory (US)
- Georgia Institute of Technology (US)
- University of California, Berkeley (US)
- Corresponding author
- Williams, Samuel
- Venue
- Proceedings of the 2007 ACM/IEEE conference on Supercomputing
- Publisher
- ACM
- Published
- 2007-11-10
- Volume
- 35
- Issue
- 3
- Pages
- 1-12
- ISSN
- 0167-8191 (ISSN-L)
- OpenAlex
- W1527464046
- Cited by
- 791
- References
- 23
- Citations by year
- 2026: 7 · 2025: 13 · 2024: 14 · 2023: 17 · 2022: 20 · 2021: 34 · 2020: 27 · 2019: 41 · 2018: 41 · 2017: 33 · 2016: 57 · 2015: 56 · 2014: 78 · 2013: 66 · 2012: 63
- FWCI
- 93.97
- Type
- journal article
- Language
- en
- Open access
- green
- escholarship.org
- Locations
- Parallel Computing (publishedVersion)
- ACM/IEEE Conference on Supercomputing (SC) (publishedVersion)
- eScholarship (California Digital Library) (submittedVersion, cc-by)
- eScholarship (California Digital Library) (submittedVersion)
- OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
- University of North Texas Digital Library (University of North Texas) (submittedVersion)
- Lawrence Berkeley National Laboratory
- OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information)
- Funders
- Office of Science (DE-AC02-05CH11231)
- Advanced Scientific Computing Research (DE-AC02-05CH11231)
- Topics
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed and Parallel Computing Systems
- Keywords
- sparse matrix-vector multiplication, multi-core processors, Cell processor, multithreading
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.