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 101–200 of 810
Non-affine Extensions to Polyhedral Code Generation
Venkat, A., Shantharam, M., Hall, M. W., & Strout, M. M. (2014) · Proceedings of the CGO/Proceedings of the ... CGO · doi:10.1145/2544137.2544141 · Cited by 66
“employ a large number of optimizations on SpMV targeting multi-core and many-core architectures [36].”
MethodAlgorithmic performance studies on graphics processing units
Schenk, O., Christen, M., & Burkhart, H. (2008) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2008.05.008 · Cited by 64
Merge-based parallel sparse matrix-vector multiplication
Merrill, D., & Garland, M. (2016) · IEEE International Conference on High Performance Computing, Data, and Analytics · doi:10.5555/3014904.3014982 · Cited by 62
Thread motion: fine-grained power management for multi-core systems
Rangan, K. K., Wei, G.-Y., & Brooks, D. M. (2009) · ACM SIGARCH Computer Architecture News · doi:10.1145/1555815.1555793 · Cited by 61
Pattern-based sparse matrix representation for memory-efficient SMVM kernels
Belgin, M., Back, G., & Ribbens, C. J. (2009) · International Conference on Supercomputing · doi:10.1145/1542275.1542294 · Cited by 68
“As has been observed by others [34], such matrices benefit from superlinear speedup under CSR.”
MethodResultInfluentialComposing parallel software efficiently with lithe
Pan, H., Hindman, B., & Asanović, K. (2010) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/1806596.1806639 · Cited by 60
“Unpredictable multip lexing also leads to cache interference between threads, hinderin g optimizations such as prefetching [18] and cache-blocking [43] .”
BackgroundIncomplete-LU and Cholesky Preconditioned Iterative Methods Using CUSPARSE and CUBLAS
Naumov, M. (2012) · Cited by 60
A hybrid computing method of SpMV on CPU–GPU heterogeneous computing systems
Yang, W., Li, K., & Li, K. (2017) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2016.12.023 · Cited by 60
Grewe, D., & Lokhmotov, A. (2011) · doi:10.1145/1964179.1964196 · Cited by 59
“Sparse linear algebra is well researched [7, 8].”
Optimizing and auto-tuning scale-free sparse matrix-vector multiplication on Intel Xeon Phi
Tang, W. T., Zhao, R., Lu, M., Liang, Y. E., Huynh, H. P., Li, X., & Goh, R. S. M. (2015) · Proceedings of the CGO/Proceedings of the ... CGO · doi:10.1109/cgo.2015.7054194 · Cited by 59
“SpMV computation is a performance bottleneck for many of these algorithms [10, 20, 21].”
BackgroundGlobally homogeneous, locally adaptive sparse matrix-vector multiplication on the GPU
Steinberger, M., Zayer, R., & Seidel, H. (2017) · International Conference on Supercomputing · doi:10.1145/3079079.3079086 · Cited by 58
yaSpMV: yet another SpMV framework on GPUs
Yan, S., Li, C., Zhang, Y., & Zhou, H. (2014) · ACM SIGPLAN Notices · doi:10.1145/2692916.2555255 · Cited by 58
Multi-core acceleration of chemical kinetics for simulation and prediction
Linford, J. C., Michalakes, J. G., Vachharajani, M., & Sandu, A. (2009) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/1654059.1654067 · Cited by 58
CSX: an extended compression format for spmv on shared memory systems
Kourtis, K., Karakasis, V., Goumas, G., & Koziris, N. (2011) · ACM SIGPLAN Notices · doi:10.1145/2038037.1941587 · Cited by 57
A high-performance parallel algorithm for nonnegative matrix factorization
Kannan, R., Ballard, G., & Park, H. (2016) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/2851141.2851152 · Cited by 63
“[25].”
Optimizing Sparse Matrix-Vector Multiplication for Large-Scale Data Analytics
Buono, D., Petrini, F., Checconi, F., Liu, X., Que, X., Long, C., & Tuan, T.-C. (2016) · International Conference on Supercomputing · doi:10.1145/2925426.2926278 · Cited by 57
“The HPC matrices we use are selected from the University of Florida Sparse Matrix Collection [11], and were used in previous studies on SpMV [22, 30].”
MethodOptimization of a lattice Boltzmann computation on state-of-the-art multicore platforms
Williams, S., Carter, J. T., Oliker, L., Shalf, J. M., & Yelick, K. (2009) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2009.04.002 · Cited by 61
“If the request for a cache line appears on one FSB, and it is not in either of the caches on the other FSB, then no coherency traffic needs to be generated.”
BackgroundInfluentialSelf-citationKronbichler, M., Schoeder, S., Müller, C., & Wall, W. A. (2015) · International Journal for Numerical Methods in Engineering · doi:10.1002/nme.5137 · Cited by 58
“For many modern iterative solvers, memory bandwidth is the limiting factor, in particular for sparse matrix-vector products and substitutions [9].”
BackgroundMerge-based sparse matrix-vector multiplication (SpMV) using the CSR storage format
Merrill, D., & Garland, M. (2016) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/2851141.2851190 · Cited by 56
“Williams et al. survey a wide range of optimization techniques for multicore CPUs [5], and Filippone et al. survey more than sixty GPU-specific variations [2].”
MethodAn approach for code generation in the Sparse Polyhedral Framework
Strout, M. M., LaMielle, A., Carter, L., Jeanne Ferrante, Y., Kreaseck, B., & Olschanowsky, C. M. (2016) · Parallel Computing · doi:10.1016/j.parco.2016.02.004 · Cited by 55
“As such, techniques for improving its performance have been studied in the context of multicore architectures [78, 79], GPUs [80, 81], and Xeon Phi [82, 83].”
MethodSparse matrix-matrix multiplication on modern architectures
Matam, K. K., Indarapu, S. B., & Kothapalli, K. (2012) · IEEE International Conference on High Performance Computing, Data, and Analytics · doi:10.1109/hipc.2012.6507483 · Cited by 54
“Section V describes our GPU algorithm for csrmm along with experimental results.”
MethodPHI: Architectural Support for Synchronization- and Bandwidth-Efficient Commutative Scatter Updates
Mukkara, A., Beckmann, N., & Sánchez, D. (2019) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1145/3352460.3358254 · Cited by 54
“Though we adopt graph analytics terminology in this paper, we use the term update batching instead of the more common Propagation Blocking to avoid confusion with graph blocking/tiling, a different optimization [55, 60] (Sec.”
MethodOptimization of Sparse Matrix-Vector Multiplication with Variant CSR on GPUs
Feng, X., Jin, H., Zheng, R., Hu, K., Zeng, J., & Shao, Z. (2011) · IEEE International Conference on Parallel and Distributed Systems (ICPADS) · doi:10.1109/icpads.2011.91 · Cited by 53
“SpMV is generally reported to sustain low fractions of peak processor performance [1], mainly due to the fact that it is a memorybound application.”
BackgroundAccelerating sparse matrix-vector multiplication on GPUs using bit-representation-optimized schemes
Tang, W. T., Tan, W. J., Ray, R., Wong, Y. W., Chen, W., Kuo, S.-H., Goh, R. S. M., Turner, S. J., & Wong, W. (2013) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/2503210.2503234 · Cited by 53
“Different optimization strategies and data formats such as Compressed Sparse Row (CSR) and ELLPACK-ITPACK (ELLPACK) have been proposed by researchers which are suitable for different kinds of matrix structure and different hardware architectures [27, 15, 8].”
BackgroundMethodTowards Efficient SpMV on Sunway Manycore Architectures
Liu, C., Xie, B., Liu, X., Xue, W., Yang, H., & Liu, X. (2018) · International Conference on Supercomputing · doi:10.1145/3205289.3205313 · Cited by 53
“Plenty of work has been published on SpMV optimization from diverse perspectives [6, 13, 15, 19, 28].”
BackgroundThe Eigenvalues Slicing Library (EVSL): Algorithms, Implementation, and Software
Li, R., Xi, Y., Erlandson, L., & Saad, Y. (2019) · SIAM Journal on Scientific Computing · doi:10.1137/18m1170935 · Cited by 53
Different approaches in parallelization of the artificial bee colony algorithm
Subotić, M., Tuba, M., & Stanarevic, N. (2011) · Cited by 52
Optimization of sparse matrix–vector multiplication using reordering techniques on GPUs
Pichel, J. C., Rivera, F. F., Fernández, M., & Rodríguez, A. (2011) · Microprocessors and Microsystems · doi:10.1016/j.micpro.2011.05.005 · Cited by 51
Brainy: effective selection of data structures
Jung, C., Rus, S., Railing, B. P., Clark, N., & Pande, S. (2011) · ACM SIGPLAN Notices · doi:10.1145/1993316.1993509 · Cited by 51
An efficient parallel solution for Caputo fractional reaction–diffusion equation
Gong, C., Bao, W., Tang, G., Yang, B., & Liu, J. (2014) · The Journal of Supercomputing · doi:10.1007/s11227-014-1123-z · Cited by 50
“The most common data structure used to store a sparse matrix for sparse matrix vector multiplication computations is compressed sparse row (CSR) format [33] shown in (12).”
BackgroundFinite-Element Sparse Matrix Vector Multiplication on Graphic Processing Units
Dehnavi, M. M., Fernandez, D. M., & Giannacopoulos, D. D. (2010) · IEEE Transactions on Magnetics · doi:10.1109/tmag.2010.2043511 · Cited by 50
“We have investigated the performance of our technique on various sparse matrices from [7] with different average nonzeros per row (Table I).”
MethodAccelerating Sparse Matrix Vector Multiplication in Iterative Methods Using GPU
Matam, K. K., & Kothapalli, K. (2011) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2011.82 · Cited by 50
“However, this comes at the expense of reinterpreting applications in a highly multithreaded manner.”
BackgroundInfluentialAuto-Tuning CUDA Parameters for Sparse Matrix-Vector Multiplication on GPUs
Guo, P., & Wang, L. (2010) · International Conference on Computational and Information Sciences · doi:10.1109/iccis.2010.285 · Cited by 62
“Our experiments are evaluated on 14 unstructured sparse matrices [3], as shown in Table 1, by using two NVIDIA GPUs: GeForce 9500 GTX and GeForce GTX 295, where the compute capability for 9500 GTX is v1.”
MethodSqueezeFlow: A Sparse CNN Accelerator Exploiting Concise Convolution Rules
Li, J., Jiang, S., Gong, S., Wu, J., Yan, J., Yan, G., & Li, X. (2019) · IEEE Transactions on Computers · doi:10.1109/tc.2019.2924215 · Cited by 51
“Prior matrix computation optimizations [48], [49], [50] only optimize for a”
BackgroundDeepDive: A Data Management System for Automatic Knowledge Base Construction
Zhang, C., Konda, P., & Mallory, E. K. (2015) · Cited by 58
Analysis and performance estimation of the Conjugate Gradient method on multiple GPUs
Verschoor, M., & Jalba, A. C. (2012) · Parallel Computing · doi:10.1016/j.parco.2012.07.002 · Cited by 52
“The Conjugate Gradient (CG) method [20] is a widely-used iterative approach for solving linear systems.”
MethodParallel algorithms for solving linear systems with sparse triangular matrices
Mayer, J. (2009) · Computing · doi:10.1007/s00607-009-0066-3 · Cited by 48
“In fact, the situation for sparse matrix vector multiplication (which requires the same type of operations as a triangular solve) is quite similar and this has been investigated extensively, see [ 19 ].”
ResultZhu, Q., Luo, H., Yang, C., Ding, M., Yin, W., & Yuan, X. (2021) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/3458817.3476158 · Cited by 47
“For the SpMV kernel, because of the concurrent nature, research focus is usually on designing different storage formats for the sparse matrix, such as CSR [14], ELLPACK [23], SELL-C-Sigma [21] etc, and enhancing the data locality by techniques such as thread blocking [46], loop optimization [40], parameter autotuning…”
MethodScalable High-Quality Hypergraph Partitioning
Gottesbüren, L., Heuer, T., Maas, N., Sanders, P., & Schlag, S. (2023) · ACM Transactions on Algorithms · doi:10.1145/3626527 · Cited by 47
Lu, Y., & Liu, W. (2023) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/3581784.3607051 · Cited by 54
“Wealsolist21representativematri-ceswidelytestedinexistingSpMVwork[27,64,65,73,76,95]in Table2toanalyzetheperformanceofourDASPmoredeeply.”
An Extended Compression Format for the Optimization of Sparse Matrix-Vector Multiplication
Karakasis, V., Gkountouvas, T., Kourtis, K., Goumas, G., & Koziris, N. (2012) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2012.290 · Cited by 47
“Index Terms—Sparse Matrix-Vector Multiplication, multicore optimizations, data compression Ç”
BackgroundA survey on hardware‐aware and heterogeneous computing on multicore processors and accelerators
Buchty, R., Heuveline, V., Karl, W., & Weiß, J.-P. (2011) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.1904 · Cited by 47
“Impressive work has been carried out by comparing basic application kernels on a multitude of multicore platforms [8–10].”
Background(2008) · Cited by 47
Self-citationQR Factorization for the Cell Broadband Engine
Jakub Kurzak, A., & Dongarra, J. J. (2009) · Scientific Programming · doi:10.1155/2009/239720 · Cited by 46
Viswanath, A., Báca, E. E. S., & Farid, A. M. (2014) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2013.2293340 · Cited by 46
“In such an instance, sparse matrix methods can be applied to take advantage of the sparsity of the knowledge bases and constraint matrices [51].”
MethodAutomatic tuning of the sparse matrix vector product on GPUs based on the ELLR-T approach
Vázquez, F., Fernández, J., & Garzón, E. M. (2011) · Parallel Computing · doi:10.1016/j.parco.2011.08.003 · Cited by 45
“Despite these drawbacks, several optimizations have made possible to improve the performance of sparse computation on current processors [4,20].”
BackgroundGPU based sparse grid technique for solving multidimensional options pricing PDEs
Gaikwad, A., & Toke, I. M. (2009) · High Performance Computational Finance · doi:10.1145/1645413.1645419 · Cited by 45
Resource-Aware Task Scheduling
Tillenius, M., Larsson, E., Badia, R. M., & Martorell, X. (2015) · ACM Transactions on Embedded Computing Systems · doi:10.1145/2638554 · Cited by 45
“Another bandwidth limited application, sparse matrix-vector multiplication, is studied in [Williams et al. 2009].”
BackgroundMPI-FAUN: An MPI-Based Framework for Alternating-Updating Nonnegative Matrix Factorization
Kannan, R., Ballard, G., & Park, H. (2017) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2017.2767592 · Cited by 52
Elafrou, A., Goumas, G., & Koziris, N. (2017) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2017.38 · Cited by 45
Brainy: effective selection of data structures
Jung, C., Rus, S., Railing, B. P., Clark, N., & Pande, S. (2011) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/1993498.1993509 · Cited by 45
“The instrumentation records traces of various runtime characteristics including underlying architecture-speci.c events.”
BackgroundExploiting compression opportunities to improve SpMxV performance on shared memory systems
Kourtis, K., Goumas, G., & Koziris, N. (2010) · ACM Transactions on Architecture and Code Optimization · doi:10.1145/1880037.1880041 · Cited by 44
“For CSR, coarse-grained row partitioning is usually applied [Williams et al. 2007] where different blocks of rows are assigned to different threads (see Figure 2).”
MethodKamath, A. G., Elango, P., Mceowen, S., Yu, Y., Carson, J. M., Mesbahi, M., & Acikmese, B. A. (2023) · AIAA SciTech Forum · doi:10.2514/6.2023-2003 · Cited by 44
Implementing Blocked Sparse Matrix-Vector Multiplication on NVIDIA GPUs
Monakov, A., & Avetisyan, A. I. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03138-0_32 · Cited by 44
“Most test matrices are those referenced in [5] and [6].”
BackgroundMethodReachability Analysis of Large Linear Systems With Uncertain Inputs in the Krylov Subspace
Althoff, M. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2906432 · Cited by 50
Node aware sparse matrix–vector multiplication
Bienz, A., Gropp, W., & Olson, L. N. (2019) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2019.03.016 · Cited by 44
“Machine topology plays an important role in the cost of communication [32].”
BackgroundThe sparse matrix vector product on GPUs
Heras‐Vázquez, F. J. L., Garzón, E. M., Martínez, J. A., & Fernández, J. (2011) · Cited by 43
Autoscheduling for sparse tensor algebra with an asymptotic cost model
Ahrens, W., Kjølstad, F., & Amarasinghe, S. P. (2022) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3519939.3523442 · Cited by 48
“Runtime autotuning techniques subsequently enjoyed widespread adoption, allowing software developers to effectively specialize to new sparsity patterns [13, 41] and architectures [20, 62].”
Optimizing Sparse Matrix Operations on GPUs Using Merge Path
Dalton, S., Baxter, S., Merrill, D., Olson, L. N., & Garland, M. (2015) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2015.98 · Cited by 41
“…40 0 0 0 50 0 60 0 0 ⎤ ⎥⎥⎦ and B = ⎡ ⎢⎢⎣ 1 0 0 0 0 2 0 3 4 5 0 0 0 6 0 7 ⎤ ⎥⎥⎦ , with tuple form given by A = ⎡ ⎢⎢⎢⎢⎢⎢⎣ (0, 0, 10) (1, 1, 20) (1, 2, 30) (1, 3, 40) (2, 3, 50) (3, 1, 60) ⎤ ⎥⎥⎥⎥⎥⎥⎦ and B = ⎡ ⎢⎢⎢⎢⎢⎢⎢⎢⎣ (0, 0, 1) (1, 1, 2) (1, 3, 3) (2, 0, 4) (2, 1, 5) (3, 1, 6) (3, 3, 7) ⎤ ⎥⎥⎥⎥⎥⎥⎥⎥⎦ .”
A scalable eigensolver for large scale-free graphs using 2D graph partitioning
Yoo, A., Baker, A. H., Pearce, R., & Henson, V. E. (2011) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/2063384.2063469 · Cited by 41
“While most work is concerned with sparse matrices from PDEs [55, 66], dense matrices have been frequently addressed as well [27].”
BackgroundDesign and Implementation of Adaptive SpMV Library for Multicore and Many-Core Architecture
Tan, G., Liu, J., & Li, J. (2018) · ACM Transactions on Mathematical Software · doi:10.1145/3218823 · Cited by 45
“Other SpMV libraries, such as Kourtis et al. (2011), Williams et al. (2009), Vuduc et al. (2005), Yang et al. (2011), Choi et al. (2010), Su and Keutzer (2012), Byun et al. (2012), and Liu (2015), can be easily included in the back-end warehouse.”
BackgroundMethodInfluentialA Comprehensive Methodology to Optimize FPGA Designs via the Roofline Model
Siracusa, M., Sozzo, E. D., Rabozzi, M., Tucci, L. D., Williams, S., Sciuto, D., & Santambrogio, M. D. (2021) · IEEE Transactions on Computers · doi:10.1109/tc.2021.3111761 · Cited by 41
Self-citationKourtis, K., Goumas, G., & Koziris, N. (2008) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2008.62 · Cited by 41
“scheme is usually applied [11], where different blocks of rows are assigned to different threads (see Fig.”
BackgroundMethodHou, K., Feng, W.-C., & Che, S. (2017) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2017.155 · Cited by 40
“…SpMV on the modern accelerators (e.g., multi-core CPUs and GPU), or finding the most preferable storage formats to facilitate the SpMV. Williams et al. [34] examine a set of optimization meth-ods of SpMV kernels on the modern processors including homogeneous and heterogeneous parallel platforms.”
BackgroundBader, M., Böck, C., Schwaiger, J., & Vigh, C. (2010) · SIAM Journal on Scientific Computing · doi:10.1137/080728871 · Cited by 39
Extracting ultra-scale Lattice Boltzmann performance via hierarchical and distributed auto-tuning
Williams, S., Oliker, L., Carter, J. T., & Shalf, J. M. (2011) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/2063384.2063458 · Cited by 39
“…exploration of alternate data structures, optimizations for efficient shared memory parallelism (threading, data replication, data synchronization), and exploration of algorithmic parameters (particles per box in FMM, steps in communication-avoiding Krylov subspace methods) [4, 15, 18, 27, 35].”
BackgroundSelf-citationMining tree-structured data on multicore systems
Tatikonda, S., & Parthasarathy, S. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687706 · Cited by 42
Sparse Matrix Multiplication On An Associative Processor
Yavits, L., Morad, A., & Ginosar, R. (2014) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2014.2370055 · Cited by 39
“However, the progress in computer industry and semiconductor technology in recent years opens the door for reconsidering the APs: The rise of big data pushes the computational re- quirements to levels never seen before.”
BackgroundParallel symmetric sparse matrix–vector product on scalar multi-core CPUs
Krotkiewski, M., & Dąbrowski, M. (2010) · Parallel Computing · doi:10.1016/j.parco.2010.02.003 · Cited by 39
Perfomance Models for Blocked Sparse Matrix-Vector Multiplication Kernels
Karakasis, V., Goumas, G., & Koziris, N. (2009) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2009.21 · Cited by 39
“configurations [5], [14], [19], which are mainly due to the memory-intensive nature of the SpMV algorithm.”
BackgroundA Row Decomposition-based Approach for Sparse Matrix Multiplication on GPUs
Pang, M., Fei, X., Qu, P., Zhang, Y., & Li, Z. (2024) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/3627535.3638470 · Cited by 38
Optimizing Large-scale Graph Analysis on Multithreaded, Multicore Platforms
Cong, G., & Makarychev, K. (2012) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2012.46 · Cited by 38
“, see [28]) hinted on Niagara2 (as necessary hardware events to compute utilization are not reported) that memory latency may not be fully masked for irregular workloads such as sparse matrix multiplication.”
BackgroundResistive GP-SIMD Processing-In-Memory
Morad, A., Yavits, L., Kvatinsky, S., & Ginosar, R. (2016) · ACM Transactions on Architecture and Code Optimization · doi:10.1145/2845084 · Cited by 38
Algorithm-Directed Data Placement in Explicitly Managed Non-Volatile Memory
Wu, P., Li, D., Chen, Z., Vetter, J. S., & Mittal, S. (2016) · ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC) · doi:10.1145/2907294.2907321 · Cited by 38
“Hence, many research efforts have focused on using numerical algorithm knowledge to address the problems of fault tolerance [14, 18, 9], performance optimization [23, 38], and energy efficiency [20, 17].”
BackgroundDeep Multilevel Graph PartitioningPreprint
Gottesbüren, L., Heuer, T., Sanders, P., Schulz, C., & Seemaier, D. (2021) · arXiv (Cornell University) · doi:10.4230/lipics.esa.2021.48 · Cited by 38
An object‐oriented bulk synchronous parallel library for multicore programming
Yzelman, A.-J. N., & Bisseling, R. H. (2011) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.1843 · Cited by 37
“The main cause is that the BSP benchmark measures process speed according to dense operations; sparse operations such as the SpMV multiply are known to perform at a fraction of peak performance, as a result of inefficient cache use [18–20].”
BackgroundNeural reputation models learned from passive DNS data
Lison, P., & Mavroeidis, V. (2017) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata.2017.8258361 · Cited by 37
“To optimise these matrix operations (and limit the memory usage), we represent the matrix R using a sparse matrix format (compressed sparse row), and rely on high-performance matrix-matrix and matrix-vector multiplications (Williams et al., 2009).”
MethodOverhead-Conscious Format Selection for SpMV-Based Applications
Zhao, Y., Zhou, W., Shen, X., & Yiu, G. (2018) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2018.00104 · Cited by 37
“performance tuning (auto-tuning) systems [9], [10], [12], [13], designing new sparse formats [6], [7], [11], and hand-tuning input- or architecture-related features [11], [30], [31].”
BackgroundA High Performance Sparse Tensor Algebra Compiler in MLIR
Tian, R., Guo, L., Li, J., Ren, B., & Kestor, G. (2021) · IEEE/ACM Workshop on the LLVM Compiler Infrastructure in HPC (LLVM-HPC) · doi:10.1109/llvmhpc54804.2021.00009 · Cited by 37
Merge-based sparse matrix-vector multiplication (SpMV) using the CSR storage format
Merrill, D., & Garland, M. (2016) · ACM SIGPLAN Notices · doi:10.1145/3016078.2851190 · Cited by 37
FPGA and GPU implementation of large scale SpMV
Shan, Y., Wu, T., Wang, Y., Wang, B., Wang, Z., Xu, N., & Yang, H. (2010) · doi:10.1109/sasp.2010.5521144 · Cited by 37
“As the data scales, it brings many challenges to the storage and computation of the SpMV for large scale applications.”
Pattern-driven parallel I/O tuning
Behzad, B., Byna, S., Prabhat, & Snir, M. (2015) · IEEE/ACM International Parallel Data Systems Workshop (PDSW) · doi:10.1145/2834976.2834977 · Cited by 37
“While auto-tuning has been extensively studied in optimizing computational algorithms [24, 10, 14, 23, 26, 8, 25], applying the same techniques to parallel I/O tuning is nontrivial.”
BackgroundGuo, P., Huang, H., Chen, Q., Wang, L., Lee, E., & Chen, P. (2011) · TeraGrid Conference · doi:10.1145/2016741.2016744 · Cited by 39
“This paper presents an innovative performance-model driven approach for partitioning sparse matrix into appropriate formats, and auto-tuning con.gurations of CUDA kernels to improve the performance of SpMV on GPUs.”
BackgroundA floating-point accumulator for FPGA-based high performance computing applications
Sun, S. M., & Zambreno, J. (2009) · International Conference on Field-Programmable Technology (FPT) · doi:10.1109/fpt.2009.5377624 · Cited by 36
“The aforementioned SMVM operation calculates Y = AX , where yi = ∑n j=1 aijxj must be computed efficiently.”
BackgroundInfluentialCan search algorithms save large-scale automatic performance tuning?
Balaprakash, P., Wild, S. M., & Hovland, P. (2011) · Procedia Computer Science · doi:10.1016/j.procs.2011.04.234 · Cited by 36
“Examples include application-specific autotuners such as lattice Boltzmann computations [1], stencil computations [2], and matrix multiplication kernels [3, 4].”
MethodSMAT: an input adaptive auto-tuner for sparse matrix-vector multiplication
Li, J., Tan, G., Chen, M., & Sun, N. (2013) · ACM SIGPLAN Notices · doi:10.1145/2499370.2462181 · Cited by 36
Optimising Sparse Matrix Vector multiplication for large scale FEM problems on FPGA
Grigoras, P., Burovskiy, P., Luk, W. W., & Sherwin, S. J. (2016) · International Conference on Field Programmable Logic and Applications (FPL) · doi:10.1109/fpl.2016.7577352 · Cited by 35
“Typical challenges associated with the SpMV kernel are related to the indirect memory access pattern which leads to poor resource utilisation and compute efficiency on modern architectures [2], [3].”
BackgroundPerformance Optimization of the HPCG Benchmark on the Sunway TaihuLight Supercomputer
Ao, Y., Yang, C., Liu, F., Yin, W., Jiang, L., & Sun, Q. (2018) · ACM Transactions on Architecture and Code Optimization · doi:10.1145/3182177 · Cited by 36
“The original sparse matrix storage scheme used in HPCG greatly resembles the popular compressed sparse row (CSR) format [36], in which only the nonzero values and their corresponding column indices are stored row by row with an additional array keeping the number of nonzeros of each row.”
MethodParSy: Inspection and Transformation of Sparse Matrix Computations for Parallelism
Cheshmi, K., Kamil, S. A., Strout, M. M., & Dehnavi, M. M. (2018) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc.2018.00065 · Cited by 44
“Several libraries have also optimized specific sparse kernels such as triangular solve [31], [38], [57], [55], [53] and sparse matrix-vector multiply [58], [26], [37].”
BackgroundGenerating piecewise-regular code from irregular structures
Augustine, T., Sarma, J., Pouchet, L.-N., & Rodríguez, G. (2019) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3314221.3314615 · Cited by 35
“For example, Vuduc [39] presented an automated system for generating efficient implementations of SpMV on CPUs, while Williams et al. [40] moved toward multi-core platforms with the implementation of parallel SpMV kernels.”
MethodMaggioni, M., & Berger-Wolf, T. Y. (2013) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2013.10 · Cited by 34
“Moreover, we introduce a loop unrolling heuristic that optimizes the SpMV performance by selecting the best unrolling factor based on the warp workload.”
MethodStochastic descriptors in an SIR epidemic model for heterogeneous individuals in small networks
López‐García, M. (2015) · Mathematical Biosciences · doi:10.1016/j.mbs.2015.10.010 · Cited by 39
Parallelized Multiple Swarm Artificial Bee Colony Algorithm (MS-ABC) for Global Optimization
Subotić, M., & Tuba, M. (2014) · Studies in Informatics and Control · doi:10.24846/v23i1y201412 · Cited by 34
Optimizing Sparse Matrix–Vector Multiplications on an ARMv8-based Many-Core Architecture
Chen, D., Fang, J., Chen, S., Xu, C., & Wang, Z. (2019) · International Journal of Parallel Programming · doi:10.1007/s10766-018-00625-8 · Cited by 34
Lee, S., & Eigenmann, R. (2008) · International Conference on Supercomputing · doi:10.1145/1375527.1375558 · Cited by 34
“In this paper, we propose adaptive runtime tuning mechanisms to improve the parallel performance on distributed memory systems.”
MethodOptimizing SpMV for Diagonal Sparse Matrices on GPU
Sun, X., Zhang, Y., Wang, T., Zhang, X., Yuan, L., & Rao, L. (2011) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2011.53 · Cited by 34
“Samuel Williams [17] sums up all those optimization methods on the emerging multi-core platforms.”
A Comparative Study of Blocking Storage Methods for Sparse Matrices on Multicore Architectures
Karakasis, V., Goumas, G., & Koziris, N. (2009) · doi:10.1109/cse.2009.223 · Cited by 34
“Although there exist other potential performance problems in this kernel, such as indirect references, irregular accesses, and loop overheads, the bottleneck in the memory subsystem is categorized as the most important SpMV performance problem in both single- and multithreaded configurations [4], [7], [16].”
BackgroundHierarchical Diagonal Blocking and Precision Reduction Applied to Combinatorial Multigrid
Blelloch, G. E., Koutis, I., Miller, G. L., & Tangwongsan, K. (2010) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc.2010.29 · Cited by 33
Adaptive Optimization of Sparse Matrix-Vector Multiplication on Emerging Many-Core Architectures
Chen, S., Fang, J., Chen, D., Xu, C., & Wang, Z. (2018) · 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/smartcity/dss.2018.00116 · Cited by 33
“SpMV has been extensively studied on various platforms over the past few decades [24, 30, 45].”
BackgroundMethodInfluentialOptimizing sparse tensor times matrix on GPUs
Ma, Y., Li, J., Wu, X., Yan, C. C., Sun, J., & Vuduc, R. W. (2018) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2018.07.018 · Cited by 33
Self-citation
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.