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 501–600 of 810
Increasing data reuse of sparse algebra codes on simultaneous multithreading architectures
Pichel, J. C., Heras, D. B., Cabaleiro, J. C., & Rivera, F. F. (2009) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.1404 · Cited by 6
Factorized parallel preconditioner for the saddle point problem
Lazarov, B. S., & Sigmund, O. (2010) · International Journal for Numerical Methods in Biomedical Engineering · doi:10.1002/cnm.1366 · Cited by 6
Parallel resolution of the 3D Helmholtz equation based on multi‐graphics processing unit clusters
Ortega, G., Lobera, J., García, I., Arroyo, M. P., & Garzón, E. M. (2014) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.3212 · Cited by 6
“Several optimizations have made it possible to improve the performance of sparse computation on current multicore platforms [24, 25] and on short-vector single instruction, multiple data architectures [26].”
BackgroundData Analytics with NVLink: An SpMV Case Study
Buono, D., Artico, F., Checconi, F., Choi, J. W., Que, X., & Schneidenbach, L. (2017) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/3075564.3075569 · Cited by 6
“A few examples with focus on CPU-based SpMV can be found in [8], [13] and [14].”
BackgroundParallel application library for object recognition
Keutzer, K., & Su, B.-Y. (2012) · Cited by 6
A sparse matrix vector multiplication accelerator based on high-bandwidth memory
Li, T., & Shen, L. (2022) · Computers & Electrical Engineering · doi:10.1016/j.compeleceng.2022.108488 · Cited by 6
Characterization of Large-scale HPC Workloads with non-naïve I/O Roofline Modeling and Scoring
Zhu, Z.-B., & Neuwirth, S. (2023) · IEEE International Conference on Parallel and Distributed Systems (ICPADS) · doi:10.1109/icpads60453.2023.00112 · Cited by 6
“Description SpMV [21] 0.17 - 0.25 Sparse Matrix-Vector multiply: y = A*x where A is a sparse matrix and x, y are dense vectors; multiplies and adds equal.”
BackgroundInfluentialSpChar: Characterizing the sparse puzzle via decision trees
Sgherzi, F., Siracusa, M., Fernandez, I., Armejach, A., & Moretó, M. (2024) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2024.104941 · Cited by 6
Visual MPI Performance Analysis using Event Flow Graphs
Aguilar, X., Fürlinger, K., & Laure, E. (2015) · Procedia Computer Science · doi:10.1016/j.procs.2015.05.322 · Cited by 6
“It could be optimized by using specialized libraries such as PETSc (the Portable, Extensible Toolkit for Scientific Computation) or more optimized algorithms for the SpMV operation such as the work in [21].”
MethodParallel GMRES Incomplete Orthogonalization Auto-Tuning
Aquilanti, P.-Y., Petiton, S. G., & Calandra, H. (2011) · Procedia Computer Science · doi:10.1016/j.procs.2011.04.245 · Cited by 6
Sparse matrix-vector multiplication on network-on-chip
Sun, C., Götze, J., Jheng, H.-C., & Ruan, S.-J. (2010) · Advances in radio science · doi:10.5194/ars-8-289-2010 · Cited by 6
“In the past few years, many researchers have presented the hardware solutions utilizing the feature of the pipeline ability and the parallelism inherent from the SMVM computation (Sun et al., 2007; Gregg et al., 2007; Gotze and Schwiegelshohn, 1988; Williams et al., 2007).”
BackgroundA case study of streaming storage format for sparse matrices
Jain-Mendon, S., & Sass, R. R. (2012) · International Conference on ReConFigurable Computing and FPGAs (ReConFig) · doi:10.1109/reconfig.2012.6416788 · Cited by 6
“In Table II we compare our implementation with a single-core, all-thread performance on various multicore processors reported in [5].”
MethodOptimizing sparse matrix vector multiplication on emerging multicores
Kislal, O., Ding, W., Kandemir, M., & Demirkiran, I. (2013) · doi:10.1109/mucocos.2013.6633600 · Cited by 6
Cache Impacts of Datatype Acceleration
Wu, L., Kim, M. A., & Edwards, S. A. (2011) · IEEE Computer Architecture Letters · doi:10.1109/l-ca.2011.25 · Cited by 6
“Multiple studies in a range of domains conclude that the quality of interaction across an application’s data structures is a significant determinant of performance [7], [8], [9].”
BackgroundRandom access schemes for efficient FPGA SpMV acceleration
Umuroglu, Y., & Jahre, M. (2016) · Microprocessors and Microsystems · doi:10.1016/j.micpro.2016.02.015 · Cited by 6
Performance Optimization for SpMV on Multi-GPU Systems Using Threads and Multiple Streams
Guo, P., & Zhang, C. (2016) · International Symposium on Computer Architecture and High Performance Computing Workshops (SBAC-PADW) · doi:10.1109/sbac-padw.2016.20 · Cited by 7
“The HYB storage scheme is illustrated in Figure 1, assuming that we set the given threshold K as K = 3.”
AXC: A new format to perform the SpMV oriented to Intel Xeon Phi architecture in OpenCL
Coronado‐Barrientos, E., Indalecio, G., & Garcia-Loureiro, A. J. (2018) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.4864 · Cited by 6
A sparse matrix‐vector multiplication method with low preprocessing cost
Aktemur, B. (2018) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.4701 · Cited by 6
“23 , 28 However, the cost of For this reason, some recent work have focused on optimizing SpMV with little or no preprocessing cost on the GPU, 6 , 7 , 9 , 10 CPU, 8 or both.”
BackgroundA Fully Structure-Driven Performance Analysis of Sparse Matrix-Vector Multiplication
Sandhu, P., Verbrugge, C., & Hendren, L. J. (2020) · ACM/SPEC International Conference on Performance Engineering (ICPE) · doi:10.1145/3358960.3379131 · Cited by 6
“[37] presented several optimization strategies like cache blocking, TLB blocking, register blocking, loop optimizations, software prefetching andmore to show significant improvements on their set of 14 sparse matrices which were collected from a variety of actual applications.”
BackgroundYu, X., Ma, H., Qu, Z., Fang, J., & Liu, W. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-79478-1_20 · Cited by 6
Development of a finite element method for neutron transport equation approximations
Ferràndiz, A. V. (2018) · RiuNet (Universitat Politècnica de València) · doi:10.4995/thesis/10251/98522 · Cited by 6
Temporal Load Imbalance on Ondes3D Seismic Simulator for Different Multicore ArchitecturesPreprint
Solórzano, A. L. V., Navaux, P. O. A., & Schnorr, L. M. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2409.11392 · Cited by 6
“A paper investigates the performance of a sparse matrix-vector multiply in four architectures from different vendors [24].”
BackgroundDo the middle letters of \OLAP" stand for Linear Algebra (\LA")?
Macedo, H. D., & Oliveira, J. N. (2011) · Cited by 5
Optimizing the Linear Fascicle Evaluation Algorithm for Multi-core and Many-core Systems
Aggarwal, K., & Bondhugula, U. K. R. (2020) · ACM Transactions on Parallel Computing · doi:10.1145/3418075 · Cited by 5
“New representations [Belgin et al. 2009; Bell and Garland 2009; Liu et al. 2013; Mellor-Crummey and Garvin 2004; Shantharam et al. 2011; Vuduc and Moon 2005; Williams et al. 2007], transformations [Ding and Kennedy 1999; Han and Tseng 2006; Mitchell et al.”
BackgroundInfluentialAn Early Performance Study of Large-Scale POWER8 SMP Systems
Liu, X., Buono, D., Checconi, F., Choi, J. W., Que, X., Petrini, F., Gunnels, J. A., & Stuecheli, J. A. (2016) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2016.14 · Cited by 5
Adaptive Sparse Matrix-Vector Multiplication on CPU-GPU Heterogeneous Architecture
Jing, N., Zhang, C., Zou, D., Xia, F., Lu, L., Wang, X., & Zhao, F. (2019) · High Performance Computing and Cluster Technologies Conference (HPCCT) · doi:10.1145/3341069.3341072 · Cited by 5
“Williams uses three types of optimization techniques, such as low-level code optimization, data structure optimization, and parallel optimization, to improve the SpMV performance on current multi-core platforms [9].”
MethodDhandhania, S., Deodhar, A., Pogorelov, K., Biswas, S., & Langguth, J. (2021) · International Conference on Parallel Processing Workshops (ICPPW) · doi:10.1145/3458744.3474049 · Cited by 5
“Prior work has studied the performance of SpMV on multicore CPUs [34] and GPUs [2] and defined some basic formats.”
BackgroundPerformance of a Structure-Detecting SpMV Using the CSR Matrix Representation
Pabst, H., Beverly Bachmayer, E., & Klemm, M. (2012) · International Symposium on Parallel and Distributed Computing · doi:10.1109/ispdc.2012.9 · Cited by 5
Performance evaluation of sparse matrix products in UPC
González‐Domínguez, J., García-López, Ó., Taboada, G. L., Martín, M. J., & Touriño, J. (2012) · The Journal of Supercomputing · doi:10.1007/s11227-012-0796-4 · Cited by 5
“Previous works have pointed out that a key aspect in the performance of the sparse matrix-vector product is the computational load balance [20].”
BackgroundA Comparison of Methods for Community Detection in Large Scale Networks
Vieira, V. D. F., & Evsukoff, A. G. (2012) · Studies in computational intelligence · doi:10.1007/978-3-642-30287-9_9 · Cited by 5
Optimizing Process-to-Core Mappings for Two Dimensional Broadcast/Reduce on Multicore Architectures
Karlsson, C., Davies, T., Ding, C., Liu, H., & Chen, Z. (2011) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2011.26 · Cited by 5
“However, in today’s high performance scientific computing, many MPI programs (e.g., ScaLAPACK applications, High Performance Linpack Benchmark HPL, and many PDE solvers based on domain decomposition methods) organize their computational processes as multidimensional process grids [22], with the…”
BackgroundApplications of the streamed storage format for sparse matrix operations
Guo, D., & Gropp, W. (2013) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342012470469 · Cited by 5
“Williams et al. (2009) tested SpMV on some multi-core platforms and discussed several tuning techniques, including different kinds of blocking, loop optimization, SIMDization, and software prefetching.”
BackgroundMethodEstablishing a Miniapp as a programmability proxy
Stone, A., Dennis, J. M., & Strout, M. M. (2012) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/2145816.2145881 · Cited by 5
A new method of Sparse Matrix-Vector Multiplication on GPU
Gao, H., & Qian, Z. (2012) · International Conference on Computer Science and Network Technology (ICCSNT) · doi:10.1109/iccsnt.2012.6526085 · Cited by 5
Thébault, L., & Petit, E. (2017) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2017.12.004 · Cited by 5
Approximate message passing based cooperative localization in WSN with AOA measurements
Gong, Y., Shengchu, W., & Zhang, L. (2018) · IEEE Wireless Communications and Networking Conference · doi:10.1109/wcnc.2018.8377230 · Cited by 5
“The POG-AMP localizer calls for sparse matrix-vector multiplications (MVM) [10], [11] as the most complex operation, and can be implemented in a distributed manner.”
BackgroundEfficient Performance Estimation and Work-Group Size Pruning for OpenCL Kernels on GPUs
Wang, X., Qian, X., Knoll, A., & Huang, K. (2020) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2019.2958343 · Cited by 5
“At first, performance autotuning research mainly focused on commonly used but computationally demanding algorithms, such as matrix multiplication [36], [37], stencil computation [38], fast Fourier 1090 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL.”
MethodSubotić, M., Manasijević, A., & Kupusinac, A. (2020) · Studies in Informatics and Control · doi:10.24846/v29i1y202008 · Cited by 5
“A dramatic change can be witnessed in computer architecture due to the multicore paradigm shift, as every electronic device from cell phones to supercomputers confronts parallelism of unprecedented scale (Williams et al., 2007).”
BackgroundEnterprise-Scale Search: Accelerating Inference for Sparse Extreme Multi-Label Ranking Trees
Etter, P. A., Zhong, K., Yu, H., Ying, L., & Dhillon, I. S. (2022) · International World Wide Web Conference (WWW) · doi:10.1145/3485447.3511973 · Cited by 5
“Other examples include work by [15] specifically targeting multi-core platforms, and [12], who develop an analytic model to better help predict optimal sparse Output Space: Y .”
BackgroundEfficiently Running SpMV on Multi-core DSPs for Banded Matrix
Bi, D., Li, S., Zhang, Y., Yang, X., & Dong, D. (2024) · Lecture notes in computer science · doi:10.1007/978-981-97-0808-6_12 · Cited by 5
Semi-supervised learning via sparse model
Wang, Y., Tang, S., Zheng, Y.-T., Zhang, Y., & Li, J. (2013) · Neurocomputing · doi:10.1016/j.neucom.2013.10.033 · Cited by 5
“The complexity of sparse model is a linear complexity of OððTkmsþTks2ÞnnÞ [10], and the complexity of sparse matrix multiplication is Oðsn2Þ5Oðmn2Þ.”
BackgroundInfluentialImplications of Memory-Efficiency on Sparse Matrix-Vector Multiplication
Jain, S., Pottathuparambil, R., & Sass, R. R. (2011) · Symposium on Application Accelerators in High-Performance Computing (SAAHPC) · doi:10.1109/saahpc.2011.24 · Cited by 5
“Although in absolute performance, the design is competitive with the current solutions described in [1], it is worth highlighting that we are using 2004 FPGA technology and our DDR2 controller is less than optimal.”
BackgroundMethodEfficient CSR-Based Sparse Matrix-Vector Multiplication on GPU
Gao, J., Qi, P., & He, G. (2016) · Mathematical Problems in Engineering · doi:10.1155/2016/4596943 · Cited by 5
“We use a total of 20 sparse matrices: 14 of them are from [35] and 6 of them are from theUniversity of Florida Sparse Matrix Collection [36].”
MethodA Principled Kernel Testbed for Hardware/Software Co-Design Research
Kaiser, A., Williams, S., 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/983482 · Cited by 5
Self-citationTask-based Conjugate-Gradient for multi-GPUs platforms
Agullo, E., Giraud, L., Guermouche, A., Nakov, S., & Roman, J. (2012) · HAL · Cited by 5
GPU computing architecture for irregular parallelism
Fung, W. W. L. (2015) · cIRcle (University of British Columbia) · doi:10.14288/1.0167110 · Cited by 5
An SSD-based eigensolver for spectral analysis on billion-node graphsPreprint
Zheng, D., Burns, R. C., Vogelstein, J. T., Priebe, C. E., & Szalay, A. S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.01421 · Cited by 5
“The current popular eigensolver packages such as ARPACK [15] and Anasazi [5] have state-of-art eigensolvers capable of computing a few eigenvalues with certain properties such as the eigenvalues of the largest or smallest magnitude.”
MethodSparse Convex Optimization on GPUs
Maggioni, M. (2016) · Figshare · Cited by 5
Exploiting Weight Redundancy in CNNs: Beyond Pruning and QuantizationPreprint
Wen, Y., & Gregg, D. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.11967 · Cited by 8
“The most widely-used of these formats is block sparse row (BSR) [26], which is similar to CSR but contains small dense blocks rather than indidual non-zeros.”
MethodOn the design of sparse hybrid linear solvers for modern parallel architectures
Nakov, S. (2015) · theses.fr (ABES) · doi:10.70675/9ea74bb0zcd35z4136zb61fz140e8e1ff3ec · Cited by 5
Bakhtiar, U., Namjoo, A., & Asgari, B. (2025) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1145/3725843.3756086 · Cited by 6
“Another approach is row-based parallelization [4, 75, 81], where all non-zeros from the same row are scheduled for the same PE.”
Heterogeneous Multi-core Processors: The Cell Broadband Engine
Hofstee, H. P. (2009) · Integrated circuits and systems · doi:10.1007/978-1-4419-0263-4_9 · Cited by 4
Millimeter-wave main memory-to-processor data bus
Guidotti, D., Chien, H., Fan, S., Chowdhury, A., Guo, T., & Chang, G. (2010) · International Conference on Electronic Packaging Technology (ICEPT) · doi:10.1109/icept.2010.5582788 · Cited by 4
“The observation that adding more DRAM memory DIMMs in a memory starved AMD system dramatically improves performance [1] suggests that adding memory hardware increases memory concurrency and directly impacts system performance.”
BackgroundMethodImplementing Sparse Linear Algebra Kernels on the Lucata Pathfinder-A Computer
Krawezik, G. P., Kuntz, S. K., & Kogge, P. M. (2020) · IEEE High Performance Extreme Computing Conference · doi:10.1109/hpec43674.2020.9286207 · Cited by 4
“On the one hand, SpMV being a core kernel in most linear algebra iterative solvers, many studies have tried to improve its performance on a variety of architectures and domain specific sparse matrix patterns [9], [10], [11].”
BackgroundSPAI Preconditioners for HPC Applications
Sawyer, W., Vanini, C., Fourestey, G., & Popescu, R. (2012) · PAMM · doi:10.1002/pamm.201210314 · Cited by 4
“The resulting GPU algorithm has been tested with the sparse matrix set used in studies of multi-core [6] and GPU [7] matrix-vector product performance.”
MethodMöller, M. (2013) · Computing · doi:10.1007/s00607-012-0276-y · Cited by 4
Efficient Parallel Reservoir Simulation Using Multicore Architectures
Khait, M. (2009) · SPE Reservoir Simulation Conference · doi:10.2118/119107-ms · Cited by 4
Using sampled information: is it enough for the sparse matrix–vector product locality optimization?
Pichel, J. C., Lorenzo, J. A., Rivera, F. F., Heras, D. B., & Pena, T. F. (2012) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.2949 · Cited by 4
Scalability study of molecular dynamics simulation on Godson-T many-core architecture
Liu, P., Tan, G., Kalia, R. K., Nakano, A., Vashishta, P. D., Fan, D., Zhang, H., & Song, F. (2012) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2012.07.007 · Cited by 4
“Thus we do not expect that this data structure could make great improvement as, to our best knowledge, it is still very difficult to efficiently optimize sparse matrix operations [27].”
BackgroundAnalyzing the execution of sparse matrix-vector product on the Finisterrae SMP-NUMA system
Pichel, J. C., Lorenzo, J. A., Heras, D. B., Cabaleiro, J. C., & Pena, T. F. (2010) · The Journal of Supercomputing · doi:10.1007/s11227-010-0392-4 · Cited by 4
A New Fill-in Strategy for IC Factorization Preconditioning Considering SIMD Instructions
Iwashita, T., Takemura, N., Ida, A., & Nakashima, H. (2015) · IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom.2015.610 · Cited by 4
“Therefore, it is important for high performance computing applications to efficiently utilize SIMD instructions [1], [2].”
BackgroundMethodAccelerating Unstructured Mesh Computational Fluid Dynamics on the NVidia Tesla GPU Architecture
Markall, G. R. (2011) · Cited by 4
Alzahrani, S., Ikbal, M. R., Mehmood, R., Fayez, M., & Katib, I. A. (2018) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-319-94180-6_28 · Cited by 4
A Fill Estimation Algorithm for Sparse Matrices and Tensors in Blocked Formats
Ahrens, W., Xu, H., & Schiefer, N. (2018) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2018.00064 · Cited by 4
A Novel Text Classification Method for Emergency Event Detection on Social Media
Liu, Y., Niu, J., Zhao, Q., Lv, J., & Ma, S. (2018) · IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI) · doi:10.1109/smartworld.2018.00192 · Cited by 4
“However they could be efficiently resolved in practice by using specialized machine learning libraries for sparse matrices and vectors computation [17].”
BackgroundMuro, R., Fujii, A., & Tanaka, T. (2019) · International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia) · doi:10.1145/3293320.3293332 · Cited by 4
“Various approaches have been suggested to reduce memory bandwidth requirement of SpMV: symmetry [1], index compression [2,3], cache blocking [4], row/column reordering [5], NUMA optimize [4], applied cache oblivious algorithm [6].”
MethodHybrid 2D/1D Blocking as Optimal Matrix-Matrix Multiplication
Gušev, M., Ristov, S., & Velkoski, G. (2013) · Advances in intelligent systems and computing · doi:10.1007/978-3-642-37169-1_2 · Cited by 4
Implementing modular adaptation of scientific software
Kang, P., Selvarasu, N. K., Ramakrishnan, N., Ribbens, C. J., Tafti, D. K., Cao, Y., & Srinidhi Varadarajan, A. (2012) · Journal of Computational Science · doi:10.1016/j.jocs.2012.01.007 · Cited by 4
“Therefore, tuning support to automatically optimize scientific codes over parameter search spaces is becoming more relevant [9,34].”
BackgroundExploring the Performance-Energy Tradeoffs in Sparse Matrix-Vector Multiplication
Karakasis, V., Goumas, G., & Koziris, N. (2011) · Cited by 4
Speeding Up the Evaluation of a Mathematical Model for VANETs Using OpenMP
García-Costa, C., Tomás-Gabarrón, J. B., Egea-López, E., & García-Haro, J. (2012) · Advances in intelligent systems and computing · doi:10.1007/978-3-642-34336-0_2 · Cited by 4
“In general, we find quite a lot of done wor k in the field of sparse matrix-vector multiplications using parallelization tec hniques [6], [7], [8].”
Dubois, J., Calvin, C., & Petiton, S. G. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-19328-6_7 · Cited by 4
“Concerning sparse matrices, the achieved performance in [19] varies from 2 to 5 GFlops on several matrices for a highly tuned matrix vector product.”
BackgroundEfficient Multicore Sparse Matrix-Vector Multiplication for FE Electromagnetics
Fernandez, D. M., Giannacopoulos, D. D., & Gross, W. J. (2009) · IEEE Transactions on Magnetics · doi:10.1109/tmag.2009.2012640 · Cited by 4
“This type of performance is in agreement with the results presented in [14].”
ResultAutomated Scratchpad Mapping and Allocation for Embedded Processors
Gao, Y. (2014) · Scholar Commons (University of South Carolina) · Cited by 4
Autotuning GPU-Accelerated QAP Solvers for Power and Performance
Chaparala, A., Novoa, C. M., & Qasem, A. (2015) · 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-css-icess.2015.121 · Cited by 4
“…parameters and performs multi-dimensional search to discover algorithmic variants that provide portable performance across different data sets • we include algorithmic choice in the search space; to our knowledge this is the first such effort in the context of GPUbased autotuning • we…”
The Impact of Voltage-Frequency Scaling for the Matrix-Vector Product on the IBM POWER8
Catalán, S., Malossi, A. C. I., Bekas, C., & Quintana–Ort́ı, E. S. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-43659-3_8 · Cited by 4
“, [5,16,22,23] and the references therein.”
Performance evaluation of sparse matrix-vector product (SpMV) computation on GPU architecture
Kasmi, N., Mahmoudi, S. A., Zbakh, M., & Manneback, P. (2014) · World Conference on Complex Systems · doi:10.1109/icocs.2014.7060964 · Cited by 4
“Williams [10] compares SpMV kernels on emerging multicore platforms.”
Background3D Waveform Oscilloscope Implemented on Coupled FPGA-GPU Embedded System
Hu, N., Zhou, X., Li, X., & Wang, C. (2018) · International Conference on Information Science and Control Engineering · doi:10.1109/icisce.2018.00010 · Cited by 4
Prioritizing Methods to Accelerate Probabilistic Model Checking of Discrete-Time Markov Models
Mohagheghi, M., Karimpour, J., & Isazadeh, A. (2019) · The Computer Journal · doi:10.1093/comjnl/bxz001 · Cited by 4
High Performance Computing Evaluation A methodology based on Scientific Application Requirements
Ferro, M., Mury, A. R., Manfroi, L. F., & Schlze, B. (2014) · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · doi:10.48550/arxiv.1412.1297 · Cited by 4
“Some evidence for the existence of the equivalence classes proposed by the Dwarfs can also be found in some numerical libraries such as The Fastest Fourier Transform in the West (FFTW) [7], a software library for computing discrete Fourier transforms (equivalent of Spectral Methods Dwarf class), the LAPACK/ScaLapack […”
MethodCooperative hierarchical resource management for efficient composition of parallel software
Asanović, K., & Pan, H. (2010) · Cited by 4
GPU Semiring Primitives for Sparse Neighborhood MethodsPreprint
Nolet, C., Gala, D., Raff, E., Eaton, J., Rees, B., Zedlewski, J., & Oates, T. (2021) · arXiv (Cornell University) · doi:10.13016/m2nwkv-ijt1 · Cited by 4
GPUs All Grown-Up: Fully Device-Driven SpMV Using GPU Work Graphs
Wildgrube, F., Ehrett, P., Trojahn, P., Membarth, R., Beckmann, B. M., Baumeister, D., & Chajdas, M. G. (2025) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/3695053.3731060 · Cited by 3
“…we employ the metric of “effective FLOPS” which uses only the number of floating-point operations necessary to perform the SpMV: Where denotes the number of non-zero elements of a given matrix and is the execution time of an SpMV, including preprocessing, performed with that matrix [16, 33, 42].”
Lodia: Towards Optimal Sparse Matrix-Vector Multiplication for Batched Fully Homomorphic Encryption
Yu, J., Chen, K., Fan, X., Chen, Y., Zhu, X., & Chen, W. (2025) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3719027.3765025 · Cited by 3
Using the VBARMS method in parallel computing
Carpentieri, B., Liao, J., Sosonkina, M., Bonfiglioli, A., & Baars, S. (2016) · Parallel Computing · doi:10.1016/j.parco.2016.01.005 · Cited by 3
“…the corresponding matrix entries may form a small dense block and optimized codes can be used for dense factorizations in the construction of the preconditioner and dense matrix-vector products in the sparse matrix-vector product operation for better performance, see e.g. [8, 11, 19, 23, 24].”
CAD models from medical images using LAR
Paoluzzi, A., DiCarlo, A., Furiani, F., & Jiřík, M. (2016) · Computer-Aided Design and Applications · doi:10.1080/16864360.2016.1168216 · Cited by 3
“Compressed Sparse Row (CSR) matrix: (a) general case with storage in 3 arrays (image from [49]); (b) special case: LAR of dmeshes, with binary values and same number k of non-zeros in each row, with k = d+ 1 (regular simplicial d-complexes) or k = 2d”
BackgroundSparse Matrix-Based HPC Tomography
Marchesini, S., Trivedi, A. G., Enfedaque, P., Perciano, T., & Parkinson, D. (2020) · eScholarship (California Digital Library) · Cited by 3
A Simple Parallel Algorithm for Biconnected Components in Sparse Graphs
Chaitanya, M., & Kothapalli, K. (2015) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2015.31 · Cited by 3
A Fast Sparse Block Circulant Matrix Vector Product
Romero, E., Tomás, A. E., Soriano, A., & Blanquer, I. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-09873-9_46 · Cited by 3
“As an example, results testing the matrix-vector (SpMV) product on several multi-core processors in [23] show disparate peak performance between 3% and 40%.”
On Shared-Memory Parallelization of a Sparse Matrix Scaling Algorithm
Çatalyürek, Ü. V., Kaya, K., & Uçar, B. (2012) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2012.43 · Cited by 3
“Some other studies [11], [10], [12] apply architecture-aware techniques to greatly improve the performance of parallelized algorithms.”
Applicability of Pattern-based sparse matrix representation for real applications
Belgin, M., Back, G., & Ribbens, C. J. (2010) · Procedia Computer Science · doi:10.1016/j.procs.2010.04.023 · Cited by 3
“Other recent efforts to understand and improve SMVM performance include [13], [14] and [15].”
BackgroundThe Importance of Dynamic Load Balancing among OpenMP Thread Teams for Irregular Workloads
Xiao, X., Hirasawa, S., Takizawa, H., & Kobayashi, H. (2016) · International Symposium on Computing and Networking · doi:10.1109/candar.2016.0097 · Cited by 3
“There are several recent studies focusing on optimizing the workload balance of the hotspots so as to improve the overall performance of an application [3][4][5].”
BackgroundEndo, T. (2019) · International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia) · doi:10.1145/3368474.3368477 · Cited by 3
“The technique has been widely used to accelerate dense linear algebra[2–4], sparse linear algebra[5, 6], stencil computation[7–9], graph algorithms[10, 11] and so on.”
MethodZubair, M., Warner, J. E., & Wagner, D. (2019) · Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems (ScalA) · doi:10.1109/scala49573.2019.00007 · Cited by 3
Model-Based Hardware-Software Codesign of ECT Digital Processing Unit
Allam, A., & Deabes, W. A. (2021) · Modelling and Simulation in Engineering · doi:10.1155/2021/4757464 · Cited by 3
“The inner-product as well as the matrix-vector multiplication possesses inherent parallelism that makes it to be executed in parallel over general-purpose graphics processing units [28] and multicore processors [29].”
BackgroundQuantifiability: a concurrent correctness condition modeled in vector space
Cook, V., Peterson, C., Painter, Z., & Dechev, D. (2022) · Computing · doi:10.1007/s00607-022-01092-3 · Cited by 3
Compiler Optimization for Irregular Memory Access Patterns in PGAS Programs
Rolinger, T. B., Krieger, C. D., & Sussman, A. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-31445-2_1 · Cited by 3
Intel vs AMD: Matrix multiplication performance
Anchev, N., Gušev, M., Ristov, S., & Atanasovski, B. (2013) · International Convention on Information and Communication Technology, Electronics and Microelectronics · Cited by 3
Implementation and performance analysis of parallel conjugate gradient on the Cell Broadband Engine
Sibai, F. N., & Kidwai, H. K. (2010) · IBM Journal of Research and Development · doi:10.1147/jrd.2010.2071191 · Cited by 3
Park, H., & Rho, S. (2012) · The Journal of Society for e-Business Studies · doi:10.7838/jsebs.2012.17.4.069 · Cited by 3
B-SCT: Improve SpMV processing on SIMD architectures
Wang, Y., Wang, D., & Zhou, X. (2015) · IEICE Electronics Express · doi:10.1587/elex.12.20150170 · Cited by 3
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.