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 201–300 of 810
A parallel computing method using blocked format with optimal partitioning for SpMV on GPU
Yang, W., Li, K., & Li, K. (2017) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2017.09.010 · Cited by 33
“Other strategies partition sparse matrices according to the configuration of a computing environment, such as the cache scale of processors [15,12], the computing power of processors [16,17], and the data transmission bandwidth [13].”
BackgroundA unified sparse matrix data format for modern processors with wide SIMD unitsPreprint
Kreutzer, M., Hager, G., Wellein, G., Fehske, H., & Bishop, A. R. (2013) · arXiv (Cornell University) · Cited by 33
Compressed Multirow Storage Format for Sparse Matrices on Graphics Processing Units
Koza, Z., Matyka, M., Szkoda, S., & Mirosław, Ł. (2014) · SIAM Journal on Scientific Computing · doi:10.1137/120900216 · Cited by 32
“Several SpMV optimization strategies were already proposed for various designs of chip multiprocessors, including multicore central processing units (CPUs) from Intel and AMD [27], single- and dual-socket STI Cell [27], Sun UltraSPARC T2 [27], field programmable gate arrays (FPGAs) [7, 8], Intel Xeon Phi coprocessors…”
MethodBridging the gap between deep learning and sparse matrix format selection
Zhao, Y., Li, J., Liao, C., & Shen, X. (2018) · ACM SIGPLAN Notices · doi:10.1145/3200691.3178495 · Cited by 32
Large Scale Finite Element Analysis Via Assembly-Free Deflated Conjugate Gradient
Yadav, P., & Suresh, K. (2014) · Journal of Computing and Information Science in Engineering · doi:10.1115/1.4028591 · Cited by 32
A More Scalable and Efficient Parallelization of the Adaptive Integral Method—Part I: Algorithm
Wei, F., & Yılmaz, A. E. (2013) · IEEE Transactions on Antennas and Propagation · doi:10.1109/tap.2013.2291559 · Cited by 32
HICAMP: architectural support for efficient concurrency-safe shared structured data access
Cheriton, D. R., Firoozshahian, A., Solomatnikov, A., Stevenson, J. P., & Azizi, O. (2012) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/2150976.2151007 · Cited by 38
“Sparse matrix computations, and, in particular sparse matrix dense vector multiplication (SpMV) [32], are often the critical inner loop of certain applications including general high performance computing (HPC), embedded control systems, linear programming, and convex optimization.”
BackgroundLoop and data transformations for sparse matrix code
Venkat, A., Hall, M. W., & Strout, M. M. (2015) · ACM SIGPLAN Notices · doi:10.1145/2813885.2738003 · Cited by 32
Schubert, G., Fehske, H., Hager, G., & Wellein, G. (2011) · Parallel Processing Letters · doi:10.1142/s0129626411000254 · Cited by 31
“1 Related work In recent years the performance of various spMVM algorithms has been evaluated by several groups [1, 2, 3].”
Optimizing Sparse Matrix Vector Multiplication Using Cache Blocking Method on Fermi GPU
Xu, W., Zhang, H., Jiao, S., Wang, D., Song, F., & Liu, Z. (2012) · ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD) · doi:10.1109/snpd.2012.20 · Cited by 31
Automatic Restructuring of GPU Kernels for Exploiting Inter-thread Data Locality
Unkule, S., Shaltz, C., & Qasem, A. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-28652-0_2 · Cited by 31
“have also applied model-based autotuning techniques to sparse matrix computation that have yielded significant performance gains over CPU-based autotuned kernels [25].”
MethodMartone, M. (2014) · Parallel Computing · doi:10.1016/j.parco.2014.03.008 · Cited by 31
623 Tflop/s HPCG run on Tianhe-2: Leveraging millions of hybrid cores
Liu, Y., Yang, C., Liu, F., Zhang, X., Lu, Y., Du, Y., Yang, C., Xie, M., & Liao, X. (2015) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342015616266 · Cited by 31
“…techniques, such as software pipelining, register blocking, row or column sorting, and dynamic load scheduling, are studied in Vuduc et al. (2005), Williams et al. (2009), Monakov et al. (2010), and Liu et al. (2013) to optimize SpMV, the basic operation in a sparse iterative solver.”
MethodFEAST—realization of hardware‐oriented numerics for HPC simulations with finite elements
Turek, S., Dominik Göddeke, A., Becker, C., Buijssen, S. H. M., & Wobker, H. (2010) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.1584 · Cited by 31
“These results are in accordance with more detailed surveys of SpMV [ 1 ] .”
BackgroundResultMEISSA: Multiplying Matrices Efficiently in a Scalable Systolic Architecture
Asgari, B., Hadidi, R., & Kim, H. (2020) · IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD) · doi:10.1109/iccd50377.2020.00036 · Cited by 30
PIT: Optimization of Dynamic Sparse Deep Learning Models via Permutation Invariant Transformation
Zheng, N., Jiang, H., Zhang, Q., Han, Z., Ma, L., Yang, Y., Yang, F., Zhang, C., Qiu, L., Yang, M., et al. (2023) · ACM SIGOPS Symposium on Operating Systems Principles (SOSP) · doi:10.1145/3600006.3613139 · Cited by 45
“In addition to the above software solutions, many hardware optimizations have been proposed for the sparse computation of deep learning models [2, 13, 17, 32, 62].”
BackgroundImproving the arithmetic intensity of multigrid with the help of polynomial smoothers
Ghysels, P., Kłosiewicz, P., & Vanroose, W. (2012) · Numerical Linear Algebra with Applications · doi:10.1002/nla.1808 · Cited by 30
“Just to name a few, we mention cache-aware techniques based on the idea of tiling [3–5], possibly with autotuning of parameters [6], cache oblivious approaches [7, 8], and wavefront parallelization [9, 10].”
BackgroundEvaluation and optimization of multicore performance bottlenecks in supercomputing applications
Diamond, J., Burtscher, M., McCalpin, J. D., Kim, B.-D., Keckler, S. W., & Browne, J. C. (2011) · IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS) · doi:10.1109/ispass.2011.5762713 · Cited by 30
“The literature is full of work on optimizing specific scientific kernels for multicore CPUs, including stencil computations [5], sparse matrix-vector multiplication [25], and even a LatticeBoltzmann computation [20].”
BackgroundSemi-External Memory Sparse Matrix Multiplication for Billion-Node Graphs
Zheng, D., Mhembere, D., Lyzinski, V., Vogelstein, J. T., Priebe, C. E., & Burns, R. C. (2016) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2016.2618791 · Cited by 30
“Sparse matrices derived from graphs impose additional challenges.”
BackgroundData Management in Machine Learning Systems
Böehm, M., Kumar, A., & Yang, J. (2019) · Synthesis lectures on data management · doi:10.1007/978-3-031-01869-5 · Cited by 41
A high-performance parallel algorithm for nonnegative matrix factorization
Kannan, R., Ballard, G., & Park, H. (2016) · ACM SIGPLAN Notices · doi:10.1145/3016078.2851152 · Cited by 30
Direct N-body Kernels for Multicore Platforms
Arora, N., Shringarpure, A., & Vuduc, R. W. (2009) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2009.71 · Cited by 30
Self-citationSpMV: A Memory-Bound Application on the GPU Stuck Between a Rock and a Hard Place
Davis, J. D., & Chung, E. S. (2012) · Cited by 29
Wong, J., Ellen Kuhl, A., & Darve, E. (2015) · International Journal for Numerical Methods in Engineering · doi:10.1002/nme.4865 · Cited by 29
“Our novel algorithms above are compared against several available standard SPMV algorithms using a set of sparse matrices commonly used in benchmarking SPMV methods [42, 43, 29].”
Improving the Performance of Dynamical Simulations Via Multiple Right-Hand Sides
Liu, X., Chow, E., Vaidyanathan, K., & Smelyanskiy, M. (2012) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2012.14 · Cited by 29
“The most costly steps of this procedure are the solves with the resistance matrices.”
BackgroundGong, Z., Tang, W., Bennett, D. A., & Thill, J. (2012) · International Journal of Geographical Information Systems · doi:10.1080/13658816.2012.741240 · Cited by 29
“2008), sparse matrix–vector multiplication (Williams et al .”
BackgroundAutomatic Library Generation for BLAS3 on GPUs
Cui, H., Wang, L., Xue, J., Yang, Y., & Feng, X. (2011) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2011.33 · Cited by 32
“On the state-of-theart architecture platforms, the auto-tuning technology has been applied to some specific applications, such as sparse matrixvector multiply [13], stencil computations [14], and dense linear algebra [2].”
MethodModeling memory concurrency for multi-socket multi-core systems
Mandal, A., Fowler, R., & Porterfield, A. (2010) · IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS) · doi:10.1109/ispass.2010.5452064 · Cited by 38
“AMD system performance improves dramatically with fully populated DIMM slots [21].”
BackgroundDynamic Sparse-Matrix Allocation on GPUs
King, J., Gilray, T., Kirby, R. M., & Might, M. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-41321-1_4 · Cited by 29
“demonstrated the efficacy of using architecture-specific data structures to optimize performance [19,20].”
BackgroundWorkStream -- A Design Pattern for Multicore-Enabled Finite Element Computations
Turcksin, B., Kronbichler, M., & Bangerth, W. (2016) · ACM Transactions on Mathematical Software · doi:10.1145/2851488 · Cited by 38
Predicting and optimizing system utilization and performance via statistical machine learning
Patterson, D. A., & Ganapathi, A. (2009) · Cited by 30
Exploring New Architectures in Accelerating CFD for Air Force Applications
Dongarra, J. J., Peterson, G. D., Tomov, S. Z., Allred, J., Natoli, V. D., & Richie, D. A. (2008) · DoD High Performance Computing Modernization Program Users Group Conference (HPCMP-UGC) · doi:10.1109/dod.hpcmp.ugc.2008.12 · Cited by 29
A survey of sparse matrix-vector multiplication performance on large matricesPreprint
Grossman, M., Thiele, C., Araya–Polo, M., Frank, F., Alpak, F. O., & Sarkar, V. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1608.00636 · Cited by 29
“Past work has generally found that SpMV is a memory-bound kernel whose performance is heavily tied to the cache hierarchy and memory bandwidth of the hardware platform it runs on [11].”
BackgroundVectorized OpenCL implementation of numerical integration for higher order finite elements
Krużel, F., & Banaś, K. (2013) · Computers & Mathematics with Applications · doi:10.1016/j.camwa.2013.08.026 · Cited by 28
Understanding sources of ineffciency in general-purpose chips
Hameed, R., Qadeer, W., Wachs, M. A., Azizi, O., Solomatnikov, A., Lee, B. C., Richardson, S., Kozyrakis, C., & Horowitz, M. (2011) · Communications of the ACM · doi:10.1145/2001269.2001291 · Cited by 28
SPAPT: Search Problems in Automatic Performance Tuning
Balaprakash, P., Wild, S. M., & Norris, B. (2012) · Procedia Computer Science · doi:10.1016/j.procs.2012.04.214 · Cited by 31
“Keywords autotuning, performance tuning, benchmark, test suite, kernels”
BackgroundAccelerating Sparse Data Orchestration via Dynamic Reflexive Tiling
Odemuyiwa, T. O., Asghari-Moghaddam, H., Pellauer, M., Hegde, K., Tsai, P.-A., Crago, N. C., Jaleel, A., Owens, J. D., Solomonik, E., Emer, J., et al. (2023) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/3582016.3582064 · Cited by 31
“Thematrices are from HB [20], Bova [13], DNVS [18], Hamm [28], LAW [12], Williams [56], and SNAP collection [36].”
An energy efficient column-major backend for FPGA SpMV accelerators
Umuroglu, Y., & Jahre, M. (2014) · IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD) · doi:10.1109/iccd.2014.6974716 · Cited by 28
“0 1 2 3 4 values[0] values[4] x[0] x[2] y[0] y[3]”
BackgroundInfluentialSparse Matrix Formats Evaluation and Optimization on a GPU
Hugues, M. R., & Petiton, S. G. (2010) · 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.2010.85 · Cited by 28
“This sparse format has been evaluated and optimized on different platforms like Cell BE, Intel, AMD and Sun processors [2].”
MethodScaling Support Vector Machines on modern HPC platforms
You, Y., Fu, H., Song, S. L., Randles, A. P., Kerbyson, D. J., Márquez, A., Yang, G., & Hoisie, A. (2014) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2014.09.005 · Cited by 31
On the Performance of an Algebraic Multigrid Solver on Multicore Clusters
Baker, A. H., Schulz, M., & Yang, U. M. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-19328-6_12 · Cited by 28
“While good results have been achieved for dense matrix kernels [1, 21, 5], obtaining good performance for sparse matrix kernels is a much bigger challenge [20, 19].”
BackgroundCSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector MultiplicationPreprint
Liu, W., & Vinter, B. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1503.05032 · Cited by 28
“These two meth-ods are respectively known as the CSR-scalar and the CSR-vector algorithms, and have been implemented on CPUs [33] and GPUs [4, 29].”
BackgroundMethodAccelerating PageRank using Partition-Centric ProcessingPreprint
Lakhotia, K., Kannan, R., & Prasanna, V. K. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1709.07122 · Cited by 39
“Cache Blocking (CB) is another popular method used to induce locality by restricting random node accesses to an address range that can fit in cache [18], [19].”
MethodInput-aware auto-tuning for directive-based GPU programming
Magni, A., Grewe, D., & Johnson, N. P. (2013) · doi:10.1145/2458523.2458530 · Cited by 27
Autotuning Sparse Matrix-Vector Multiplication for Multicore
Byun, J.-H., Lin, R. C.-H., Yelick, K., & Demmel, J. W. (2012) · Cited by 27
Self-citationIn-Core Optimization of High-Order Stencil Computations.
Dursun, H., Nomura, K., Wang, W., Kunaseth, M., Liu, P., Seymour, R. J., Kalia, R. K., Nakano, A., & Vashishta, P. D. (2009) · Parallel and Distributed Processing Techniques and Applications · Cited by 27
Wei, F., & Yılmaz, A. E. (2011) · Parallel Computing · doi:10.1016/j.parco.2011.03.006 · Cited by 26
Sparse matrix partitioning for optimizing SpMV on CPU-GPU heterogeneous platforms
Benatia, M. A., Ji, W., Wang, Y., & Shi, F. (2019) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342019886628 · Cited by 26
Parallelization of the artificial bee colony (ABC) algorithm
Subotić, M., Tuba, M., & Stanarevic, N. (2010) · Cited by 26
Analysis and performance results of computing betweenness centrality on IBM Cyclops64
Tan, G., Sreedhar, V. C., & Gao, G. R. (2009) · The Journal of Supercomputing · doi:10.1007/s11227-009-0339-9 · Cited by 26
“[34]’s work on sparse matrix-vector multiplication on conventional multi-core platforms implies that new methods for parallel irregular computing is imperative.”
BackgroundData access optimizations for highly threaded multi-core CPUs with multiple memory controllers
Hager, G., Zeiser, T., & Wellein, G. (2008) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2008.4536341 · Cited by 26
Improving the Performance of the Symmetric Sparse Matrix-Vector Multiplication in Multicore
Gkountouvas, T., Karakasis, V., Kourtis, K., Goumas, G., & Koziris, N. (2013) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2013.43 · Cited by 27
Generating optimal CUDA sparse matrix–vector product implementations for evolving GPU hardware
Zein, A. H. E., & Rendell, A. P. L. (2011) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.1732 · Cited by 26
Optimization of Block Sparse Matrix-Vector Multiplication on Shared-Memory Parallel Architectures
Eberhardt, R., & Hoemmen, M. F. (2016) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2016.42 · Cited by 26
Vectorized Parallel Sparse Matrix-Vector Multiplication in PETSc Using AVX-512
Zhang, H., Mills, R. T., Rupp, K., & Smith, B. (2018) · Proceedings of the International Conference on Parallel Processing · doi:10.1145/3225058.3225100 · Cited by 26
“Because of the low arithmetic intensity of these sparse kernels, tuning or optimizing their performance on many-core architectures [24], such as GPUs, is generally focused on achieving optimal memory bandwidth, rather than the complicated register-and cache-centric optimizations required for…”
BackgroundConflict-free symmetric sparse matrix-vector multiplication on multicore architectures
Elafrou, A., Goumas, G., & Koziris, N. (2019) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/3295500.3356148 · Cited by 26
Compressed linear algebra for large-scale machine learning
Elgohary, A., Böehm, M., Haas, P. J., Reiss, F. R., & Reinwald, B. (2017) · The VLDB Journal · doi:10.1007/s00778-017-0478-1 · Cited by 26
“Williams et al. studied various optimizations and storage formats for sparse matrix-vector multiplications on multi-core systems [48].”
BackgroundSome useful strategies for unstructured edge‐based solvers on shared memory machines
Aubry, R., Houzeaux, G., Vázquez, M., & Cela, J. M. (2010) · International Journal for Numerical Methods in Engineering · doi:10.1002/nme.2973 · Cited by 26
“The optimizations considered in this paper stay mainly at an algorithmic level, while low level optimizations such as register, cache and TLB blocking, and SIMD intrinsics and other data structure optimizations are also of relevant value [2].”
BackgroundMemory-efficient optimization of Gyrokinetic particle-to-grid interpolation for multicore processors
Madduri, K., Williams, S., Ethier, S., Oliker, L., Shalf, J. M., Strohmaier, E., & Yelicky, K. (2009) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/1654059.1654108 · Cited by 26
“As the existing threaded programming model (based on pthreads) is likely beyond the reach of most programmers, and the subtle serial performance bugs in an OpenMP model will become increasingly severe as we scale the number of cores, we believe auto-tuned frameworks that combine the auto-tuning [15] and flexible and p…”
BackgroundSelf-citationParallel Iterative Linear Solvers on GPU: A Financial Engineering Case
Gaikwad, A., & Toke, I. M. (2010) · Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP) · doi:10.1109/pdp.2010.55 · Cited by 25
“Sev eral algorithmic as well as architecture specific optimizations have been proposed to improve the performance of both serial and parallel implementations [26], [25], [14], [13].”
MethodResultEnabling Runtime SpMV Format Selection through an Overhead Conscious Method
Zhou, W., Zhao, Y., Shen, X., & Chen, W. (2019) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2019.2932931 · Cited by 25
“Since its performance is essential for these applications, it has motivated a large volume of research on optimizing its performance [7], [8], [9], [10], [11].”
BackgroundSelecting optimal SpMV realizations for GPUs via machine learning
Dufrechou, E., Ezzatti, P., & Quintana–Ort́ı, E. S. (2021) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342021990738 · Cited by 25
“Other interesting efforts related with this topic are the article by Williams et al. (2007) where the authors study some optimization techniques for the SpMV kernel over several hardware platforms; the proposal by Erguiz et al. (2017) with advances over the automatic selection of different sparse…”
BackgroundOptimization techniques for sparse matrix–vector multiplication on GPUs
Maggioni, M., & Berger-Wolf, T. Y. (2016) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2016.03.011 · Cited by 25
“As a consequence, its parallel performance is generally reported to sustain low fractions of computational peak [8].”
Performance analysis and optimization for SpMV based on aligned storage formats on an ARM processor
Zhang, Y., Yang, W., Li, K., Tang, D., & Li, K. (2021) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2021.08.002 · Cited by 25
“Therefore, a sparse matrix can be compressed to store the nonzero elements, such as the original coordinate (COO) format and the compressed sparse column/row (CSC/CSR) [19].”
Improving parallelism and locality with asynchronous algorithms
Liu, L., & Li, Z. (2010) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/1693453.1693483 · Cited by 25
A Systematic Literature Survey of Sparse Matrix-Vector MultiplicationPreprint
Gao, J., Liu, B., Ji, W., & Huang, H. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2404.06047 · Cited by 25
“Cache optimization : Cache-blocking [85][88][137][138] partitions the sparse matrix into smaller blocks that can fit in the cache and performs computations on these blocks, which increases temporal locality by reordering memory accesses.”
MethodA superlinear speedup region for matrix multiplication
Gušev, M., & Ristov, S. (2013) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.3102 · Cited by 24
“Williams et al. [37] determine that greater number of threads generates conflict cache misses in the same cache set when they share some cache with lower set associativity.”
BackgroundReordering Algorithms for Increasing Locality on Multicore Processors
Pichel, J. C., Singh, D. E., & Carretero, J. (2008) · 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.2008.96 · Cited by 24
Optimizing and Scaling HPCG on Tianhe-2: Early Experience
Zhang, X., Yang, C., Liu, F., Liu, Y., & Lu, Y. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-11197-1_3 · Cited by 23
“as [9,12,13,1,10].”
Guo, P., & Wang, L. (2014) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.3217 · Cited by 23
“Our experimental evaluation does not adopt the rest 6 matrices (“Wind Tunnel”, “Economics”, “FEM/Accelerator”, “Circuit”, “Webbase”, and “LP”) in [32] since NVIDIA’s SpMV implementations cannot execute ELL SpMV kernel on the reference architecture because of the limitation of “num cols per row”.”
BackgroundAdaptive Multi-level Blocking Optimization for Sparse Matrix Vector Multiplication on GPU
Nagasaka, Y., Nukada, A., & Matsuoka, S. (2016) · Procedia Computer Science · doi:10.1016/j.procs.2016.05.304 · Cited by 23
“More recently, numerous sparse formats have been proposed for specific processor architectures or matrices in order to achieve better performance of SpMV computation [12, 13, 10, 15].”
BackgroundFine-grained accelerators for sparse machine learning workloads
Mishra, A. K., Nurvitadhi, E., Venkatesh, G., Pearce, J., & Marr, D. (2017) · Asia and South Pacific Design Automation Conference (ASP-DAC) · doi:10.1109/aspdac.2017.7858395 · Cited by 23
“We explored a well known software optimization method for these data structures - blocking [22].”
MethodAn efficient SIMD compression format for sparse matrix‐vector multiplication
Chen, X., Xie, P., Chi, L., Liu, J., & Gong, C. (2018) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.4800 · Cited by 23
Tang, W. T., Tan, W. J., Goh, R. S. M., Turner, S. J., & Wong, W. (2014) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2014.2357437 · Cited by 23
“Index Terms—Sparse matrix format, data compression, matrix-vector multiplication, GPU, parallelism, memory bandwidth Ç”
Post-Quantum Era in V2X Security: Convergence of Orchestration and Parallel Computation
Zeydan, E., Türk, Y., Aksoy, B., & Tasbag, Y. Y. (2022) · IEEE Communications Standards Magazine · doi:10.1109/mcomstd.0001.2100060 · Cited by 22
An I/O Bandwidth-Sensitive Sparse Matrix-Vector Multiplication Engine on FPGAs
Sun, S. M., Monga, M., Jones, P. H., & Zambreno, J. (2011) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2011.2161389 · Cited by 22
“In [1], the authors explore the potential advantages of explicit multicore programming.”
BackgroundOptimizing sparse matrix-vector multiplication on CUDA
Wang, Z., Xu, X., Zhao, W., Zhang, Y., & He, S. (2010) · International Conference on Education Technology and Computer · doi:10.1109/icetc.2010.5529724 · Cited by 22
“In sparse matrix vector multiplication kernel, if all executed rows in sparse matrix can not fill with all thread blocks, it can increase the branch of SpMV kernel function determine and reduce the computing performance [11].”
BackgroundKrasnopolsky, B. I. (2018) · Computer Physics Communications · doi:10.1016/j.cpc.2018.03.023 · Cited by 22
“The real performance of linear algebra algorithms with sparse matrices of the general form does not exceed several percent of the peak performance [16, 17, 18].”
BackgroundFork-Join and Data-Driven Execution Models on Multi-core Architectures: Case Study of the FMM
Amer, A., Maruyama, N., Pericàs, M., Taura, K., Yokota, R., & Matsuoka, S. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38750-0_19 · Cited by 21
“authors used stencil-computation and sparse matrix-vector multiplication kernels and optimized them for state-of-the-art multi-core architectures[27] [28].”
MethodpSyncPIM: Partially Synchronous Execution of Sparse Matrix Operations for All-Bank PIM Architectures
Baek, D., Hwang, S., & Huh, J. (2024) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca59077.2024.00034 · Cited by 21
“33 × 10 − 5 SpTRSV, PCG pdb1HYS [45] 36,417 3 .”
InfluentialAutomatic Generation of Multicore Chemical Kernels
Linford, J. C., Michalakes, J. G., Vachharajani, M., & Sandu, A. (2010) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2010.106 · Cited by 23
“For this reason, existing literature tends to focus on the model subcomponents, such as basic linear algebra operations [6], [7], [8], and does not comprehensively address this problem domain for chemical kinetics and related problems on real-world domains.”
BackgroundMethodGeveler, M., Dirk Ribbrock, A., Mallach, S., & Dominik Göddeke, A. (2011) · Journal of Computational Science · doi:10.1016/j.jocs.2011.01.008 · Cited by 21
“At the same time, the well-known memory wall has become an ever larger limiting obstacle, as currently sustainable memory bandwidths do not suffice to serve all cores situated on a single chip simultaneously [4, 28].”
BackgroundPerformance Evaluation and Analysis of Linear Algebra Kernels in the Prototype Tianhe-3 Cluster
You, X., Yang, H., Luan, Z., Liu, Y., & Qian, D. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-18645-6_6 · Cited by 21
“Different storage forms are proposed with different SpMV algorithms, such as CSR [32], CSR5 [15] and ELLPACK [16].”
MethodUsing Ginkgo's memory accessor for improving the accuracy of memory‐bound low precision BLAS
Grützmacher, T., Anzt, H., & Quintana–Ort́ı, E. S. (2021) · Software Practice and Experience · doi:10.1002/spe.3041 · Cited by 25
Data Management in Machine Learning Systems
Boehm, M., Kumar, A., & Yang, J. (2019) · Data Management in Machine Learning Systems · doi:10.2200/s00895ed1v01y201901dtm057 · Cited by 55
Stencil-Aware GPU Optimization of Iterative Solvers
Lowell, D., Godwin, J., Holewinski, J., Karthik, D., Choudary, C., Mametjanov, A., Norris, B., Sabin, G., Sadayappan, P., & Sarich, J. (2013) · SIAM Journal on Scientific Computing · doi:10.1137/120883153 · Cited by 21
“, [13, 30, 34]) explore this structure, but address only a portion of the relevant kernels and typically rely on general sparse matrix formats such as those described in Section 2.”
BackgroundMethodUse of hybrid recursive CSR/COO data structures in sparse matrix-vector multiplication
Martone, M., Filippone, S., Tucci, S., Gepner, P., & Paprzycki, M. (2010) · Proceedings of the International Multiconference on Computer Science and Information Technology · doi:10.1109/imcsit.2010.5680039 · Cited by 21
“I T IS known that computations with sparse matrices incur very poor memory performance: indirect addressing causes unpredictable run-time dependencies in memory read/write access; memory access has poor data locality (just to name a two key aspects; see also [1], [2], [3]).”
BackgroundSparse Matrix-Vector Multiplication on Multicore and Accelerators
Williams, S., Bell, N., Choi, J. W., Garland, M., Oliker, L., & Vu, R. (2010) · Chapman & Hall/CRC computational science series/Chapman & Hall/CRC computational science · doi:10.1201/b10376-8 · Cited by 21
Self-citationPerformance modeling and optimization of sparse matrix-vector multiplication on NVIDIA CUDA platform
Xu, S., Xue, W., & Lin, H. X. (2011) · The Journal of Supercomputing · doi:10.1007/s11227-011-0626-0 · Cited by 20
“Due to the growing adoption and popularity of GPUs, there have been recent works on porting SpMV to these platforms [7, 10, 13].”
A CAD-based methodology to optimize HLS code via the roofline model
Siracusa, M., Tucci, L. D., Rabozzi, M., Williams, S., Sozzo, E. D., & Santambrogio, M. D. (2020) · doi:10.1145/3400302.3415730 · Cited by 20
“Figure 1: IBM QS20 Cell Blade [12, 34, 35] Roofline model.”
Self-citationVCSR: An Efficient GPU Memory-Aware Sparse Format
Karimi, E., Agostini, N. B., Dong, S., & Kaeli, D. R. (2022) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2022.3177291 · Cited by 20
“mizations have been proposed for sparse matrices to better manage memory and improve execution performance on CPUs [1], [2], [3] and GPUs [4], [5], [6], [7], [8], [9], [10].”
BackgroundPredicting an Optimal Sparse Matrix Format for SpMV Computation on GPU
Bayyapu, N., Reddy, G. R. M., & Raghavendra, P. S. (2014) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2014.160 · Cited by 20
“The benchmark input matrices for SpMV computation from [18], [19] are considered for evaluating the proposed sparse format prediction model and the salient features are given in Table V.”
BackgroundCompiled multithreaded data paths on FPGAs for dynamic workloads
Halstead, R. J., & Najjar, W. A. (2013) · doi:10.5555/2555729.2555732 · Cited by 20
2012 Freeman Scholar Lecture: Computational Fluid Dynamics on Graphics Processing Units
Vanka, S. P. (2013) · Journal of Fluids Engineering · doi:10.1115/1.4023858 · Cited by 20
Optimizing collective communication on multicores
Nishtala, R., & Yelick, K. (2009) · USENIX conference on Hot topics in parallelism · Cited by 20
Self-citationMinimizing synchronizations in sparse iterative solvers for distributed supercomputers
Zhu, S., Gu, T.-X., & Liu, X. (2013) · Computers & Mathematics with Applications · doi:10.1016/j.camwa.2013.11.008 · Cited by 20
“For general sparse matrices, efficient matrix-vector multiplications need sophisticated techniques [46], whereas for some structured sparse matrices, sparse matrix-vector multiplications usually only need local communication—only exchanging data with its neighbours, especially the data structure of the underlying spar…”
BackgroundZhang, J., & Gruenwald, L. (2018) · ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA) (GRADES-NDA) · doi:10.1145/3210259.3210263 · Cited by 20
“It was first used by Samuel Williams et al [51] as a dataset representing web connectivity matrix for experiments on SpMV and later was used by several studies for SpGEMM, including CUSP, bhSPARSE, BalancedHash and HybridSparse on GPUs.”
MethodZhang, J., Wan, J., Li, F., Mao, J., Li, Z., Yuan, J., Liu, E., & Yu, Z. (2015) · Future Generation Computer Systems · doi:10.1016/j.future.2015.03.005 · Cited by 20
Efficient Finite Element Geometric Multigrid Solvers for Unstructured Grids on GPUs
Geveler, M., Dirk Ribbrock, A., & Zajac, P. (n.d.) · Cited by 20
dCSR: A Memory-Efficient Sparse Matrix Representation for Parallel Neural Network Inference
Trommer, E., Waschneck, B., & Kumar, A. S. (2021) · International Conference on Computer Aided Design · doi:10.1109/iccad51958.2021.9643506 · Cited by 23
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.