The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Sparsity: Optimization Framework for Sparse Matrix Kernels
Abstract
Sparse matrix–vector multiplication is an important computational kernel that performs poorly on most modern processors due to a low compute-to-memory ratio and irregular memory access patterns. Optimization is difficult because of the complexity of cache-based memory systems and because performance is highly dependent on the non-zero structure of the matrix. The SPARSITY system is designed to address these problems by allowing users to automatically build sparse matrix kernels that are tuned to their matrices and machines. SPARSITY combines traditional techniques such as loop transformations with data structure transformations and optimization heuristics that are specific to sparse matrices. It provides a novel framework for selecting optimization parameters, such as block size, using a combination of performance models and search. In this paper we discuss the optimization of two operations: a sparse matrix times a dense vector and a sparse matrix times a set of dense vectors. Our experience indicates that register level optimizations are effective for matrices arising in certain scientific simulations, in particular finite-element problems. Cache level optimizations are important when the vector used in multiplication is larger than the cache size, especially for matrices in which the non-zero structure is random. For applications involving multiple vectors, reorganizing the computation to perform the entire set of multiplications as a single operation produces significant speedups. We describe the different optimizations and parameter selection techniques and evaluate them on several machines using over 40 matrices taken from a broad set of application domains. Our results demonstrate speedups of up to 4× for the single vector case and up to 10× for the multiple vector case.
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
Computer Architecture: A Quantitative Approach
Hennessy, J. L., & Patterson, D. A. (1989) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 9,375
Using Linear Algebra for Intelligent Information Retrieval
Berry, M. W., Dumais, S. T., & O’Brien, G. W. (1995) · SIAM Review · doi:10.1137/1037127 · Cited by 1,481
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
Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide
Demmel, J. W., Dongarra, J. J., Ruhe, A., van der Vorst, H. A., & Bai, Z. (1987) · Medical Entomology and Zoology · Cited by 1,102
Computer architecture (2nd ed.): a quantitative approach
Hennessy, J. L., & Patterson, D. A. (1996) · Morgan Kaufmann Publishers Inc. eBooks · Cited by 1,053
Computer Architecture: A Quantitative Approach, 2nd Edition
Hennessy, J. L., & Patterson, D. A. (1996) · Cited by 1,015
The cache performance and optimizations of blocked algorithms
Lam, M. D., Rothberg, E. E., & Wolf, M. E. (1991) · Proceedings of the fourth international conference on Architectural support for programming languages and operating systems - ASPLOS-IV · doi:10.1145/106972.106981 · Cited by 921
Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide
(2000) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719581 · Cited by 670
Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology
Bilmes, J., Asanovic, K., Chin, C.-W., & Demmel, J. (2014) · 25th Anniversary International Conference on Supercomputing Anniversary Volume - · doi:10.1145/2591635.2667174 · Cited by 453
A Shifted Block Lanczos Algorithm for Solving Sparse Symmetric Generalized Eigenproblems
Grimes, R. G., Lewis, J. G., & Simon, H. D. (1994) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479888151111 · Cited by 436
Motion segmentation and tracking using normalized cuts
Shi, J., & Malik, J. (2002) · Sixth International Conference on Computer Vision (IEEE Cat. No.98CH36271) · doi:10.1109/iccv.1998.710861 · Cited by 336
Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology
Bilmes, J., Asanovic, K., Chin, C.-W., & Demmel, J. (1997) · Proceedings of the 11th international conference on Supercomputing - ICS '97 · doi:10.1145/263580.263662 · Cited by 308
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
A Technique for Accelerating the Convergence of Restarted GMRES
Baker, A. H., Jessup, E. R., & Manteuffel, T. (2005) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479803422014 · Cited by 230
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
Optimizing the Performance of Sparse Matrix-Vector Multiplication
Im, E. (2000) · UC Berkeley · Cited by 120
Self-citationOptimizing Sparse Matrix Vector Multiplication on SMP.
Im, E.-J., & Yelick, K. (1999) · PPSC · Cited by 60
Self-citationSIPR: A New Framework for Generating Efficient Code for Sparse Matrix Computations
Pugh, W., & Shpeisman, T. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48319-5_14 · Cited by 39
Ordering Unstructured Meshes for Sparse Matrix Computations on Leading Parallel Systems
Oliker, L., Li, X., Heber, G., & Biswas, R. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45591-4_66 · Cited by 14
Heras, D. B., Blanco, V., Cabaleiro, J. C., & Rivera, F. F. (1999) · Lecture notes in computer science · doi:10.1007/bfb0100581 · Cited by 11
Cited by
(2006) · Cited by 1,979
Implementing 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
SPIRAL: Code Generation for DSP Transforms
Puschel, M., Moura, J. M. F., Johnson, J. R., Padua, D., Veloso, M. M., Singer, B. W., Xiong, J., Franchetti, F., Gacic, A., Voronenko, Y., et al. (2005) · Proceedings of the IEEE · doi:10.1109/jproc.2004.840306 · Cited by 826
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
“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-citationOptimization 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-citation
Metadata
- Authors
- Im, E.-J., Yelick, K., & Vuduc, R.
- Venue
- The International Journal of High Performance Computing Applications
- Publisher
- SAGE Publications
- Published
- 2004-02
- Volume
- 18
- Issue
- 1
- Pages
- 135-158
- ISSN
- 0890-2720 (ISSN-L)
- 1094-3420
- 1741-2846
- OpenAlex
- W2130289795
- Cited by
- 339
- References
- 20
- FWCI
- 24.27
- Type
- journal article
- 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.