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 301–400 of 810
Performance Evaluation of Multithreaded Sparse Matrix-Vector Multiplication Using OpenMP
Liu, S., Zhang, Y., Sun, X., & Qiu, R. (2009) · 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.2009.75 · Cited by 19
“Based on OSKI, BeBOP team developed pOSKI (Parallel Optimized Sparse Kernel Interface) software package [19] for multi-core architecture.”
MethodA High Performance Block Eigensolver for Nuclear Configuration Interaction Calculations
Aktulga, H. M., Afibuzzaman, M., Williams, S., Buluç, A., Shao, M., Yang, C., Ng, E., Maris, P., & Vary, J. P. (2016) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2016.2630699 · Cited by 19
“In addition, CSB automatically enables cache blocking [13].”
MethodSelf-citationXu, S., Lin, H. X., & Xue, W. (2010) · International Symposium on Distributed Computing and Applications for Business Engineering and Science (DCABES) · doi:10.1109/dcabes.2010.162 · Cited by 18
Cache-aware sparse matrix formats for Kepler GPU
Nagasaka, Y., Nukada, A., & Matsuoka, S. (2014) · IEEE International Conference on Parallel and Distributed Systems (ICPADS) · doi:10.1109/padsw.2014.7097819 · Cited by 18
“Various research have attempted to address this issue by developing efficient implementation of SpMV, to reduce this overhead [5], [6], [7], [8].”
MethodCASK: Open-Source Custom Architectures for Sparse Kernels
Grigoras, P., Burovskiy, P., & Luk, W. W. (2016) · ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA) · doi:10.1145/2847263.2847338 · Cited by 18
“For example scaling the results of [15] for a modern dual CPU Xeon server would indicate performance on the order of 4.”
BackgroundVariable-Sized Blocks for Locality-Aware SpMV
Namashivavam, N., Mehta, S., & Yew, P.-C. (2021) · Proceedings of the CGO/Proceedings of the ... CGO · doi:10.1109/cgo51591.2021.9370327 · Cited by 18
“…blocking scheme (CVB-VAR) as described in Section V against the following SpMV implementations: 1) standard CSR-based SpMV (marked as CSR) [22]; 2) CSR-based state-of-the-art SpMV implementation available in Intel MKL (marked as MKL) [20]; 3) a non-blocking variant of the CVB-based SpMV…”
MethodAchieving Efficient Strong Scaling with PETSc Using Hybrid MPI/OpenMP Optimisation
Lange, M., Gorman, G., Weiland, M., Mitchell, L., & Southern, J. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38750-0_8 · Cited by 18
“Multiple storage formats, optimisation strategies and even auto-tuning frameworks exist to improve spMVM performance on a wide range of multi-core architectures [15].”
BackgroundAcceleration of conjugate gradient method for circuit simulation using CUDA
Maringanti, A., Athavale, V., & Patkar, S. (2009) · IEEE International Conference on High Performance Computing, Data, and Analytics · doi:10.1109/hipc.2009.5433184 · Cited by 18
A High-Performance Sparse Tensor Algebra Compiler in Multi-Level IRPreprint
Tian, R., Guo, L., Li, J., Ren, B., & Kestor, G. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.05187 · Cited by 21
“SpMV and SpMM widely appear in applications from scientific computing, such as direct or iterative solvers [39, 71], to data intensive domains [76], graph analytics [41].”
BackgroundAutotuning Runtime Specialization for Sparse Matrix-Vector Multiplication
Yılmaz, B., Aktemur, B., Garzarán, M. J., Kamin, S., & Kıraç, F. (2016) · ACM Transactions on Architecture and Code Optimization · doi:10.1145/2851500 · Cited by 20
“This 1D partition is a common approach [Williams et al. 2009; Belgin et al. 2011; Byun et al. 2012; Liu et al. 2013].”
BackgroundMethodZhang, N. (2011) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2011.174 · Cited by 17
“However, from the literatures [19], [20], we understand that the implementation was far from optimal.”
BackgroundMethodA linear algebra approach to OLAP
Macedo, H. D., & Oliveira, J. N. (2014) · Formal Aspects of Computing · doi:10.1007/s00165-014-0316-9 · Cited by 17
How naive is naive SpMV on the GPU?
Steinberger, M., Derlery, A., Zayer, R., & Seidel, H. (2016) · IEEE High Performance Extreme Computing Conference · doi:10.1109/hpec.2016.7761634 · Cited by 17
“Unsurprisingly, SpMV on the GPU quickly became the focus in a variety of research domains, which is reflected in the large body of work aimed at increasing its performance on multicore architectures like the GPU [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15].”
BackgroundEffective Implementation of Matrix–Vector Multiplication on Intel's AVX multicore Processor
Hassan, S. A., Mahmoud, M. M. M., Hemeida, A. M., & Saber, M. A. (2017) · Computer Languages · doi:10.1016/j.cl.2017.06.003 · Cited by 19
“Optimizing the performance of matrix-vector multiplication kernel requires an extensive understanding of the memory hierarchy and how it can be handled to maximize data-reuse, the size of the cache levels, the number of floating-point units and other essential parameters that must be taken into account [36-39].”
BackgroundCompiled multithreaded data paths on FPGAs for dynamic workloads
Halstead, R. J., & Najjar, W. A. (2013) · International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES) · doi:10.1109/cases.2013.6662507 · Cited by 17
Parallel Sparse Matrix-Vector Multiplication as a Test Case for Hybrid MPI+OpenMP Programming
Schubert, G., Hager, G., Fehske, H., & Wellein, G. (2011) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdps.2011.332 · Cited by 17
“In recent years the performance of various spMVM algorithms has been evaluated by several groups [1], [ 2 ], [3].”
MethodPERI - auto-tuning memory-intensive kernels for multicore
Williams, S., Datta, K., Carter, J. T., Oliker, L., Shalf, J. M., Yelick, K., & Bailey, D. (2008) · Journal of Physics Conference Series · doi:10.1088/1742-6596/125/1/012038 · Cited by 18
Self-citationA model-driven blocking strategy for load balanced sparse matrix–vector multiplication on GPUs
Ashari, A., Sedaghati, N., Eisenlohr, J., & Sadayappan, P. (2014) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2014.11.001 · Cited by 17
“In order to evaluate the effectiveness of the BRC format, we selected a diverse set of sparse matrices that have been used in previous studies [23][7].”
BackgroundMethodA design methodology for domain-optimized power-efficient supercomputing
Mohiyuddin, M., Murphy, M., Oliker, L., Shalf, J. M., Wawrzynek, J., & Williams, S. (2009) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/1654059.1654072 · Cited by 21
“The results reaffirm the significant impact of auto-tuning shown previously shown on numerous multicore architectures [5, 6, 29].”
BackgroundMethodResultInfluentialSelf-citationAn Experimental Study of Global and Local Search Algorithms in Empirical Performance Tuning
Balaprakash, P., Wild, S. M., & Hovland, P. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38718-0_26 · Cited by 17
“Using this approach, several researchers have achieved considerable success in tuning scientific kernels for both serial and multicore processors [1, 5, 7, 8, 15, 17].”
BackgroundA Cross-Platform SpMV Framework on Many-Core Architectures
Zhang, Y., Li, S., Yan, S., & Zhou, H. (2016) · ACM Transactions on Architecture and Code Optimization · doi:10.1145/2994148 · Cited by 17
“These matrices have been widely previous [Monakov et al. and 2009].”
PAGANI Toolkit: Parallel graph‐theoretical analysis package for brain network big data
Du, H., Xia, M., Zhao, K., Liao, X., Yang, H., Wang, Y., & He, Y. (2018) · Human Brain Mapping · doi:10.1002/hbm.23996 · Cited by 18
“The basic operation of the power method is sparse matrix vector multiplication, which has been accelerated on GPU devices in several studies (Bell & Garland, 2008; Williams et al., 2009).”
MethodScale-Free Sparse Matrix-Vector Multiplication on Many-Core Architectures
Liang, Y. E., Tang, W. T., Zhao, R., Lu, M., Huynh, H. P., & Goh, R. S. M. (2017) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2017.2681072 · Cited by 17
“SpMV computation is a performance bottleneck for many of these algorithms [3]–[5].”
BackgroundA Tensor Marshaling Unit for Sparse Tensor Algebra on General-Purpose Processors
Siracusa, M., Soria-Pardos, V., Sgherzi, F., Randall, J., Joseph, D. J., Moretó, M., & Armejach, A. (2023) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1145/3613424.3614284 · Cited by 16
Auto-tuning of Sparse Matrix-Vector Multiplication on Graphics Processors
Abu-Sufah, W., & Karim, A. A. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38750-0_12 · Cited by 16
“Williams and co-workers developed a SpMV auto-tuning framework for multi-core architectures [9].”
BackgroundMethodPrincipal Component Analysis Based Filtering for Scalable, High Precision k-NN Search
Feng, H., Eyers, D. M., Mills, S. J., Wu, Y., & Huang, Z. (2017) · IEEE Transactions on Computers · doi:10.1109/tc.2017.2748131 · Cited by 16
“structured multiplication has been well-studied [28], [32], [33].”
BackgroundPageRank Acceleration for Large Graphs with Scalable Hardware and Two-Step SpMV
Sadi, F., Sweeney, J., McMillan, S., Low, T. M., Hoe, J. C., Pileggi, L., & Franchetti, F. (2018) · IEEE High Performance Extreme Computing Conference · doi:10.1109/hpec.2018.8547561 · Cited by 16
Stochastic Gradient Descent on Modern Hardware: Multi-core CPU or GPU? Synchronous or Asynchronous?
Ma, Y., Rusu, F., & Torres, M. (2019) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2019.00113 · Cited by 23
“Parallelizing linear algebra operations on sparse data is known to be a difficult task because of the irregular memory access [37].”
BackgroundxMath2.0: a high-performance extended math library for SW26010-Pro many-core processor
Liu, F., Ma, W., Zhao, Y., Chen, D., Hu, Y. C., Lu, Q., Yin, W., Yuan, X., Jiang, L., Yan, H., et al. (2022) · CCF Transactions on High Performance Computing · doi:10.1007/s42514-022-00126-8 · Cited by 17
“Optimization on multi-core platforms has been extensively studied, including thread blocking, TLB blocking, loop optimization, etc (Williams et al. 2009), and auto-tuning has been proved to be effective.”
BackgroundThe Resource Problem of Using Linear Layer Leakage Attack in Federated Learning
Zhao, J. C., Elkordy, A. R., Sharma, A., Ezzeldin, Y. H., Avestimehr, S., & Bagchi, S. (2023) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr52729.2023.00387 · Cited by 23
“Much work is going into sparse matrix/tensor optimization [2, 5, 27, 33].”
BackgroundXu, F., Xu, Z., & Yakobson, B. I. (2014) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2014.04.013 · Cited by 16
Exploiting Sparsity to Accelerate Fully Connected Layers of CNN-Based Applications on Mobile SoCs
Xie, X., Du, D., Li, Q., Liang, Y. E., Tang, W. T., Ong, Z., Lu, M., Huynh, H. P., & Goh, R. S. M. (2017) · ACM Transactions on Embedded Computing Systems · doi:10.1145/3122788 · Cited by 20
“For multicore architectures, Williams and coworkers proposed and studied thread blocking optimizations (Williams et al. 2007) on a number of platforms, ranging from homogeneous AMD and Intel multicore processors to the heterogeneous STI Cell processor.”
BackgroundMethodProgramming Strategies for Irregular Algorithms on the Emu Chick
Hein, E. R., Eswar, S., Yaşar, A., Li, J., Young, J., Conte, T. M., Çatalyürek, Ü. V., Vuduc, R. W., Riedy, J., & Uçar, B. (2020) · ACM Transactions on Parallel Computing · doi:10.1145/3418077 · Cited by 16
“SpMV: There has been a large body of work on SpMV including on emerging architectures [12, 67] but somewhat limited recent work that is directly related to PGAS systems.”
BackgroundSelf-citationAsgari, B., Hadidi, R., Dierberger, J., Steinichen, C., Marfatia, A., & Kim, H. (2021) · IEEE International Symposium on Workload Characterization · doi:10.1109/iiswc53511.2021.00012 · Cited by 16
Adaptive sparse matrix representation for efficient matrix–vector multiplication
Zardoshti, P., Khunjush, F., & Sarbazi‐Azad, H. (2015) · The Journal of Supercomputing · doi:10.1007/s11227-015-1571-0 · Cited by 16
Optimising purely functional GPU programs
McDonell, T. L., Chakravarty, M. M. T., Keller, G., & Lippmeier, B. (2013) · ACM SIGPLAN Notices · doi:10.1145/2544174.2500595 · Cited by 16
Solving the Caputo Fractional Reaction-Diffusion Equation on GPU
Liu, J., Gong, C., Bao, W., Tang, G., & Jiang, Y. (2014) · Discrete Dynamics in Nature and Society · doi:10.1155/2014/820162 · Cited by 16
“The most common data structure used to store a sparse matrix for sparse matrix vector multiplication computations is compressed sparse row (CSR) format [34] shown in So in the following parts of this paper, matrix 𝐴 stands for the format of (11) not the format of (10).”
BackgroundSun, S. M. (2011) · Iowa State University Digital Repository (Iowa State University) · doi:10.31274/etd-180810-795 · Cited by 16
“89 Table 4.5 Comparison of SMVM Hardware Architectures . . . . . . . . . . . . . . . .”
BackgroundMethodInfluentialPerformance Gains and Drawbacks using Set Associative Cache
Gušev, M., & Ristov, S. (2012) · Journal of Next Generation Information Technology · doi:10.4156/jnit.vol3.issue3.9 · Cited by 15
Memory-aware Optimization for Sequences of Sparse Matrix-Vector Multiplications
Zhang, Y., Li, S., Yuan, F., Dong, D., Yang, X., Li, T., & Wang, Z. (2023) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps54959.2023.00046 · Cited by 15
“If thread 4 completes the computation of xL1 [4] (the bottom element of vector xL1 ) first, it will proceed to compute xL2 (the bottom element of vector xL2 ).”
BackgroundInfluentialDynamic Model-Driven Parallel I/O Performance Tuning
Behzad, B., Byna, S., Wild, S. M., Prabhat, & Snir, M. (2015) · IEEE International Conference on Cluster Computing (CLUSTER) · doi:10.1109/cluster.2015.37 · Cited by 15
GPU-Based Steady-State Solution of the Chemical Master Equation
Maggioni, M., Berger-Wolf, T. Y., & Liang, J. (2013) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2013.271 · Cited by 15
“Besides being limited by an out-of-date GPU architecture, their work is based on the general CSR format [12] and does not propose any optimization strategy.”
Sparse matrix-vector multiply on the Keystone II Digital Signal Processor
Gao, Y., Zhang, F., & Bakos, J. D. (2014) · IEEE High Performance Extreme Computing Conference · doi:10.1109/hpec.2014.7040985 · Cited by 15
Zubair, M., Nielsen, E. J., Luitjens, J., & Hammond, D. P. (2016) · Irregular Applications: Architectures and Algorithms · doi:10.1109/ia3.2016.009 · Cited by 15
HDagg: Hybrid Aggregation of Loop-carried Dependence Iterations in Sparse Matrix Computations
Zarebavani, B., Cheshmi, K., Liu, B., Strout, M. M., & Dehnavi, M. M. (2022) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps53621.2022.00121 · Cited by 17
“Kernels with parallel loops such as the sparse matrix-vector multiplication have also been optimized in implementations such as [29]–[32].”
MethodGPU-accelerated sparse matrix-vector product for a hybridizable discontinuous Galerkin method
Roca, X., Nguyen, N. C., & Peraire, J. (2011) · AIAA Aerospace Sciences Meeting · doi:10.2514/6.2011-687 · Cited by 15
Performance Analysis of Multicore and Multinodal Implementation of SpMV Operation
Bylina, B., Bylina, J., Stpiczyński, P., & Szałkowski, D. (2014) · Annals of Computer Science and Information Systems · doi:10.15439/2014f313 · Cited by 15
“Hence SpMV operation can be treated as n distinct tasks, which have ith row of A and x as a input data and produce ith element of y. Note that x is shared between all computing tasks.”
BackgroundA Performance Prediction and Analysis Integrated Framework for SpMV on GPUs
Guo, P., & Lee, C.-W. (2016) · Procedia Computer Science · doi:10.1016/j.procs.2016.05.308 · Cited by 15
Performance Analysis and Optimization of Sparse Matrix-Vector Multiplication on Intel Xeon Phi
Elafrou, A., Goumas, G., & Koziris, N. (2017) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2017.134 · Cited by 15
An Empirical Study of HPC Workloads on Huawei Kunpeng 916 Processor
Wang, Y., Chen, J.-K., Li, B.-R., Zuo, S.-C., Tang, W. M., Wang, B., Liao, Q., Xie, R., & Lin, J. (2019) · IEEE International Conference on Parallel and Distributed Systems (ICPADS) · doi:10.1109/icpads47876.2019.00057 · Cited by 15
“As matrix storage format [13] is sensitive to SpMV performance, we chose BCSR (Block Compressed Sparse Row) [14] for this evaluation.”
MethodA Study of SpMV Implementation Using MPI and OpenMP on Intel Many-Core Architecture
Ye, F., Calvin, C., & Petiton, S. G. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-17353-5_4 · Cited by 15
A framework for auto-tuning HDF5 applications
Behzad, B., Huchette, J., Luu, H. V. T., Aydt, R. A., Byna, S., Yao, Y., Koziol, Q., & Prabhat (2013) · ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC) · doi:10.1145/2462902.2462931 · Cited by 15
“Auto-tuning has been used extensively in computer science for improving performance of computational kernels [4, 3, 5].”
MethodOptimization and parallelization of the boundary element method for the wave equation in time domain
Bramas, B. (2016) · theses.fr (ABES) · doi:10.70675/fb28a34az4839z427az87ffz71012b66e4f3 · Cited by 15
“Finally, in general the SpMV hardly achieves 20% of the peak performance on CPU [34] and 5% on GPU [42].”
BackgroundReconfigurable Virtual Memory for FPGA-Driven I/O
Landgraf, J., Giordano, M., Yoon, E., & Rossbach, C. J. (2023) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/3582016.3582048 · Cited by 16
“These include the Matrix Market versions of webbase-1M [116], mawi_201512020030 [8], and GAP-kron [16].”
Dedicated Hardware Accelerators for Processing of Sparse Matrices and Vectors: A Survey
Isaac--Chassande, V., Evans, A., Durand, Y., & Rousseau, F. (2024) · ACM Transactions on Architecture and Code Optimization · doi:10.1145/3640542 · Cited by 14
“This opened the path for specialized software libraries for sparse algebra [84].”
BackgroundAlgorithm and hardware co-optimized solution for large SpMV problems
Sadi, F., Fileggi, L., & Franchetti, F. (2017) · IEEE High Performance Extreme Computing Conference · doi:10.1109/hpec.2017.8091096 · Cited by 14
“The stripes of A are stored in a row major format and we select compressed sparse row (CSR) [7] for our implementation.”
MethodDeployment Architectures for Cyber-Physical Control Systems
Tseng, S.-H., & Anderson, J. (2020) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc45564.2020.9147953 · Cited by 14
Xiang, F., & Zhang, Y. (2021) · Proceedings of the International Conference on Parallel Processing · doi:10.1145/3472456.3472479 · Cited by 14
“It is one of the level 2 sparse basic linear algebra subprograms (sp-BLAS) [12]; many algorithms (PageRank [14], conjugate gradient method [17], etc) use SpMV repeatedly, which makes it a performance bottleneck among these algorithms [10, 19, 20].”
A segment‐based sparse matrix–vector multiplication on CUDA
Feng, X., Jin, H., Zheng, R., Shao, Z., & Zhu, L. (2012) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.2978 · Cited by 14
“Sparse Matrix–Vector multiplication is generally reported to sustain low fractions of peak processor performance [2], primarily because of the fact that it is a memory-bound application.”
BackgroundCoAdELL: Adaptivity and Compression for Improving Sparse Matrix-Vector Multiplication on GPUs
Maggioni, M., & Berger-Wolf, T. Y. (2014) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2014.106 · Cited by 14
“We designed a lightweight index compression scheme based on delta encoding and warp granularity that can be transparently embedded into AdELL, leading to an immediate performance benefit associated with the bandwidth-limited nature of the SpMV.”
MethodOptimizing Sparse Data Structures for Matrix-vector Multiply
Guo, D., & Gropp, W. (2010) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342010374847 · Cited by 14
“Williams et al. (2009) tested SpMV on some multi-core platforms and discussed several tuning techniques, such as different kinds of blocking, loop optimization, simdization, and software prefetching.”
MethodOn the Usage of 16 Bit Indices in Recursively Stored Sparse Matrices
Martone, M., Filippone, S., Paprzycki, M., & Tucci, S. (2010) · International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC) · doi:10.1109/synasc.2010.77 · Cited by 14
“The results presented in [1] and those from other experiments ([4]) clearly indicate that performance of the SpMV and the SpSV suffers because of excessive memory traffic, especially when many cores are active at once (see, also [4], [5]).”
ResultAbu-Sufah, W., & Karim, A. A. (2012) · 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.2012.68 · Cited by 14
“In TJAD, the columns of the matrix are first compressed upward then the columns are reordered such that the number of nonzero elements decreases in columns visited in the new ordering.”
BackgroundBailey, D. H., Chame, J., Chen, C., Dongarra, J. J., Hall, M. W., Hollingsworth, J. K., Hovland, P., Moore, S., Seymour, K., Shin, J., et al. (2008) · Journal of Physics Conference Series · doi:10.1088/1742-6596/125/1/012089 · Cited by 14
“In two subsequent studies [7,8], these researchers analyzed similar but more sophisticated automatic optimizations for SpMV, the explicit heat equation PDE on a regular grid (Stencil), and a lattice Boltzmann application (LBMHD).”
BackgroundSelf-citationEfficient Multicore Algorithms For Identifying Biconnected Components
Chaitanya, M., & Kothapalli, K. (2016) · International Journal of Networking and Computing · doi:10.15803/ijnc.6.1_87 · Cited by 14
Sparse Matrix-Vector Multiplication on Multicore and Accelerators
Williams, S., Bell, N., Choi, J. W., Garland, M., Oliker, L., & Vuduc, R. (2010) · CRC Press eBooks · doi:10.1201/b10376-15 · Cited by 14
Self-citationDot-Product Join: Scalable In-Database Linear Algebra for Big Model Analytics
Qin, C., & Rusu, F. (2017) · International Conference on Scientific and Statistical Database Management · doi:10.1145/3085504.3085512 · Cited by 16
“[34] and [28] propose optimizations for SpMV in multicore architectures, while [3] optimizes distributed SpMV for large scale-free graphs with 2D partitioning to reduce communication between machines.”
Abubaker, N., Akbudak, K., & Aykanat, C. (2018) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2018.2864729 · Cited by 14
“[30] propose 17 different optimizations in three categories (i.”
BackgroundAn FPGA architecture for the Pagerank eigenvector problem
McGettrick, S., Geraghty, D., & McElroy, C. (2008) · International Conference on Field Programmable Logic and Applications (FPL) · doi:10.1109/fpl.2008.4629999 · Cited by 14
“This is in line with results obtained for the WebBase matrix (test matrix 10) by Williams et al. [ 7 ].”
ResultCharacterizing Scalability of Sparse Matrix–Vector Multiplications on Phytium FT-2000+
Chen, D., Fang, J., Xu, C., Chen, S., & Wang, Z. (2019) · International Journal of Parallel Programming · doi:10.1007/s10766-019-00646-x · Cited by 14
“Substantial previous work has been conducted to study the SpMV performance on parallel systems [7, 30, 35, 50].”
BackgroundMalossi, A. C. I., Ineichen, Y., Bekas, C., Curioni, A., & Quintana–Ort́ı, E. S. (2014) · International Conference on Parallel Processing Workshops (ICPPW) · doi:10.1109/icppw.2014.30 · Cited by 13
“, the seminal works [4], [23], [24].”
Ramalingam, S., Hall, M. W., & Chen, C. (2012) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2012.63 · Cited by 15
“Prior work on tuning sparse linear algebra has focused on a few key aspects of their implementation, including capitalizing on matrix structure, optimizing dense blocks and autotuning [9], [10].”
BackgroundModel-driven adaptation of double-precision matrix multiplication to the Cell processor architecture
Wyrzykowski, R., Rojek, K., & Szustak, Ł. (2011) · Parallel Computing · doi:10.1016/j.parco.2011.08.006 · Cited by 13
“Performance is a question of how well characteristics of a kernel map to characteristics of an architecture [31,32].”
HOPE: Hierarchical Object Prototype Encoding for Efficient Object Instance Search in Videos
Yu, T., Wu, Y., & Yuan, J. (2017) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2017.340 · Cited by 14
“(9) are the sparse matrixvector multiplication (SpMV) problem [30] which take O(nt1z2) and O(nmz1), respectively.”
BackgroundA review of CUDA optimization techniques and tools for structured grid computing
Al-Mouhamed, M. A., Khan, A. H., & Mohammad, N. (2019) · Computing · doi:10.1007/s00607-019-00744-1 · Cited by 13
“Optimization of sparse matrix–vector multiplication on emerging multicore platforms [46] CO Analysis of SpMV optimization strategies across a broad spectrum of multicore environment and provide key insights into the architectural tradeoffs of leading design strategies, in the context of demanding memory-bound numerica…”
BackgroundEfficient Matrix-Encoded Grammars and Low Latency Parallelization Strategies for CYK
Dunlop, A., Bodenstab, N., & Brian Roark, A. (2011) · Cited by 13
Accelerating HPCG on Tianhe-2: A hybrid CPU-MIC algorithm
Liu, Y., Zhang, X., Yang, C., Liu, F., & Lu, Y. (2014) · IEEE International Conference on Parallel and Distributed Systems (ICPADS) · doi:10.1109/padsw.2014.7097852 · Cited by 13
“Both SpMV and SymGS need neighboring communication to update halo for each subdomain before computing.”
InfluentialFrom Sparse Matrix to Optimal GPU CUDA Sparse Matrix Vector Product Implementation
Zein, A. H. E., & Rendell, A. P. L. (2010) · IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid) · doi:10.1109/ccgrid.2010.81 · Cited by 13
“The Unstructured matrices were represented by a set of 14 matrices taken from previous work by Williams et al [8].”
MethodAlgorithm-Directed Crash Consistence in Non-volatile Memory for HPC
Yang, S., Wu, K., Qiao, Y., Li, D., & Zhai, J. (2017) · IEEE International Conference on Cluster Computing (CLUSTER) · doi:10.1109/cluster.2017.61 · Cited by 13
“Algorithm knowledge has been used to address the problems of fault tolerance [16], [17], [18], [19], [20], performance optimization [21], [22], [23], and energy efficiency [24], [25].”
BackgroundMethodConvey HC-1 Hybrid Core Computer - The Potential of FPGAs in Numerical Simulation
Augustin, W., Weiß, J.-P., & Heuveline, V. (2010) · Cited by 13
Performance modeling of the sparse matrix–vector product via convolutional neural networks
Barreda, M., Dolz, M. F., Castaño, M. A., Alonso, P., & Quintana–Ort́ı, E. S. (2020) · The Journal of Supercomputing · doi:10.1007/s11227-020-03186-1 · Cited by 13
“1 For instance, the authors in [3, 4] found that typical sequential SpMV implementations generally achieve no more than 10% of the machine peak floating-point rate on commodity microprocessors.”
BackgroundRnR: A Software-Assisted Record-and-Replay Hardware Prefetcher
Zhang, C., Zeng, Y., Shalf, J. M., & Guo, X. (2020) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1109/micro50266.2020.00057 · Cited by 13
“Take the Sparse Matrix-Vector multiplication kernel (SpMV) [57] as an example, when the sparse matrix is stored in a CSR format, the row pointer, column array, and matrix value array are accessed in sequence and have good spatial locality.”
MethodSelf-citationPerformance Optimization of SpMV Using CRS Format by Considering OpenMP Scheduling on CPUs and MIC
Ohshima, S., Katagiri, T., & Matsumoto, M. (2014) · IEEE International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC) · doi:10.1109/mcsoc.2014.43 · Cited by 13
“Therefore, some applications use other matrix data formats such as the BCRS and ELL formats[1], [2].”
BackgroundMethodA Library for Pattern-based Sparse Matrix Vector Multiply
Belgin, M., Back, G., & Ribbens, C. J. (2010) · International Journal of Parallel Programming · doi:10.1007/s10766-010-0145-2 · Cited by 13
“Another recent study [37, 38] considered the impact of several known optimization techniques for SMVM on emerging multicore architectures.”
BackgroundTORCH Computational Reference Kernels - A Testbed for Computer Science Research
Kaiser, A., Williams, S. W., Madduri, K., Ibrahim, K. Z., Bailey, D. H., Demmel, J. W., & Strohmaier, E. (2010) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · doi:10.2172/1004197 · Cited by 13
“Williams et al’s recent multicore papers provide excellent information on performance optimization [105, 106].”
BackgroundSelf-citationOyarzun, G., Peyrolon, D., Álvarez, C., & Martorell, X. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.12371 · Cited by 13
“This data path generally leads to low resource utilization and compute efficiency in modern architectures [18].”
BackgroundFeature-based SpMV Performance Analysis on Contemporary Devices
Mpakos, P., Galanopoulos, D., Anastasiadis, P., Παπαδοπούλου, Ν., Koziris, N., & Goumas, G. (2023) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps54959.2023.00072 · Cited by 12
“Early works on multicore CPUs [1], [23] identify the bottlenecks discussed in this work, and propose techniques to alleviate them through autotuning [36], and compressed formats [28], [37], [38].”
BackgroundPorting FEASTFLOW to the Intel Xeon Phi: Lessons Learned
Venetis, I. E., Goumas, G., Geveler, M., & Dirk Ribbrock, A. (2014) · Cited by 12
Optimizing Large-Scale Graph Analysis on a Multi-threaded, Multi-core Platform
Cong, G., & Makarychev, K. (2011) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2011.393 · Cited by 12
An effective SPMV based on block strategy and hybrid compression on GPU
Cui, H., Wang, N., Wang, Y., Han, Q., & Xu, Y. (2021) · The Journal of Supercomputing · doi:10.1007/s11227-021-04123-6 · Cited by 12
“In order to improve the performance of sparse matrix vector multiplication, some other matrix compression formats are proposed such as blocked compressed sparse row (BCSR) format [13], row-grouped CSR (RGCSR) format [14], blocked ELLPACK (BELLPACK) format [15], sliced coordinate (SCOO) format [16], sliced ELLPACK (SEL…”
MethodLi, W., Cheng, H., Lu, Z., Lu, Y., & Liu, W. (2023) · IEEE International Conference on Cluster Computing (CLUSTER) · doi:10.1109/cluster52292.2023.00025 · Cited by 12
Matrix-Free Finite-Element Operator Application on Graphics Processing Units
Ljungkvist, K. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-14313-2_38 · Cited by 12
Characterizing dataset dependence for sparse matrix-vector multiplication on GPUs
Sedaghati, N., Ashari, A., Pouchet, L.-N., Parthasarathy, S., & Sadayappan, P. (2015) · Workshop on Parallel Programming for Analytics Applications (PPAA) · doi:10.1145/2726935.2726941 · Cited by 12
“Sparse storage representations have been studied extensively for CPUs [18, 19] as well as GPUs [6, 8, 9] and accelerators [13].”
BackgroundNew Sparse Matrix Storage Format to Improve The Performance of Total SPMV Time
Reddy, N. C. E., Prakash, R., & Guddeti, R. M. R. (2012) · doi:10.12694/scpe.v13i2.777 · Cited by 12
Bandwidth Reduced Parallel SpMV on the SW26010 Many-Core Platform
Sun, Q., Zhang, C., Wu, C., Zhang, J., & Li, L. (2018) · Proceedings of the International Conference on Parallel Processing · doi:10.1145/3225058.3225074 · Cited by 12
CCF: An efficient SpMV storage format for AVX512 platforms
Almasri, M., & Abu-Sufah, W. (2020) · Parallel Computing · doi:10.1016/j.parco.2020.102710 · Cited by 12
A Vector Caching Scheme for Streaming FPGA SpMV Accelerators
Umuroglu, Y., & Jahre, M. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-16214-0_2 · Cited by 12
Image feature extraction for mobile processors
Murphy, M., Keutzer, K., & Wang, H. (2009) · IEEE International Symposium on Workload Characterization · doi:10.1109/iiswc.2009.5306789 · Cited by 12
“A large portion of prior auto-tuning work is from the domain of high performance scientific computing, having targeted numerical kernels such as dense matrix-matrix multiplication [17], sparse matrix-vector multiplication [16], [18], and stencil codes for differential equations [4].”
BackgroundExecuting Optimized Irregular Applications Using Task Graphs within Existing Parallel Models
Krieger, C. D., Strout, M. M., Roelofs, J., & Bajwa, A. (2012) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc.companion.2012.43 · Cited by 12
“The BeBOP group at Berkeley has done an extensive amount of research on how to improve the serial [26] and parallel performance [27] of sparse matrix vector computations.”
BackgroundOKL: A Unified Language for Parallel Architectures
Medina, D. (2015) · Rice Research Repository (Rice University) · Cited by 12
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.