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 601–700 of 810
Accelerating the iterative linear solver for reservoir simulation on multicore architectures
Wu, W., Li, X., He, L., & Zhang, D. (2014) · IEEE International Conference on Parallel and Distributed Systems (ICPADS) · doi:10.1109/padsw.2014.7097817 · Cited by 3
“This has been extensively studied in existing literature [19], [20], [21].”
BackgroundPichel, J. C., Heras, D. B., Cabaleiro, J. C., Garcia-Loureiro, A. J., & Rivera, F. F. (2009) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342009106416 · Cited by 3
“Williams et al. (2007) apply an index reduction technique, in which 16-byte indices are used when possible.”
MethodLinear Algebraic Primitives for Parallel Computing on Large Graphs
Bárbara, S. (2010) · Cited by 3
PARALLELIZATION OF A MATHEMATICAL MODEL TO EVALUATE A CCA APPLICATION FOR VANETS
Hernández, R. M., García-Costa, C., Tomás-Gabarrón, J. B., Egea-López, E., & García-Haro, J. (2011) · International Conference on Simulation and Modeling Methodologies, Technologies and Applications · doi:10.5220/0003570000050013 · Cited by 3
“In general, we find quite a lot of done work in the field of sparse matrix-vector multiplications using parallelization techniques (Kotakemori et al., 2008; Goumas et al., 2009; Williams et al., 2009).”
BackgroundAn Efficient Solution to Structured Optimization Problems using Recursive Matrices
Rückert, D., & Stamminger, M. (2019) · Computer Graphics Forum · doi:10.1111/cgf.13758 · Cited by 3
Cascaded DMA Controller for Speedup of Indirect Memory Access in Irregular Applications
Kashimata, T., Kitamura, T., Kimura, K. R., & Kasahara, H. (2019) · Irregular Applications: Architectures and Algorithms · doi:10.1109/ia349570.2019.00017 · Cited by 3
“optimized SpMV on various multi–core platforms [17].”
Trotter, J. D., Langguth, J., & Cai, X. H. (2020) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2020.05.020 · Cited by 3
Optimization by runtime specialization for sparse matrix-vector multiplication
Kamin, S., Garzarán, M. J., Aktemur, B., Xu, D., Yılmaz, B., & Chen, Z. (2014) · ACM SIGPLAN Notices · doi:10.1145/2775053.2658773 · Cited by 5
HICAMP: architectural support for efficient concurrency-safe shared structured data access
Cheriton, D. R., Firoozshahian, A., Solomatnikov, A., Stevenson, J. P., & Azizi, O. (2012) · ACM SIGPLAN Notices · doi:10.1145/2248487.2151007 · Cited by 3
Towards an Efficient Sparse Storage Format for the SpMM Kernel in GPUs
Marini, R., Dufrechou, E., & Ezzatti, P. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-06156-1_9 · Cited by 3
Towards an Efficient SIMD Virtual Radio Access Network (vRAN) and Edge Cloud System
Wang, J., Wang, Z., & Hu, Y. (2023) · IEEE Transactions on Cloud Computing · doi:10.1109/tcc.2023.3275576 · Cited by 3
“The typical vRAN co-located workloads selected in the traditional network, image processing, and AI applications are longest prefix matching (LPM) [16], [17], halftoning direct binary search (DBS) [18], [19] and sparse matrix unifying (SMU) [20].”
BackgroundTechniques for finite element methods on modern processors
Ljungkvist, K. (2015) · KTH Publication Database DiVA (KTH Royal Institute of Technology) · Cited by 3
Accelerating Atmospheric Modeling Through Emerging Multi-core Technologies
Linford, J. C. (2010) · VTechWorks (Virginia Tech) · Cited by 6
Performance Engineering for Exascale-Enabled Sparse Linear Algebra Building Blocks
Kreutzer, M. (2018) · doi:10.25593/978-3-96147-104-1 · Cited by 3
Sparse tensor algebra compilation
Kjølstad, F. (2020) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 20
Scalable and Efficient Algorithms for Unstructured Mesh Computations
Thébault, L. (2016) · theses.fr (ABES) · doi:10.70675/6c897703z9a22z4ff2zbb5fz74b794c8a21d · Cited by 5
“highlight the memory bandwidth bottleneck that occurs on many different parallel architectures when dealing with the SpMV kernel [124].”
BackgroundUsing Multithreaded Techniques to Mask Memory Latency on FPGA Accelerators
Halstead, R. J. (2015) · eScholarship (California Digital Library) · Cited by 3
Sparse Matrix-Vector Multiplication Based on Network-on-Chip in FPGA
Sun, C., Götze, J., Jheng, H.-Y., & Ruan, S.-J. (2010) · IEEE International Conference on Computer and Information Technology (CIT) · doi:10.1109/cit.2010.397 · Cited by 2
“In the past few years, many researchers have presented hardware solutions utilizing the feature of pipelining and parallelism inherent to SMVM computation [5]–[8].”
BackgroundOn the Influence of Thread Allocation for Irregular Codes in NUMA Systems
Lorenzo, J. A., Rivera, F. F., Tuma, P., & Pichel, J. C. (2009) · International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT) · doi:10.1109/pdcat.2009.42 · Cited by 2
“In a recent work, a framework for automatic detection and application of the best mapping among threads and cores in parallel applications on multi-core systems was presented [5].”
MethodOptimizing the linear fascicle evaluation algorithm for many-core systems
Aggarwal, K., & Bondhugula, U. K. R. (2019) · International Conference on Supercomputing · doi:10.1145/3330345.3332469 · Cited by 2
“Numerous prior works have been proposed to improve the performance of SpMV, including that of the development of new sparse representations [10, 40, 62], representation-specific optimizations [9, 10, 25] and architecture-specific techniques [6, 10, 37, 43, 57, 67, 69, 70].”
BackgroundMany-Core Algorithm of the Embedded Zerotree Wavelet Encoder
Cedillo, J. A. Á., Álvarez-Sánchez, T., Aguilar-Fernández, M., & Sandoval-Gutiérrez, J. (2019) · IntechOpen eBooks · doi:10.5772/intechopen.89300 · Cited by 2
Dynamic Heterogeneous scheduling of GPU-CPU in Distributed Environment
Goyat, S., Kant, S., & Dhariwal, N. (2019) · International Conference on Smart Systems and Inventive Technology (ICSSIT) · doi:10.1109/icssit46314.2019.8987886 · Cited by 2
“Some other strategies implemented over partition of sparse matrices with supporting configuration environment and are implemented by some researcher such as the cache scalability of processors [15, 19], related with computing power capability of processors [4, 18] the mandatory bandwidth transmission of data [8, 11, 1…”
MethodA High-performance SpMV Accelerator on HBM-equipped FPGAs
Li, T., Shen, L., & Yao, S. (2022) · IEEE International Conference on High Performance Computing and Communications; IEEE International Conference on Smart City; IEEE International Conference on Data Science and Systems (HPCC/SmartCity/DSS) · doi:10.1109/hpcc-dss-smartcity-dependsys57074.2022.00171 · Cited by 2
“Prior researches on high-performance processors has focused on rearranging the non-zero elements and designing more efficient compression storage formats [6]–[8] to meet the requirements of vector units, along with designing parallel algorithms to distribute the workload evenly [9], [10].”
BackgroundPerformance of Portable Sparse Matrix-Vector Product Implemented Using OpenACC
Stec, K., & Stpiczyński, P. (2023) · Annals of Computer Science and Information Systems · doi:10.15439/2023f9640 · Cited by 2
“There are a lot of various sparse matrix storage formats and sophisticated techniques for developing efficient implementations of SpMV that utilize the underlying hardware of modern multicore CPUs and GPUs [3], [4], [5], [6], [7], [8], [9].”
MethodAhmad, M., Usman, S., Batyrshin, I., Hasnain, M. A., Khan, S., & Sidorov, G. (2024) · Information · doi:10.3390/info15110685 · Cited by 2
Performance Portability of SpMV for CSR and BSR Storage Formats Implemented Using OpenACC and SYCL
Stec, K., & Stpiczyński, P. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-85700-3_10 · Cited by 2
Systematic Mapping of Reed–Solomon Erasure Codes on Heterogeneous Multicore Architectures
Wyrzykowski, R., Woźniak, M., & Kuczyński, Ł. (2014) · Wiley eBooks · doi:10.1002/9781118711897.ch10 · Cited by 2
Sparse Matrix Multiplication on a Reconfigurable Many-Core Architecture
Pinhao, J., José, W., Neto, H. C., & Véstias, M. P. (2015) · Euromicro Conference on Digital System Design (DSD) · doi:10.1109/dsd.2015.89 · Cited by 2
“In [2] and [3] several multi-core CPUs are tested for SMVM.”
BackgroundBreaking the performance bottleneck of sparse matrix-vector multiplication on SIMD processors
Zhang, K., Chen, S., Wang, Y., & Wan, J. (2013) · IEICE Electronics Express · doi:10.1587/elex.10.20130147 · Cited by 2
High throughput compression of floating point numbers on graphical processing units
Ravishankar, A. P., Sudheer, C. D., Baruah, P. K., & Srinivasan, A. (2012) · International Conference on Parallel, Distributed and Grid Computing (PDGC) · doi:10.1109/pdgc.2012.6449838 · Cited by 2
“Also parallel sparse matrix linear algebra packages are not capable of utilizing the potential of a processor for the type of operations that were performed and the type of communication that they are involved in [7].”
BackgroundCommunication-optimal iterative methods
Demmel, J. W., Hoemmen, M. F., Mohiyuddin, M., & Yelick, K. (2009) · Journal of Physics Conference Series · doi:10.1088/1742-6596/180/1/012040 · Cited by 2
“We compared it against applying SpMV s times, where we used a highly optimized SpMV implementation [13].”
MethodSelf-citationSibai, F. N., & El‐Moursy, A. A. (2013) · International Journal of Parallel Emergent and Distributed Systems · doi:10.1080/17445760.2012.762774 · Cited by 2
“…are trivially parallelisable [10] and as a result authors in [5,32] have given much importance in analysing the parallelisation of sparse matrix-vector multiplication (SpMV) [36], given its role in solving linear systems and eigenvalue problems that arise in scientific and engineering applications.”
BackgroundA compiler-automated array compression scheme for optimizing memory intensive programs
Liu, L., & Li, Z. (2010) · International Conference on Supercomputing · doi:10.1145/1810085.1810124 · Cited by 2
“Three encoding methods are developed for such compression.”
MethodExpression Tree Evaluation by Dynamic Code Generation - Are Accelerators Up for the Task?
Muller, T., Weidendorfer, J., & Blaszczyk, A. (2013) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2013.32 · Cited by 2
“Code generation techniques are also used to automatically tune code for specific architectures, e.g. for linear algebra kernels (ATLAS, [8]), sparse matrices (OSKI, [1]), or FFTs (FFTW, [9]).”
BackgroundMethodWorkflows for performance evaluation and tuning
Tilson, J. L., Reed, M. S. C., & Fowler, R. J. (2008) · IEEE International Conference on Cluster Computing (CLUSTER) · doi:10.1109/clustr.2008.4663758 · Cited by 2
“Finally, thanks to the reviewers for helpful comments.”
BackgroundOptimization and Parallelization of Emedge3D on Shared Memory Architecture
Kuhn, M., Latu, G., Stéphane Genaud, A., & Crouseilles, N. (2013) · International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC) · doi:10.1109/synasc.2013.72 · Cited by 2
“∗ Icube, CNRS - Université de Strasbourg, France.”
Parallel Sparse Matrix Vector Multiplication using greedy extraction of boxes
Brahme, D., Mishra, B. R., & Barve, A. (2010) · IEEE International Conference on High Performance Computing, Data, and Analytics · doi:10.1109/hipc.2010.5713185 · Cited by 2
“This reduces the compute, memory throughput imbalance and improves the overall performance of SpMV multiplication.”
BackgroundKirk, D. B., & Hwu, W. (2013) · Elsevier eBooks · doi:10.1016/b978-0-12-415992-1.00002-x · Cited by 2
Efficient sparse matrix-delayed vector multiplication for discretized neural field model
Fousek, J. (2017) · The Journal of Supercomputing · doi:10.1007/s11227-017-2194-4 · Cited by 2
“Several optimization strategies for multicore CPU architectures are presented in [36] and extended with autotuning by [3], while [38] proposes parallelization techniques based on matrix partitioning.”
MethodHMCSP: Reducing Transaction Latency of CSR-based SPMV in Hybrid Memory Cube
Qian, C., Childers, B. R., Huang, L., Yu, Q., & Wang, Z. (2018) · IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS) · doi:10.1109/ispass.2018.00021 · Cited by 2
“Several techniques have been proposed to improve the performance of CSR-based [1] SPMV (CSR-SPMV) by using a GPU, the Intel MIC or an FPGA [2], which needs an external co-processor and the support of a runtime programming model.”
MethodVatai, E., Singhal, U., & Suda, R. (2019) · International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia) · doi:10.1145/3368474.3368494 · Cited by 2
“However, this situation is mitigated somewhat by the fact that the execution stage, which would need to run on multiple threads is very similar to the traditional SpMV algorithm, and there is ample amount of literature which deals with this issue such as [15] for example.”
BackgroundImproving parallelism and locality with asynchronous algorithms
Liu, L., & Li, Z. (2010) · ACM SIGPLAN Notices · doi:10.1145/1837853.1693483 · Cited by 2
On the Performance and Energy Efficiency of Sparse Matrix-Vector Multiplication on FPGAs
Mpakos, P., Παπαδοπούλου, Ν., Alverti, C., Goumas, G., & Koziris, N. (2020) · Advances in parallel computing · doi:10.3233/apc200092 · Cited by 2
Establishing a Miniapp as a programmability proxy
Stone, A., Dennis, J. M., & Strout, M. M. (2012) · ACM SIGPLAN Notices · doi:10.1145/2370036.2145881 · Cited by 2
Identifying and (automatically) remedying performance problems in CPU/GPU applications
Welton, B., & Miller, B. P. (2020) · International Conference on Supercomputing · doi:10.1145/3392717.3392759 · Cited by 2
“Autotuning techniques have been applied to identifying parameters such as the best program inputs [5, 38, 39], compiler settings [2, 34], and algorithm configurations [3, 11] to use to increase performance.”
MethodReview on Sparse Matrix Storage Formats With Space Complexity Analysis
Jamalmohammed, S. B., Lavanya, K., V, Thaseen, I. S., & Biju, V. (2020) · Advances in computational intelligence and robotics book series · doi:10.4018/978-1-7998-3335-2.ch009 · Cited by 2
Memory-Driven Data-Flow Optimization for Neural Processing Accelerators
Nie, Q. (2020) · Cited by 3
Auto-Selection of an Optimal Sparse Matrix Format in the Neuro-Simulator ANNarchy
Dinkelbach, H. Ü., Bouhlal, B.-E., Vitay, J., & Hamker, F. H. (2022) · Frontiers in Neuroinformatics · doi:10.3389/fninf.2022.877945 · Cited by 2
“The efficiency of a single optimization may depend on the matrix as well as on the specific platform as demonstrated in the work of Williams et al. (2009).”
BackgroundMethodInfluentialRFID Data Management and Analysis via Tensor Calculus
Virgilio, R. D., & Milicchio, F. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-35332-1_1 · Cited by 2
Hardware Support for Efficient Sparse Matrix Vector Multiplication
Ku, A. K.-A., Kuo, J. Y.-C., & Xue, J. (2008) · IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC) · doi:10.1109/euc.2008.154 · Cited by 2
“Williams et al [19] present a number of optimization strategies for a multi-core environment, such as thread blocking, loop optimization, and memory bandwidth reduction techniques, and evaluate their work using homogenous AMD and INTEL multi-cores and heterogeneous STI Cell processors.”
MethodParallel implementation of Davidson-type methods for large-scale eigenvalue problems
Alcalde, E. R. (2012) · RiuNet (Universitat Politècnica de València) · doi:10.4995/thesis/10251/15188 · Cited by 2
“Moreover the time-expensive operations in the iterative methods (e.g, the matrix-vector products with the problem matrices, the vector operations such as additions, scaling and inner products) can be implemented with excellent performance in high-performance architectures, like in distributed memory or in GPUs.”
BackgroundInfluentialSMAT: An Input Adaptive Sparse Matrix-Vector Multiplication Auto-TunerPreprint
Li, J., Xiuxia, Z., Tan, G., & Chen, M. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1210.2536 · Cited by 2
“Williams et al. [19] evaluated different optimization strategies on five platforms (AMD Opteron, Intel Clovertown, Sun Niagara2, and STI Cell SPE).”
BackgroundMethodUnderstanding the design trade-offs among current multicore systems for numerical computations
Kang, S., Bader, D. A., & Vuduc, R. W. (2009) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2009.5161055 · Cited by 2
“’s high bandwidth utilization [31], though an open question is what the ultimate impact of adopting different DRAM technologies will be (i.”
BackgroundResultSelf-citationPerformance Evaluation of Sparse Matrix Multiplication Kernels onPreprint
Saule, É., Kaya, K., & C, U. V. (2013) · arXiv (Cornell University) · Cited by 2
A Framework for Composing High-Performance OpenCL from Python Descriptions
Anderson, M. J. (2014) · eScholarship (California Digital Library) · Cited by 3
Simultaneous Modelling of Multiple Turbulent Flow StatesPreprint
Krasnopolsky, B. I. (2017) · arXiv (Cornell University) · Cited by 2
SpVM Acceleration with Latency Masking Threads on FPGAs
Halstead, R. J., Najjar, W. A., & Huseini, O. (2021) · eScholarship (California Digital Library) · Cited by 2
Tunnell, M. A., & Gleich, D. F. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2505.20696 · Cited by 3
Detecting Silent Data Corruption from Hardware Counters
Choi, M., Azzaoui, T., Chaisson, K., Arias, O., & Son, S. W. (2025) · IEEE International Conference on Cluster Computing (CLUSTER) · doi:10.1109/cluster59342.2025.11186479 · Cited by 1
“Optimizing the SpMV operation is an open research problem spanning (1) data structures for efficiently storing sparse matrices [22] (2) algorithmic improvements [57] (3) parallelization and matrix partitioning [6], [38], [53] (4) hardware acceleration [39], [59].”
A multilevel algorithm for scalable independent task assignment
Tabak, H. B., Tabak, E. K., & Aykanat, C. (2025) · Future Generation Computer Systems · doi:10.1016/j.future.2025.108183 · Cited by 1
Optimizing Sparse Matrix-Vector Multiplication on GPUs using the Mathematics of Arrays
Thomas, S. J., & Mullin, L. M. R. (2025) · IEEE High Performance Extreme Computing Conference · doi:10.1109/hpec67600.2025.11196568 · Cited by 1
“Achieving a high B eff is essential for SpMV performance, and this depends on both the storage format and how well memory accesses are coalesced [13], [18].”
A Diagonal Block Memory-Aware Polynomial Preconditioner for Linear and Eigenvalue Solvers
Yang, X., Ni, Y., Yuan, F., Li, S., Dong, D., Xu, C., Jia, H., & Liu, J. (2026) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/3774934.3786446 · Cited by 1
“Extensive research has been devoted to optimize this kernel [11, 41, 42, 45, 50, 60].”
CoD-SELL: A Non-Zero Location Dictionary Compression Sparse Matrix Format for SpMV on GPU
Murakami, S., Yoneda, K., Iwamura, T., Watanabe, M., & Inoguchi, Y. (2026) · IEEE Access · doi:10.1109/access.2026.3659140 · Cited by 1
“For our test suite, we collected square sparse matrix data from reference [15] in the SuiteSparse Matrix Collection [16].”
Sparsity-Aware Roofline Models for Sparse Matrix-Matrix Multiplication
Qian, M., Ramadan, Y., Anubha, S., & Azad, A. (2026) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw71298.2026.00141 · Cited by 1
“Prior work has used Roofline-style reasoning to analyze sparse linear algebra kernels such as SpMV [14] and SpGEMM [15], often concluding that irregular access patterns and limited locality reduce effective bandwidth well below hardware peaks [10].”
Parallel non-linear dimension reduction algorithm on GPU
Yeh, T. T., Chen, T., Chen, Y. C., & Wei, H. W. (2011) · International Journal of Granular Computing Rough Sets and Intelligent Systems · doi:10.1504/ijgcrsis.2011.043370 · Cited by 1
Experiences with the Sparse Matrix-Vector Multiplication on a Many-core Processor
Pichel, J. C., & Rivera, F. F. (2012) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2012.17 · Cited by 1
Exploring a Novel Gathering Method for Finite Element Codes on the Cell/B.E. Architecture
Jowkar, M., de la Cruz, R., & Cela, J. M. (2010) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc.2010.24 · Cited by 1
“has been used many times in the past, to show that very high bandwidths can be achieved by using DMA transfers [2], [3], [4], [5].”
BackgroundMulti-core optimization for conjugate gradient benchmark on heterogeneous processors
Deng, L., & Dou, Y. (2011) · Journal of Central South University · doi:10.1007/s11771-011-0722-6 · Cited by 1
A 2D algorithm with asymmetric workload for the UPC conjugate gradient method
González‐Domínguez, J., Marques, O. A., Martín, M. J., & Touriño, J. (2014) · The Journal of Supercomputing · doi:10.1007/s11227-014-1300-0 · Cited by 1
“However, previous works have pointed out that this is a key aspect in the performance of SpMV [25].”
BackgroundA Hybrid Dynamic Load Balancing Algorithm for Distributed Systems Using Genetic Algorithms
Mehta, M. A., & Jinwala, D. C. (2014) · International Journal of Distributed Systems and Technologies · doi:10.4018/ijdst.2014070101 · Cited by 1
Bridging the gap between complex software paradigms and power-efficient parallel architectures
Ibrahim, K. Z. (2010) · International Conference on Green Computing · doi:10.1109/greencomp.2010.5598285 · Cited by 1
“Code generation is either done manually [I], [2], [3], [ 4], through automated process [I], [2], [3], or through searching large optimization space [5], [ 6 ].”
BackgroundMethodHardware Computation of the PageRank Eigenvector
McGettrick, S., & Geraghty, D. (2010) · International Conference on ReConFigurable Computing and FPGAs (ReConFig) · doi:10.1109/reconfig.2010.83 · Cited by 1
Memory Hierarchy Aware Parallel Priority Based Data Structures
Agarwal, D. (2011) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdps.2011.372 · Cited by 1
“Research has also reported effective techniques to make use of multicore computers and memory hierarchy for memory intensive scientific applications such as sparse matrix vector multiplication [19], [20], Matrix Reduction [21], [22], and di-”
MethodAdaptive tuning in a dynamically changing resource environment
Lee, S., & Eigenmann, R. (2008) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2008.4536399 · Cited by 1
“Extensive studies have been conducted to improve irregular applications on single-processor or shared memory systems [14].”
BackgroundModel-guided performance analysis of the sparse matrix-matrix multiplication
Scharpff, T., Iglberger, K., Hager, G., & Rüde, U. (2013) · International Conference on High Performance Computing & Simulation (HPCS) · doi:10.1109/hpcsim.2013.6641452 · Cited by 1
“However , most publications deal with parallel sparse matrix-vector multiplication [13], [14], [15], since it is of pivotal importa nce in solving sparse linear systems and sparse eigenvalue prob lems.”
BackgroundCOSC: Combine Optimized Sparse Matrix-Vector Multiplication for CSR Format
Zhang, J., Zhuang, L., Wan, J., Xu, X., Jiang, C., & Ren, Y. (2011) · ChinaGrid Annual Conference · doi:10.1109/chinagrid.2011.39 · Cited by 1
“[ 3 ]. These optimization strategy uses computing hardware features and its instruction set to improve operational efficiency and has a good performance.”
BackgroundMethodParallel Optimization for Sparse Matrix–Vector on GPU
Yin, M. J., Xu, X. B., Chen, H., He, S. B., & Hu, J. Z. (2013) · Lecture notes in electrical engineering · doi:10.1007/978-1-4471-4850-0_71 · Cited by 1
“The intermediate results stored in shared memory, and finally through accumulated calculation the intermediate results to complete the output element y [13].”
BackgroundOptimized Sparse Matrix Formats on GT200 and Fermi GPUs
Hugues, M., & Petiton, S. G. (2011) · HAL · Cited by 1
Generation of Key Bit-Streams Using Sparse Matrix-Vector Multiplication for Video Encryption
Sivasankar, M. (2014) · Advances in intelligent systems and computing · doi:10.1007/978-81-322-1602-5_82 · Cited by 1
“Due to the crucial requirements of SpMV in (i) Iterative methods for solving large linear systems Ax = b and (ii) Eigenvalue problems Ax = λx it attracted many researchers and more efficient methods are being introduced [8, 13, 15].”
MethodNode Level Primitives for Exact Inference using GPGPU
Jeon, H., Xia, Y., & Prasanna, V. K. (2010) · Cited by 1
PCAF: Scalable, High Precision k-NN Search Using Principal Component Analysis Based Filtering
Feng, H., Eyers, D. M., Mills, S. J., Wu, Y., & Huang, Z. (2016) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2016.79 · Cited by 1
“The space of the principal components is called the projected space of PCA.”
BackgroundEfficient FCM computations using sparse matrix-vector multiplication
Puheim, M., Vaščák, J., & Machová, K. (2016) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/smc.2016.7844885 · Cited by 1
“Optimization and evaluation of SpMxV on multicore platforms was performed in [18].”
BackgroundMethodAccelerating Sparse Matrix Kernels on Graphics Processing Units
Matam, K. K. (2012) · Cited by 1
An Efficient Fill Estimation Algorithm for Sparse Matrices and Tensors in Blocked Formats
Ahrens, W., Schiefer, N., & Xu, H. (2017) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 1
Toward Dynamic Load Balancing across OpenMP Thread Teams for Irregular Workloads
Xiao, X., Hirasawa, S., Takizawa, H., & Kobayashi, H. (2017) · International Journal of Networking and Computing · doi:10.15803/ijnc.7.2_387 · Cited by 1
“Their domains vary from fluid dynamics [32] to linear algebra [31].”
BackgroundOn tuning the symmetric sparse matrix vector multiplication with CSR and TJDS
Aymerich, E., Duchâteau, A., Montagne, E., & Plochan, F. (2018) · Journal of International Crisis and Risk Communication Research · doi:10.5555/3213069.3213073 · Cited by 1
MTTF-Aware Reliability Task Scheduling for PIM-Based Heterogeneous Computing System
Pang, D., Xu, D., Wang, Y., & Liang, H. (2018) · IEEE International Test Conference in Asia (ITC-Asia) · doi:10.1109/itc-asia.2018.00015 · Cited by 1
“means[28], Sparse Matrix-Vector Multiply[29], Connected Component[28], Topological Sorting[32].”
MethodDynamic Threading to Improve Embedded Software Performance in IoT Devices Using MQTT Protocol
Phúc, B. H., Quang, P. V., Linh, N. Q., & Hưởng, P. V. (2018) · International Conference on Advanced Technologies for Communications · doi:10.1109/atc.2018.8587511 · Cited by 1
“Optimizing this application focuses on two main objectives: performance and power consumption based on task division methods, cache organization, constraint bottlenecks or fragmentation of data in parallel [19, 20].”
BackgroundReducing communication in sparse solvers
Bienz, A. (2018) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 1
Systolic Sparse Matrix Vector Multiply in the Age of TPUs and Accelerators
Montagne, E., & Surós, R. (2019) · doi:10.22360/springsim.2019.hpc.003 · Cited by 1
Adaptive sparse matrix representation for efficient matrix-vector multiplication
Zardoshti, P., Khunjush, F., & Sarbazi‐Azad, H. (2017) · Elsevier eBooks · doi:10.1016/b978-0-12-803738-6.00014-8 · Cited by 1
Measuring Cache Complexity Using Data Movement Distance (DMD)
Snyder, D., & Ding, C. (2021) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw52791.2021.00070 · Cited by 1
“The I/O complexity is the basis of I/O efficient algorithms [Meyer et al., 2003], including cache-oblivious algorithms [Frigo et al., 1999] and communication avoiding algorithms [Williams et al., 2009a].”
MethodLSSM-SpMM: A Long-Row Splitting and Short-Row Merging Approach for Parallel SpMM on PEZY-SC3s
Cao, L., Wang, Q., Yang, S., Xia, R., Guo, W., & Liu, J. (2025) · Lecture notes in computer science · doi:10.1007/978-981-96-1551-3_7 · Cited by 1
Stec, K., & Stpiczyński, P. (2025) · Future Generation Computer Systems · doi:10.1016/j.future.2025.107825 · Cited by 1
Modular Construction and Optimization of the UZP Sparse Format for SpMV on CPUs
Rodríguez-Iglesias, A., Tongli, S. T., Tucker, E., Pouchet, L.-N., Rodríguez, G., & Touriño, J. (2025) · Proceedings of the ACM on Programming Languages · doi:10.1145/3729335 · Cited by 1
“For example, Vuduc [45] presented an automated system for generating e � cient implementations of SpMV on CPUs, while Williams et al. [49] moved toward multi-core platforms with the implementation of parallel SpMV kernels.”
Ye, B., Gao, M., Zhan, X., He, X., Zhang, Z., Gong, Q., Wang, X., & Chen, Y. (2025) · Humanities and Social Sciences Communications · doi:10.1057/s41599-025-05180-5 · Cited by 1
“3(d), such as metrics computation in hypergraph analysis, and Sparse Matrix-Vector Multiplication (SpMV) (Williams et al. 2007; Yesil et al. 2023) in hypergraph learning.”
Deep multilevel graph partitioning
Gottesbüren, L., Heuer, T., Sanders, P., Schulz, C., & Seemaier, D. (2021) · Repository KITopen (Karlsruhe Institute of Technology) · doi:10.5445/ir/1000138388 · Cited by 1
Optimizing Sparse Matrix-Vector Multiplication on GPUs via Index Compression
Sun, X., Wei, K.-C., Lai, L., Tsai, S.-H., & Wu, C. (2018) · IEEE Advanced Information Technology, Electronic and Automation Control Conference (IAEAC) · doi:10.1109/iaeac.2018.8577693 · Cited by 1
“In order to access sparse matrices effectively, S.Xu et al. proposed to use RCM (Reverse Cuthill-Mckee) [7] algorithm to reduce the bandwidth of the matrix.”
MethodSpFlow: Memory-Driven Data Flow Optimization for Sparse Matrix-Matrix Multiplication
Nie, Q., & Malik, S. (2019) · IEEE International Symposium on Circuits and Systems proceedings · doi:10.1109/iscas.2019.8702111 · Cited by 1
“Some provide optimization strategies for multicore environment [3] and GPUs [4], [5].”
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.