Optimization of sparse matrix-vector multiplication on emerging multicore platforms
Open accessThe DOI matches its Crossref record; 21 of the 23 references it cites were found in a registry or an index.
Abstract
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
Items 401–500 of 810
Optimizing Cache Performance for Graph Analytics.Preprint
Zhang, Y., Kiriansky, V., Mendis, C., Zaharia, M., & Amarasinghe, S. P. (2016) · arXiv (Cornell University) · Cited by 12
A methodology for speeding up matrix vector multiplication for single/multi-core architectures
Kelefouras, V. I., Kritikakou, A. S., Papadima, E., & Goutis, C. E. (2015) · The Journal of Supercomputing · doi:10.1007/s11227-015-1409-9 · Cited by 11
“However, many works exist in optimizing the sparse MVM on cluster architectures and GPUs (sparse MVM achieves lower complexity), such as [55] [54] [24].”
BackgroundMMSparse: 2D partitioning of sparse matrix based on mathematical morphology
Tan, Z., Ji, W., Gao, J., Zhao, Y., Benatia, M. A., Wang, Y., & Shi, F. (2020) · Future Generation Computer Systems · doi:10.1016/j.future.2020.02.076 · Cited by 11
Tareen, A. R., Meyer, M., Plessl, C., & Kenter, T. (2024) · IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM) · doi:10.1109/fccm60383.2024.00014 · Cited by 11
“However, it is also very challenging to actually achieve high utilization of a computing platform’s off-chip bandwidth for SpMV [1]–[3].”
BackgroundAn Architecture-aware Technique for Optimizing Sparse Matrix-vector Multiplication on GPUs
Maggioni, M., & Berger-Wolf, T. Y. (2013) · Procedia Computer Science · doi:10.1016/j.procs.2013.05.196 · Cited by 11
“SpMV is a bandwidth-limited kernel and it is generally reported to sustain low fractions of peak processor performance on irregular matrices [6].”
BackgroundSparse matrix–vector multiplication on the Single-Chip Cloud Computer many-core processor
Pichel, J. C., & Rivera, F. F. (2013) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2013.07.017 · Cited by 11
Rossi, R., Mossaiby, F., & Idelsohn, S. R. (2013) · Computers & Fluids · doi:10.1016/j.compfluid.2013.04.017 · Cited by 11
Examining recent many-core architectures and programming models using SHOC
Lopez, M. G., Young, J., Meredith, J. S., Roth, P. C., Horton, M. D., & Vetter, J. S. (2015) · IEEE/ACM International Workshop on Performance Modeling, Benchmarking and Simulation of High Performance Computer Systems (PMBS) · doi:10.1145/2832087.2832090 · Cited by 11
Programmable Acceleration for Sparse Matrices in a Data-Movement Limited World
Rawal, A., Fang, Y., & Chien, A. A. (2019) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2019.00016 · Cited by 11
“Similarly, GPUs provide massive parallel streaming processors to accelerate SpMV computations but the performance is still limited by the DRAM bandwidth even with the advanced GDDR packaging technology [15], [28], [47].”
BackgroundInfluentialVectorizing Sparse Matrix Computations with Partially-Strided Codelets
Cheshmi, K., Cetinic, Z., & Dehnavi, M. M. (2022) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc41404.2022.00037 · Cited by 11
“Libraries such as MKL and Eigen as well as implementations in [30], [31], [32], [33], [34] optimize the performance of SpMV on shared memory architectures and improve SIMD vectorizability.”
MethodParallel Structurally-Symmetric Sparse Matrix-Vector Products on Multi-Core Processors
Ainsworth, G. O., Jr., Batista, V. H. F., & Ribeiro, F. L. B. (2013) · Civil-comp proceedings · doi:10.4203/ccp.101.22 · Cited by 11
“Williams et al. [34] evaluated the sparse matrix-vector kernel using the CSR format on several up-to-date chip multiprocessor systems, such as the heterogeneous STI Cell.”
MethodGeneralised vectorisation for sparse matrix: vector multiplication
Yzelman, A.-J. N. (2015) · Irregular Applications: Architectures and Algorithms · doi:10.1145/2833179.2833185 · Cited by 11
“Segmented scans appear in shared-memory parallel sparse computations [14] and on GPU-tailored structures [15, 9].”
BackgroundAdjacency-Based Data Reordering Algorithm for Acceleration of Finite Element Computations
Zhou, M., Sahni, O., Shephard, M. S., Carothers, C. D., & Jansen, K. E. (2010) · Scientific Programming · doi:10.1155/2010/273921 · Cited by 17
CPU and/or GPU: Revisiting the GPU Vs. CPU MythPreprint
Kothapalli, K., Banerjee, D. S., Narayanan, P. J., Sood, S., Bahl, A. K., Sharma, S., Lad, S., Singh, K. K., Matam, K. K., Indarapu, S. B., et al. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1303.2171 · Cited by 11
“For these two workloads we use the average measurement over all the instances in the d ataset considered [49].”
BackgroundMethodInfluentialUnderstanding and Improving Graph Algorithm Performance
Beamer, S. (2016) · UC Berkeley · Cited by 20
Parallel Breadth-First Search on Distributed Memory SystemsPreprint
Buluç, A., & Madduri, K. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1104.4518 · Cited by 11
“A sparse graph can analogously be viewed as a sparse matrix, and optimization strategies for linear algebra computations similar to BFS, such as sparse matrix-vector multiplication [36], may be translated to the realm of graph”
BackgroundAchieving efficient strong scaling with PETSc using hybrid MPI/OpenMP optimisationPreprint
Lange, M., Gorman, G., Mitchell, L., & Southern, J. A. (n.d.) · Cited by 11
Neuralink: Fast on-Device LLM Inference with Neuron Co-Activation Linking
Wang, T., Fan, R., Huang, M., Hao, Z., Li, K., Cao, T., Lu, Y., Zhang, Y., & Ren, J. (2025) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/3676642.3736114 · Cited by 16
Performance drawbacks for matrix multiplication using set associative cache in GPU devices
Djinevski, L., Arsenovski, S., Ristov, S., & Gušev, M. (2013) · International Convention on Information and Communication Technology, Electronics and Microelectronics · Cited by 10
A GPU Framework for Sparse Matrix Vector Multiplication
Bayyapu, N., Reddy, G. R. M., & Raghavendra, P. S. (2014) · International Symposium on Parallel and Distributed Computing · doi:10.1109/ispdc.2014.10 · Cited by 10
“To confirm this observation, tests were conducted with the SpMV computation on GPU using various formats with large set of matrices from benchmark matrices used by William et al. [22] from University of Florida sparse matrix collections [23].”
MethodExploiting spatial symmetries for solving Poisson's equation
Alsalti-Baldellou, À., Álvarez-Farré, X., Trias, F. X., & Oliva, A. (2023) · Journal of Computational Physics · doi:10.1016/j.jcp.2023.112133 · Cited by 15
Efficient sparse matrix-matrix multiplication on heterogeneous high performance systems
Siegel, J., Villa, O., Krishnamoorthy, S., Tumeo, A., & Li, X. (2010) · IEEE International Conference on Cluster Computing Workshops (CLUSTER Workshops) · doi:10.1109/clusterwksp.2010.5613109 · Cited by 10
“Starting from the specific characteristics and performance variability of the sparse matrix-matrix multiplication, we propose a codesign approach that copes with the architectural limits of a heterogeneous cluster and allows its efficient exploitation with this application.”
BackgroundOptimizing Process-to-Core Mappings for Application Level Multi-dimensional MPI Communications
Karlsson, C., Davies, T., & Chen, Z. (2012) · IEEE International Conference on Cluster Computing (CLUSTER) · doi:10.1109/cluster.2012.47 · Cited by 10
“, ScaLAPACK applications, High Performance Linpack Benchmark HPL, and many PDE solvers based on domain decomposition methods) organize their computational processes as multidimensional Cartesian grids [24], with the communications often being performed in each dimension.”
MethodStatistical Analysis of a Jointly Optimized Beamformer-Assisted Acoustic Echo Canceler
Maruo, M. H., Bermudez, J. C. M., & Resende, L. S. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2284138 · Cited by 10
“the same computational complexity, mainly when the number of constraints is small and the block matrix is not neither sparse [37] nor its entries are constrained in the ([30], p.”
BackgroundAccurate CUDA performance modeling for sparse matrix-vector multiplication
Guo, P., & Wang, L. (2012) · International Conference on High Performance Computing & Simulation (HPCS) · doi:10.1109/hpcsim.2012.6266964 · Cited by 13
“We evaluated our performance models on the 14 widely-used testing matrices [18].”
MethodLBM-IB: A Parallel Library to Solve 3D Fluid-Structure Interaction Problems on Manycore Systems
Nagar, P., Song, F., Zhu, L., & Lin, L. (2015) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2015.14 · Cited by 10
“William et al. used a technique called sparse cache blocking to optimize memory-bound sparse matrix vector multiplications (SpMV) [32].”
Memory bandwidth optimization of SpMV on GPGPUs
Yan, C. C., Yu, H., Xu, W., Zhang, Y., Chen, B., Tian, Z., Wang, Y., & Yin, J. (2014) · Frontiers of Computer Science · doi:10.1007/s11704-014-4127-1 · Cited by 10
“[13] tested SpMV kernels with many kinds of optimizing methods on five multi-core/many-core platforms.”
Reducing the amount of out‐of‐core data access for GPU‐accelerated randomized SVD
Lu, Y., Yamazaki, I., Ino, F., Matsushita, Y., Tomov, S. Z., & Dongarra, J. J. (2020) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.5754 · Cited by 10
Evaluation of Sparse LU Factorization and Triangular Solution on Multicore Platforms
Li, X. S. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-92859-1_26 · Cited by 11
“[14] performed extensive study and optimization of sparse matrix-vector multiply (SpMV) on several leading CMP systems.”
BackgroundOptimization by runtime specialization for sparse matrix-vector multiplication
Kamin, S., Garzarán, M. J., Aktemur, B., Xu, D., Yılmaz, B., & Chen, Z. (2014) · doi:10.1145/2658761.2658773 · Cited by 10
“Several of these matrices were used in previous studies [11, 24, 34].”
BackgroundResultExploiting dense substructures for fast sparse matrix vector multiplication
Shantharam, M., Chatterjee, A., & Raghavan, P. (2011) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342011414748 · Cited by 10
Mapping Dense LU Factorization on Multicore Supercomputer Nodes
Lifflander, J., Miller, P., Venkataraman, R., Arya, A., Kalé, L. V., & Jones, T. (2012) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2012.61 · Cited by 10
“Such an implementation could be parameterized by the expected degree of contention and autotuned to the characteristics of each architecture [22], [33], [34].”
BackgroundExploring the effect of block shapes on the performance of sparse kernels
Karakasis, V., Goumas, G., & Koziris, N. (2009) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2009.5161159 · Cited by 10
“Recent work [4], [5], [16] has identified the memory subsystem, and more specifically the memory bandwidth, as the main performance bottleneck of SpMV.”
BackgroundSparse matrix-vector multiply on the HICAMP architecture
Stevenson, J. P., Firoozshahian, A., Solomatnikov, A., Horowitz, M., & Cheriton, D. R. (2012) · International Conference on Supercomputing · doi:10.1145/2304576.2304603 · Cited by 9
“The cost of the direct approach can be amortized by solving several vectors Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro.t or commercial advantage and that copies…”
BackgroundAccelerating Radiation Therapy Dose Calculation with Nvidia GPUs
Liu, F., Jansson, N., Podobas, A., Fredriksson, A., & Markidis, S. (2021) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw52791.2021.00076 · Cited by 9
“Instead, we redirect the interested reader to several well-written surveys on the topic [19], [20], [21], [22].”
BackgroundLINQits: big data on little clients
Chung, E. S., Davis, J. D., & Lee, J. (2013) · ACM SIGARCH Computer Architecture News · doi:10.1145/2508148.2485945 · Cited by 9
Graph-OPU: A Highly Flexible FPGA-Based Overlay Processor for Graph Neural Networks
Tang, E., Li, S., Chen, R., Zhou, H., Ma, Y., Zhang, H., Yu, J. W., & Wang, K. (2024) · ACM Transactions on Reconfigurable Technology and Systems · doi:10.1145/3691636 · Cited by 10
Parallel finite element technique using Gaussian belief propagation
El-Kurdi, Y., Dehnavi, M. M., Gross, W. J., & Giannacopoulos, D. D. (2015) · Computer Physics Communications · doi:10.1016/j.cpc.2015.03.019 · Cited by 9
“For example, implementations of Conjugate Gradient (CG) solvers for FEM problems [2], require global sparse operations which perform at a low fraction of the peak CPU computational throughput [3].”
MethodSparse Matrix Matrix Multiplication on Hybrid CPU+GPU Platforms
Matam, K. K., Indarapu, S. B., & Kothapalli, K. (2012) · Cited by 9
CRSD: Application Specific Auto-tuning of SpMV for Diagonal Sparse Matrices
Sun, X., Zhang, Y., Wang, T., Long, G., Zhang, X., & Li, Y. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-23397-5_32 · Cited by 9
Architecture- and workload- aware heterogeneous algorithms for sparse matrix vector multiplication
Indarapu, S. B., Maramreddy, M., & Kothapalli, K. (2014) · Annual ACM India Conference (COMPUTE) · doi:10.1145/2675744.2675749 · Cited by 9
Analysis of Sparse Matrix-Vector Multiplication Using Iterative Method in CUDA
Hassani, R., Fazely, A., Choudhury, R.-U.-A., & Luksch, P. (2013) · IEEE International Conference on Networking, Architecture and Storage (NAS) · doi:10.1109/nas.2013.41 · Cited by 9
Altınkaynak, A. (2016) · International Journal for Numerical Methods in Engineering · doi:10.1002/nme.5346 · Cited by 9
“[37] could be used in this work.”
Performance Characteristics for Sparse Matrix-Vector Multiplication on GPUs
Alahmadi, S., Muhammed, T., Mehmood, R., & Albeshri, A. A. (2019) · EAI/Springer Innovations in Communication and Computing · doi:10.1007/978-3-030-13705-2_17 · Cited by 9
“SpMV is a memory-bounded computation and hence they did not achieve the peak performance of the used devices [10, 39, 46–48].”
MethodStochastic Gradient Descent on Highly-Parallel ArchitecturesPreprint
Ma, Y., Rusu, F., & Torres, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.08800 · Cited by 9
“Parallelizing linear algebra operations on sparse data is known to be a difficult task because of the irregular memory access [36].”
BackgroundEfficient visual search in images and videos
Yu, T. (2019) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/83290 · Cited by 9
Considerations when evaluating microprocessor platforms
Anderson, M. C., Catanzaro, B., Chong, J., Gonina, E., Keutzer, K., Lai, C.-Y., Murphy, M., Sheffield, D., Su, B.-Y., & Sundaram, N. (2011) · Cited by 8
A hardware–software co-design approach for implementing sparse matrix vector multiplication on FPGAs
Jain-Mendon, S., & Sass, R. R. (2014) · Microprocessors and Microsystems · doi:10.1016/j.micpro.2014.02.004 · Cited by 8
Intelligent runtime tuning of parallel applications with control points
Kalé, L. V., & Dooley, I. (2010) · Cited by 8
Cerberus: Triple Mode Acceleration of Sparse Matrix and Vector Multiplication
Hwang, S., Baek, D., Park, J., & Huh, J. (2024) · ACM Transactions on Architecture and Code Optimization · doi:10.1145/3653020 · Cited by 8
Machine Learning-Based Kernel Selector for SpMV Optimization in Graph Analysis
Xiao, G., Zhou, T., Chen, Y., Hu, Y., & Li, K. (2024) · ACM Transactions on Parallel Computing · doi:10.1145/3652579 · Cited by 8
“Williams et al. [38] provided valuable insights into the architectural tradeoffs of multicore design strategies for SpMV.”
BackgroundParallel Implementation of Conjugate Gradient Method on Graphics Processors
Woźniak, M., Olas, T., & Wyrzykowski, R. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14390-8_14 · Cited by 8
“architectures [11,19,20].”
Lee, C. (2013) · SIAM Journal on Scientific Computing · doi:10.1137/110838716 · Cited by 8
“tance in high performance computing [32].”
Sparse matrix-vector multiply on the Texas Instruments C6678 Digital Signal Processor
Gao, Y., & Bakos, J. D. (2013) · IEEE International Conference on Application-specific Systems, Architectures and Processors (ASAP) · doi:10.1109/asap.2013.6567571 · Cited by 8
“Optimizing sparse matrix-vector multiply on emerging architectures has been the subject of much recent work [9][10][11][12].”
BackgroundEfficient Parallel Algorithm for Nonlinear Dimensionality Reduction on GPU
Yeh, T. T., Chen, T., Chen, Y.-C., & Shih, W. (2010) · IEEE International Conference on Granular Computing (GrC) · doi:10.1109/grc.2010.145 · Cited by 8
“Sparse matrix-vector multiplication (SpMV) is an important operation for solving Eigen-problems, and there are several existing GPU-based SpMV implementations [ 6 ].”
MethodFpga Acceleration Of Sparse Matrix-Vector Multiplication Based On Network-On-Chip
Götze, J., Jheng, H.-Y., Ruan, S.-J., & Sun, C.-C. (2011) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.42281 · Cited by 8
Geveler, M., Dirk Ribbrock, A., Dominik Göddeke, A., Zajac, P., & Turek, S. (2011) · Civil-comp proceedings · doi:10.4203/ccp.95.22 · Cited by 8
“• The coarse grid solver generally requires very little time, and we use a preconditioned conjugate gradient solver for this task, which in turn is, once SpMV and the BLAS-1 operations DOT and NRM2 are available, trivial to implement on both CPUs and GPUs.”
ResultInfluentialAccelerating Graph Adjacency Matrix Multiplications with Adjacency Forest
Nishino, M., Yasuda, N., Minato, S.-I., & Nagata, M. (2014) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611973440.122 · Cited by 13
Sparse Binary Matrix-Vector Multiplication on Neuromorphic Computers
Schuman, C. D., Kay, B., Date, P., Kannan, R., Sao, P., & Potok, T. E. (2021) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw52791.2021.00054 · Cited by 8
“Researchers have studied optimizing S P MVon single-core C PU [4], multicore C PU s [5], G PU s [6], and Xeon-Phi [7].”
BackgroundMethods for Network Optimization and Parallel Derivative-free Optimization
Olsson, P.-M. (2014) · Linköping studies in science and technology. Dissertations · doi:10.3384/diss.diva-104110 · Cited by 10
“Examples of such methods are Rapidly Exploring Random Trees (RRTs) [59, 60, 80] and Probabilistic Road Maps (PRMs) [57, 60].”
MethodSome Optimization Techniques of the Matrix Multiplication Algorithm
Golubi�, K. (2013) · ITI ... · doi:10.2498/iti.2013.0572 · Cited by 8
“[13] used padding to the first element of each submatrix to land on equidistant cache sets.”
MethodPower models supporting energy-efficient co-design on ultra-low power embedded systems
Tran, V. N.-N., Barry, B., & Ha, P. H. (2016) · International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation · doi:10.1109/samos.2016.7818329 · Cited by 8
“SpMV has low operational intensity and high speed-up due to its parallel scalability [25].”
BackgroundData-parallel language for correct and efficient sparse matrix codes
Bodík, R., & Arnold, G. (2011) · Cited by 8
Fast Sparse Matrix Matrix Product Based on ELLR-T and GPU Computing
V'zquez, F., Ortega, G., Fern'ndez, J. J., García, I., & Garzón, E. M. (2012) · IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA) · doi:10.1109/ispa.2012.99 · Cited by 8
Optimal block size for matrix multiplication using blocking
Ristov, S., Gušev, M., & Velkoski, G. (2014) · International Convention on Information and Communication Technology, Electronics and Microelectronics · doi:10.1109/mipro.2014.6859580 · Cited by 8
“A possible solution to avoid the associativity problem is padding the first element of the matrix [10].”
BackgroundEfficient Dense and Sparse Matrix Multiplication on GP-SIMD
Morad, A., Yavits, L., & Ginosar, R. (2014) · International Workshop on Power and Timing Modeling, Optimization and Simulation (PATMOS) · doi:10.1109/patmos.2014.6951895 · Cited by 8
“03 GFLOPS/W [38].”
BackgroundNonnegative matrix factorization for clustering
Kuang, D. (2014) · SMARTech Repository (Georgia Institute of Technology) · Cited by 8
Accelerating the SpMV kernel on standard CPUs by exploiting the partially diagonal structuresPreprint
Fukaya, T., Ishida, K., Miura, A., Iwashita, T., & Nakashima, H. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2105.04937 · Cited by 8
“We can find studies for early hardware in Williams et al. [2009] and Liu et al. [2013].”
MethodHigh Performance Adaptive Finite Element Methods : With Applications in Aerodynamics
Jansson, N. (2013) · KTH Publication Database DiVA (KTH Royal Institute of Technology) · Cited by 8
FastLoad: Speeding Up Data Loading of Both Sparse Matrix and Vector for SpMV on GPUs
Hu, J., Luo, H., Jiang, H., Xiao, G., & Li, K. (2024) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2024.3477431 · Cited by 7
“Williams et al. investigated the application of SpMV on multicore platforms, considering both homogeneous (e.g., AMD dual-core, Intel quad-core) and heterogeneous platforms (e.g., STI Cell, Sun Niagara2) [13].”
BackgroundMemory Optimizations for Sparse Linear Algebra on GPU Hardware
Walden, A. C., Zubair, M., Stone, C. P., & Nielsen, E. J. (2021) · IEEE/ACM Workshop on Memory Centric High Performance Computing (MCHPC) · doi:10.1109/mchpc54807.2021.00010 · Cited by 7
“[5]–[11].”
An Improved Implementation of Preconditioned Conjugate Gradient Method on GPU
Gui, Y., & Zhang, G. (2012) · Journal of Software · doi:10.4304/jsw.7.12.2695-2702 · Cited by 7
“583-592, 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing, 2010 [12] S.”
MethodErlebacher, G., Saule, É., Flyer, N., & Bollig, E. F. (2014) · International Conference on Supercomputing · doi:10.1145/2597652.2597656 · Cited by 7
“Naturally, improving the performance of SpMV has captured the interest of many researchers; including the development of various implementations for CPUs [5, 28] and GPUs [2, 13, 26, 15].”
BackgroundInfluentialApplying vectorization of diagonal sparse matrix to accelerate wind field calculation
Gomez, G. S., Tena, C., Margalef, T., & Cortés, A. (2016) · The Journal of Supercomputing · doi:10.1007/s11227-016-1696-9 · Cited by 7
“WindNinja [3] is a wind field simulator that requires an elevation map and the meteorological wind speed and direction to determine the wind parameters at each cell of the terrain.”
BackgroundMethodTemplate based synthesis for high performance computing
Fujita, M., Kimura, Y., & Wang, Q. (2017) · IFIP/IEEE International Conference on Very Large Scale Integration · doi:10.1109/vlsi-soc.2017.8203492 · Cited by 7
“There are multiple expressions and assignments, and normal ways to process are to start with either w11× Is[1], w21× Is[1], w31× Is[1],andw41× Is[1] (column first), or w11 × Is[1]+w12 × Is[2]+w13 × Is[3]+ w14 × Is[4] (row first).”
BackgroundMethodChen, R., Zhang, H., Ma, Y., Chen, J., Yu, J. W., & Wang, K. (2023) · IEEE International Symposium on Circuits and Systems proceedings · doi:10.1109/iscas46773.2023.10181734 · Cited by 7
“With 3 CUs or threads for computing, previous methods shown in Fig.2(b) [18, 19] can hardly avoid the imbalance across rows, resulting in a waste of resources and power consumption.”
MethodGenerating Approximate Inverse Preconditioners for Sparse Matrices Using CUDA and GPGPU
Xu, S., Xue, W., Wang, K., & Lin, H. X. (2011) · Journal of Algorithms & Computational Technology · doi:10.1260/1748-3018.5.3.475 · Cited by 7
Towards Efficient Execution of Erasure Codes on Multicore Architectures
Wyrzykowski, R., Kuczyński, Ł., & Woźniak, M. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-28145-7_35 · Cited by 7
Dapper: An Adaptive Manager for Large-Capacity Persistent Memory
Xue, D., Huang, L., Li, C., & Wu, C. (2019) · IEEE Transactions on Computers · doi:10.1109/tc.2019.2899836 · Cited by 7
Unleashing the performance of bmSparse for the sparse matrix multiplication in GPUs
Berger, G., Freire, M., Marini, R., Dufrechou, E., & Ezzatti, P. (2021) · Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems (ScalA) · doi:10.1109/scala54577.2021.00008 · Cited by 7
ASA: A ccelerating S parse A ccumulation in Column-wise SpGEMM
Zhang, C., Bremer, M., Chan, C. P., Shalf, J. M., & Guo, X. (2022) · ACM Transactions on Architecture and Code Optimization · doi:10.1145/3543068 · Cited by 7
“For example, bioinformatics applications such as metagenome assembly [33] and protein clustering [28] work with sparse graphs of genetic and protein sequences that have 0.35% of non-zero connections [56].”
MethodInfluentialSelf-citationAdaptive Hybrid Storage Format for Sparse Matrix–Vector Multiplication on Multi-Core SIMD CPUs
Chen, S., Fang, J., Xu, C., & Wang, Z. (2022) · Applied Sciences · doi:10.3390/app12199812 · Cited by 7
Performance Limitations for Sparse Matrix-Vector Multiplications on Current Multi-Core Environments
Schubert, G., Hager, G., & Fehske, H. (2010) · Springer eBooks · doi:10.1007/978-3-642-13872-0_2 · Cited by 7
“In recent years, the performance of various SpMVM algorithms has been evaluated by several groups [4, 9, 17 ].”
MethodHPCG: Preliminary Evaluation and Optimization on Tianhe-2 CPU-only Nodes
Chen, C., Du, Y., Jiang, H., Zuo, K., & Yang, C. (2014) · International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD) · doi:10.1109/sbac-pad.2014.10 · Cited by 7
“Several survey papers, [24,25,26] have done comprehensive review.”
BackgroundSome Useful Strategies for Unstructured Edge-Based Solvers on Shared Memory Machines
Aubry, R., Houzeaux, G., & Vázquez, M. (2011) · AIAA Aerospace Sciences Meeting · doi:10.2514/6.2011-614 · Cited by 7
Semiautomatic Acceleration of Sparse Matrix-Vector Product Using OpenACC
Stpiczyński, P. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-32152-3_14 · Cited by 7
Image convolution optimization using sparse matrix vector multiplication technique
Bipin, B. J., & Nair, J. J. (2016) · International Conference on Advances in Computing, Communications and Informatics (ICACCI) · doi:10.1109/icacci.2016.7732252 · Cited by 7
Zubair, M., Nielsen, E. J., Luitjens, J., & Hammond, D. P. (2016) · Irregular Applications: Architectures and Algorithms · doi:10.5555/3018843.3018847 · Cited by 7
Scientific Computing on Heterogeneous Architectures
Brodtkorb, A. R. (2011) · Cited by 7
A geometric partitioning method for distributed tomographic reconstruction
Buurlage, J., Bisseling, R. H., & Batenburg, K. J. (2018) · Parallel Computing · doi:10.1016/j.parco.2018.12.007 · Cited by 7
Systolic Sparse Matrix Vector Multiply in the Age of TPUs and Accelerators
Montagne, E., & Surós, R. (2019) · Spring Simulation Multiconference · doi:10.23919/springsim.2019.8732860 · Cited by 7
“Many mappings based in CSR and partitioning have been studied and implemented in multiprocessors, multicores, GPUs, and FPGA accelerators (Im et al. 2004, Krotkiewski and Dabrowski 2010, Vuduc 2004, Williams et al. 2009).”
BackgroundAutomatically tuning collective communication for one-sided programming models
Yelick, K., & Nishtala, R. (2009) · Cited by 7
Self-citationA Task-Scheduling Approach for Efficient Sparse Symmetric Matrix-Vector Multiplication on a GPU
Mironowicz, P., Dziekonski, A., & Mrozowski, M. (2015) · SIAM Journal on Scientific Computing · doi:10.1137/14097135x · Cited by 7
“In this section, we follow [24] in describing how to choose key parameters in particular situations—including the decision of whether to use RCM reordering and what value of BS to choose.”
BackgroundMethodMury, A. R., Schulze, B. R., Licht, F. L., Bona, L. C. E., & Ferro, M. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-19848-4_3 · Cited by 6
Performance impact of reconfigurable L1 cache on GPU devices
Ristov, S., Gušev, M., Djinevski, L., & Arsenovski, S. (2013) · Annals of Computer Science and Information Systems · Cited by 6
Moghnieh, H., & Lowther, D. A. (2010) · Digest of the Fifth Biennial IEEE Conference on Electromagnetic Field Computation · doi:10.1109/cefc.2010.5481252 · Cited by 6
Dynamic tuning of algorithmic parameters of parallel scientific codes
Kang, P., Selvarasu, N. K., Ramakrishnan, N., Ribbens, C. J., Tafti, D. K., & Srinidhi Varadarajan, A. (2010) · Procedia Computer Science · doi:10.1016/j.procs.2010.04.017 · Cited by 6
“Therefore, tuning support to automatically optimize scientific codes over parameter search spaces is becoming more relevant [1, 2].”
BackgroundAbed, K. H., & Morris, G. R. (2009) · DoD High Performance Computing Modernization Program Users Group Conference (HPCMP-UGC) · doi:10.1109/hpcmp-ugc.2009.70 · Cited by 6
Sparse Matrix-Based HPC Tomography
Marchesini, S., Trivedi, A., Enfedaque, P., Perciano, T., & Parkinson, D. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-50371-0_18 · Cited by 6
“[21]) on numerous architectures for both CPUs and GPUs.”
BackgroundAdaptive Finite Element Modelling of Welding Processes
Banaś, K., Chłoń, K., Cybułka, P., Michalik, K., Płaszewski, P., & Siwek, A. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-10894-0_28 · Cited by 6
“Traditionally, such investigations include the problem of proper mapping of numerical linear algebra routines to computer architectures [17], [28].”
Background
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.