The DOI matches its Crossref record; 21 of the 23 references it cites were found in a registry or an index.
Optimization of sparse matrix-vector multiplication on emerging multicore platforms
Open accessAbstract
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
Williams, S., Waterman, A., & Patterson, D. A. (2009) · Communications of the ACM · doi:10.1145/1498765.1498785 · Cited by 2,798
Self-citationImplementing sparse matrix-vector multiplication on throughput-oriented processors
Bell, N., & Garland, M. (2009) · Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis · doi:10.1145/1654059.1654078 · Cited by 900
“All of our experiments are run on a system comprised of an NVIDIA GTX 285 GPU paired with an Intel Core i7 965 CPU.”
BackgroundInfluentialDebunking the 100X GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU
Lee, V. W., Kim, C., Chhugani, J., Deisher, M., Kim, D., Nguyen, A. D., Satish, N., Smelyanskiy, M., Chennupaty, S., Hammarlund, P., et al. (2010) · Proceedings of the 37th annual international symposium on Computer architecture · doi:10.1145/1815961.1816021 · Cited by 640
“SpMV (SpMV) [50, 8, 47] Sparse Solver Gather Across non-zero BW bound for typical large matrices”
BackgroundA view of the parallel computing landscape
Asanovic, K., Bodik, R., Demmel, J., Keaveny, T., Keutzer, K., Kubiatowicz, J., Morgan, N., Patterson, D., Sen, K., Wawrzynek, J., et al. (2009) · Communications of the ACM · doi:10.1145/1562764.1562783 · Cited by 627
Self-citationEcient Sparse Matrix-Vector Multiplication on CUDA
Bell, N., & Garland, M. (2008) · Cited by 574
Stencil computation optimization and auto-tuning on state-of-the-art multicore architectures
Datta, K., Murphy, M., Volkov, V. M., Williams, S., Carter, J. T., Oliker, L., Patterson, D. A., Shalf, J. M., & Yelick, K. (2008) · IEEE International Conference on High Performance Computing, Data, and Analytics · doi:10.5555/1413370.1413375 · Cited by 462
Self-citationBuluç, A., Fineman, J. T., Frigo, M., Gilbert, J. R., & Leiserson, C. E. (2009) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1583991.1584053 · Cited by 430
“Sublinear speedup of SpMV on superscalar multicore architectures has been noted by others as well [41].”
BackgroundModel-driven autotuning of sparse matrix-vector multiply on GPUs
Choi, J. W., Singh, A., & Vuduc, R. W. (2010) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/1693453.1693471 · Cited by 394
Self-citationUnderstanding sources of inefficiency in general-purpose chips
Hameed, R., Qadeer, W., Wachs, M., Azizi, O., Solomatnikov, A., Lee, B. C., Richardson, S., Kozyrakis, C., & Horowitz, M. (2010) · Proceedings of the 37th annual international symposium on Computer architecture · doi:10.1145/1815961.1815968 · Cited by 391
“Co-optimization of the memory system and the application can yield large savings in these situations [28], but the advantages of application customization over a conventional memory design with a few adjustable parameters still needs to be explored.”
BackgroundKjolstad, F., Kamil, S., Chou, S., Lugato, D., & Amarasinghe, S. (2017) · Proceedings of the ACM on Programming Languages · doi:10.1145/3133901 · Cited by 358
“…is a C library that automatically tunes sparse linear algebra kernels to take advantage of optimizations such as register blocking and vectorization. pOSKI [Byun et al. 2012] is another library that is built on top of OSKI and implements a number of parallel optimizations from Williams [2007].”
MethodCSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector Multiplication
Liu, W., & Vinter, B. (2015) · Proceedings of the 29th ACM on International Conference on Supercomputing · doi:10.1145/2751205.2751209 · Cited by 315
“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].”
BackgroundMethodStencil computation optimization and auto-tuning on state-of-the-art multicore architectures
Datta, K., Murphy, M., Volkov, V., Williams, S., Carter, J., Oliker, L., Patterson, D., Shalf, J., & Yelick, K. (2008) · 2008 SC - International Conference for High Performance Computing, Networking, Storage and Analysis · doi:10.1109/sc.2008.5222004 · Cited by 281
“Given the coherency protocol overhead, it is not too surprising that the performance does not improve between the four-core and eight-core experiment (when both FSBs are engaged), despite the doubling of the peak aggregate FSB bandwidth.”
InfluentialSelf-citationWhere is the data? Why you cannot debate CPU vs. GPU performance without the answer
Gregg, C., & Hazelwood, K. (2011) · (IEEE ISPASS) IEEE INTERNATIONAL SYMPOSIUM ON PERFORMANCE ANALYSIS OF SYSTEMS AND SOFTWARE · doi:10.1109/ispass.2011.5762730 · Cited by 279
“It can also run as a nonstreaming application, so its secondary category is DD.”
BackgroundA quantitative performance analysis model for GPU architectures
Zhang, Y., & Owens, J. D. (2011) · IEEE International Symposium on High-Performance Computer Architecture (HPCA) · doi:10.1109/hpca.2011.5749745 · Cited by 276
“We use a naturally 3x3 blocked sparse matrix named QCD, from the benchmark suite of 14 sparse matrices used in prior work by others [14, 20, 22].”
MethodAutomatically Tuning Sparse Matrix-Vector Multiplication for GPU Architectures
Monakov, A., Lokhmotov, A., & Avetisyan, A. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-11515-8_10 · Cited by 274
“Williams et al. [11] present evaluation of optimized SpMV implementations on multi-core x86 processors, STI Cell and Sun Niagara 2.”
BackgroundMethodInfluentialDebunking the 100X GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU
Lee, V. W., Kim, C., Chhugani, J., Deisher, M., Kim, D., Nguyen, A. D., Satish, N., Smelyanskiy, M., Chennupaty, S., Hammarlund, P., et al. (2010) · ACM SIGARCH Computer Architecture News · doi:10.1145/1816038.1816021 · Cited by 267
Efficient sparse matrix-vector multiplication on x86-based many-core processors
Liu, X., Smelyanskiy, M., Chow, E., & Dubey, P. K. (2013) · International Conference on Supercomputing · doi:10.1145/2464996.2465013 · Cited by 263
“3.2 Overview of CSR Kernel Similar to earlier work on SpMV for multi-core CPUs [26, 7], our CSR kernel is statically load balanced by row decomposition, in which the sparse matrix is partitioned into row blocks with approximately equal numbers of nonzeros.”
BackgroundMethodResultInfluentialKreutzer, M., Hager, G., Wellein, G., Fehske, H., & Bishop, A. R. (2014) · SIAM Journal on Scientific Computing · doi:10.1137/130930352 · Cited by 262
“These matrices have already been used in previous research [4, 6, 8] for analyzing the spMVM on GPGPUs, and thus provide a good basis for comparison.”
BackgroundMethodState-of-the-art in Heterogeneous Computing
Brodtkorb, A. R., Dyken, C., Hagen, T. R., Hjelmervik, J. M., & Storaasli, O. O. (2010) · Scientific Programming · doi:10.1155/2010/540159 · Cited by 257
Efficient Sparse Matrix-Vector Multiplication on GPUs Using the CSR Storage Format
Greathouse, J. L., & Daga, M. (2014) · SC14: International Conference for High Performance Computing, Networking, Storage and Analysis · doi:10.1109/sc.2014.68 · Cited by 246
“study SpMV across a number of modern parallel CPU architectures and found that the best performance came from tuning the algorithm and data structures to match the underlying hardware [32].”
BackgroundAccelerating Haskell array codes with multicore GPUs
Chakravarty, M. M. T., Keller, G., Lee, S., McDonell, T. L., & Grover, V. (2011) · Proceedings of the sixth workshop on Declarative aspects of multicore programming · doi:10.1145/1926354.1926358 · Cited by 244
“Using a 14 matrix corpus derived from a variety of application domains [34], we compare against several of the handoptimised CUSP algorithms most similar to our implementation.”
MethodMilepost GCC: Machine Learning Enabled Self-tuning Compiler
Fursin, G., Kashnikov, Y., Memon, A. W., Chamski, Z., Temam, O., Namolaru, M., Yom-Tov, E., Mendelson, B., Zaks, A., Courtois, E., et al. (2011) · International Journal of Parallel Programming · doi:10.1007/s10766-010-0161-2 · Cited by 234
“Originally developed to improve performance of various small kernels using a few parametric transformations across multiple architectures, where static compilers fail to deliver best performance [84,53,63,71,81,21,85], these techniques have been extended to larger applications and richer set of optimizations [22, 52,2…”
BackgroundParallel breadth-first search on distributed memory systems
Buluç, A., & Madduri, K. (2011) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/2063384.2063471 · Cited by 230
“A sparse graph can analogously be viewed as a sparse matrix, and optimization strategies for linear algebra computations similar to BFS, such as sparse matrix-vector multiplication [36], may be translated to the realm of graph”
BackgroundExposing Fine-Grained Parallelism in Algebraic Multigrid Methods
Bell, N., Dalton, S., & Olson, L. N. (2012) · SIAM Journal on Scientific Computing · doi:10.1137/110838844 · Cited by 215
“Nevertheless, efficient techniques exist for matrices with a wide variety of sparsity patterns [11, 9, 38, 15, 39, 4, 5].”
BackgroundThread motion: fine-grained power management for multi-core systems
Rangan, K. K., Wei, G.-Y., & Brooks, D. (2009) · Proceedings of the 36th annual international symposium on Computer architecture · doi:10.1145/1555754.1555793 · Cited by 209
A generic interface for parallel cell-based finite element operator application
Kronbichler, M., & Kormann, K. (2012) · Computers & Fluids · doi:10.1016/j.compfluid.2012.04.012 · Cited by 186
“Even though attempts have been made to tune SpMV kernels [56, 57] or to allow only problems with structured non-zero pattern [55], Gflops rates rarely exceed 2%–20% of peak arithmetic throughput.”
BackgroundAdaptive sparse tiling for sparse matrix multiplication
Hong, C., Sukumaran-Rajam, A., Nisa, I., Singh, K., & Sadayappan, P. (2019) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/3293883.3295712 · Cited by 189
“Register blocking also plays a pivotal role in many sparse matrix formats for both CPUs [8, 9, 45] and GPUs [47].”
BackgroundTechnological Exploration of RRAM Crossbar Array for Matrix-Vector Multiplication
Xia, L., Gu, P., Li, B., Tang, T., Yin, X., Huangfu, W., Yu, S., Cao, Y., Wang, Y., & Yang, H. (2016) · Journal of Computer Science and Technology · doi:10.1007/s11390-016-1608-8 · Cited by 183
Fast Sparse Matrix-Vector Multiplication on GPUs for Graph Applications
Ashari, A., Sedaghati, N., Eisenlohr, J., Parthasarathy, S., & Sadayappan, P. (2014) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc.2014.69 · Cited by 171
“…+ 1]; NNZ ← next row idx− row idx; bSize← NNZ/ThreadLoad; str ← a CUDA stream; SpMV <<< 1, bSize, str >>> (argv) where: // SpMV is the row specific kernel; Algorithm 4 begin argv[0] : values[row idx..next row idx); argv[1] : col idx[row idx..next row idx); argv[2] : NNZ; argv[3] : x; argv[4] : y;”
BackgroundModel-driven autotuning of sparse matrix-vector multiply on GPUs
Choi, J. W., Singh, A., & Vuduc, R. W. (2010) · ACM SIGPLAN Notices · doi:10.1145/1837853.1693471 · Cited by 166
Self-citationclSpMV: A Cross-Platform OpenCL SpMV Framework on GPUs
Su, B.-Y., & Keutzer, K. (2012) · International Conference on Supercomputing · doi:10.1145/2304576.2304624 · Cited by 153
“Based on the Cocktail Format, we develop the clSpMV framework that is able to analyze all kinds of sparse matrices at runtime, and recommend the best representations of the given sparse matrices on di.erent platforms.”
MethodReduced-Bandwidth Multithreaded Algorithms for Sparse Matrix-Vector Multiplication
Buluç, A., Williams, S., Oliker, L., & Demmel, J. W. (2011) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2011.73 · Cited by 150
“Our previous studies examined auto-tuned optimizations in the context of multicore architectures [34] and demonstrated its significant potential.”
BackgroundSelf-citationSparse Matrix-Vector Multiplication on GPGPUs
Filippone, S., Cardellini, V., Barbieri, D., & Fanfarillo, A. (2017) · ACM Transactions on Mathematical Software · doi:10.1145/3017994 · Cited by 175
“In the previous sections, we have seen in the format-by-format analysis that a number of SpMV optimizations previously used for other architectures [104, 103] have been also applied to GPGPUs.”
MethodEvaluation Criteria for Sparse Matrix Storage Formats
Langr, D., & Tvrdík, P. (2015) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2015.2401575 · Cited by 165
“Moreover, in case that matrices are within an HPC application constructed in different formats, this criterion alone is not sufficient for the key decision whether or not to convert them into the presented format for the SpMV-based application phase.”
BackgroundA High Memory Bandwidth FPGA Accelerator for Sparse Matrix-Vector Multiplication
Fowers, J., Ovtcharov, K., Strauß, K., Chung, E. S., & Stitt, G. (2014) · IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM) · doi:10.1109/fccm.2014.23 · Cited by 144
“Compressed Sparse Row (CSR) is a commonly used encoding for CPUs [19], GPUs [1][2], and FPGA implementations [4][11][21].”
BackgroundMethodAutotuning in High-Performance Computing Applications
Balaprakash, P., Dongarra, J. J., Gamblin, T., Hall, M. W., Hollingsworth, J. K., Norris, B., & Vuduc, R. W. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2841200 · Cited by 144
“Examples include application-specific autotuners such as lattice Boltzmann computations [48], stencil computations [49], and matrix multiplication kernels [50], [51].”
MethodSelf-citationAutomatic Selection of Sparse Matrix Representation on GPUs
Sedaghati, N., Mu, T., Pouchet, L.-N., Parthasarathy, S., & Sadayappan, P. (2015) · International Conference on Supercomputing · doi:10.1145/2751205.2751244 · Cited by 140
“[26] moved toward multi-core platforms with the implementation of parallel SpMV kernels.”
BackgroundMinimizing communication in sparse matrix solvers
Mohiyuddin, M., Hoemmen, M. F., Demmel, J. W., & Yelick, K. (2009) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/1654059.1654096 · Cited by 140
“Register tile size: Register tiling a sparse matrix can reduce the required slow memory bandwidth [24] or improve instruction through-put [22].”
BackgroundMethodInfluentialSelf-citationAlappat, C. L., Basermann, A., Bishop, A. R., Fehske, H., Hager, G., Schenk, O., Thies, J., & Wellein, G. (2020) · ACM Transactions on Parallel Computing · doi:10.1145/3399732 · Cited by 140
“Various authors [19, 47] used advanced data storage formats and techniques such as register and cache blocking for SpMV by splitting the matrix into several smaller p × q sparse submatrices and presented an analytic cache-aware model to determine the optimal block size.”
MethodAvoiding communication in sparse matrix computations
Demmel, J., Hoemmen, M. F., Mohiyuddin, M., & Yelick, K. (2008) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2008.4536305 · Cited by 139
“CacheBlocked: This implementation models a single core of the quad-core Intel Clovertown chip, with 2 GFlops/s (based on measurements in [27]) with onchip 8 MB cache as fast memory and DRAM as slow memory.”
MethodSelf-citationOptimizing Sparse Matrix—Matrix Multiplication for the GPU
Dalton, S., Olson, L. N., & Bell, N. (2015) · ACM Transactions on Mathematical Software · doi:10.1145/2699470 · Cited by 138
“An analysis of SpMV reveals that the operation has very low computational intensity—that is, the ratio of the floating-point operations (FLOPs) to memory accesses—which severely limits the potential throughput of the operation on contemporary architectures [Williams et al. 2009a, 2009b].”
BackgroundCoRAM: an in-fabric memory architecture for FPGA-based computing
Chung, E. S., Hoe, J. C., & Mai, K. (2011) · ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA) · doi:10.1145/1950413.1950435 · Cited by 138
“SpMV has been studied and optimized extensively for general-purpose architecture [108, 54, 48, 105, 104, 70, 95, 100, 84].”
BackgroundPerformance Evaluation of Sparse Matrix Multiplication Kernels on Intel Xeon Phi
Saule, É., Kaya, K., & Çatalyürek, Ü. V. (2014) · Lecture notes in computer science · doi:10.1007/978-3-642-55224-3_52 · Cited by 134
“well studied [1–3,9,19], and there exist several techniques such as prefetching, loop transformations, vectorization, register, cache, TLB blocking, and NUMA optimization, which have been extensively investigated to optimize the performance [7,11,12,19].”
BackgroundAn Efficient GPU General Sparse Matrix-Matrix Multiplication for Irregular Data
Liu, W., & Vinter, B. (2014) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2014.47 · Cited by 134
Fast sparse matrix-vector multiplication on GPUs: implications for graph mining
Yang, X., Parthasarathy, S., & Sadayappan, P. (2011) · Proceedings of the VLDB Endowment · doi:10.14778/1938545.1938548 · Cited by 134
“Williams [20] compares SpMV kernels on emerging multicore platforms.”
BackgroundMerge-Based Parallel Sparse Matrix-Vector Multiplication
Merrill, D., & Garland, M. (2016) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc.2016.57 · Cited by 134
“11 compares CsrMV performance across commonlyevaluated, large-sized matrices [26], [35].”
BackgroundMethodSMAT: an input adaptive auto-tuner for sparse matrix-vector multiplication
Li, J., Tan, G., Chen, M., & Sun, N. (2013) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/2491956.2462181 · Cited by 133
DimmWitted: a study of main-memory statistical analytics
Zhang, C., & Ré, C. (2014) · Proceedings of the VLDB Endowment · doi:10.14778/2732977.2733001 · Cited by 131
yaSpMV: yet another SpMV framework on GPUs
Yan, S., Li, C., Zhang, Y., & Zhou, H. (2014) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/2555243.2555255 · Cited by 129
“These matrices have been widely used in previous works [1][7][12][16][23].”
MethodTaming parallel I/O complexity with auto-tuning
Behzad, B., Luu, H. V. T., Huchette, J., Byna, S., Prabhat, Aydt, R. A., Koziol, Q., & Snir, M. (2013) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/2503210.2503278 · Cited by 129
“There has been extensive research in developing optimized linear algebra libraries and matrix operation kernels using auto-tuning [29, 14, 16, 28, 31, 12, 30].”
BackgroundCommunication lower bounds and optimal algorithms for numerical linear algebra
Ballard, G., Carson, E., Demmel, J. W., Hoemmen, M. F., Knight, N., & Schwartz, O. (2014) · Acta Numerica · doi:10.1017/s0962492914000038 · Cited by 128
“For details, see Vuduc (2003), Vuduc et al. (2005) and Williams et al. (2009), for example.”
BackgroundSelf-citationMaking caches work for graph analytics
Zhang, Y., Kiriansky, V., Mendis, C., Amarasinghe, S. P., & Zaharia, M. (2017) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata.2017.8257937 · Cited by 128
“Finally, graph applications like PageRank are analogous to sparse matrix-vector multiply problems, for which techniques, such as cache blocking, have been proposed [16], [24].”
MethodPerformance Optimization Using Partitioned SpMV on GPUs and Multicore CPUs
Yang, W., Li, K., Mo, Z., & Li, K. (2014) · IEEE Transactions on Computers · doi:10.1109/tc.2014.2366731 · Cited by 127
Improving the Performance of the Sparse Matrix Vector Product with GPUs
Vázquez, F., Ortega, G., Fernández, J., & Garzón, E. M. (2010) · IEEE International Conference on Computer and Information Technology (CIT) · doi:10.1109/cit.2010.208 · Cited by 123
“Despite these drawbacks, several optimizations have made possible to improve the performance of sparse computation on current processors [8], [15].”
BackgroundMethodUnderstanding sources of inefficiency in general-purpose chips
Hameed, R., Qadeer, W., Wachs, M. A., Azizi, O., Solomatnikov, A., Lee, B. C., Richardson, S., Kozyrakis, C., & Horowitz, M. (2010) · ACM SIGARCH Computer Architecture News · doi:10.1145/1816038.1815968 · Cited by 122
Rabbit Order: Just-in-Time Parallel Reordering for Fast Graph Analysis
Arai, J., Shiokawa, H., Yamamuro, T., Onizuka, M., & Iwamura, S. (2016) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2016.110 · Cited by 120
“As is common practice, we parallelize SpMV (Algorithm 1) at the outermost for-loop using the thread blocking technique of Williams et al. [26].”
MethodAn anomaly detection system based on variable N-gram features and one-class SVM
Khreich, W., Khosravifar, B., Hamou-Lhadj, A., & Talhi, C. (2017) · Information and Software Technology · doi:10.1016/j.infsof.2017.07.009 · Cited by 115
“However, the obtained feature vectors are very sparse, at most 2× 6− 1 = 11 elements are non-null, and hence they can be e ciently encoded in practise using specialized machine learning libraries for sparse vectors and matrices computation [41].”
BackgroundA new approach for sparse matrix vector product on NVIDIA GPUs
Vázquez, F., Fernández, J., & Garzón, E. M. (2010) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.1658 · Cited by 119
“Despite these drawbacks, several optimizations have made it possible to improve the performance of sparse computation on current processors [5, 18].”
BackgroundSpaceA: Sparse Matrix Vector Multiplication on Processing-in-Memory Accelerator
Xie, X., Liang, Z., Gu, P., Basak, A., Deng, L., Liang, L., Hu, X., & Xie, Y. (2021) · IEEE International Symposium on High-Performance Computer Architecture (HPCA) · doi:10.1109/hpca51647.2021.00055 · Cited by 119
“The study on efficient SpMV imple mentation starts from the CPU platform where the explo ration of the locality of SpMV computations to efficiently use the memory bandwidth plays a major role [31], [44], [49], [66].”
BackgroundNaumov, M. (2011) · Cited by 116
HiCOO: Hierarchical Storage of Sparse Tensors
Li, J., Sun, J., & Vuduc, R. W. (2018) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc.2018.00022 · Cited by 112
Self-citationA framework for general sparse matrix–matrix multiplication on GPUs and heterogeneous processors
Liu, W., & Vinter, B. (2015) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2015.06.010 · Cited by 110
“ultiplier with different sparsity structure. We choose 23 sparse matrices as our benchmark suite. 16 of them were widely used for performance evaluations in previous sparse matrix computation research [8, 11, 14, 15, 16, 24, 25, 51]. The other 7 new matrices are chosen since they bring more diverse irregular sparsity s…”
BackgroundMethodWilliams, S., Waterman, A., & Patterson, D. (2009) · doi:10.2172/1407078 · Cited by 110
“Indeed, three of the results were considered significant enough to be accepted for publication at major conferences [12][25][26].”
BackgroundSelf-citationOn the limits of GPU acceleration
Vuduc, R. W., Chandramowlishwaran, A. M., Choi, J. W., Guney, M. E., & Shringarpure, A. (2010) · Cited by 108
Self-citationUltraSPARC T2: A highly-treaded, power-efficient, SPARC SOC
Shah, M., Olson, C., Saha, B., Sheahan, D., Spracklen, L., Wynn, A., Barreh, J., Brooks, J., Golla, R., Grohoski, G., et al. (2007) · IEEE Asian Solid-State Circuits Conference (A-SSCC) · doi:10.1109/asscc.2007.4425786 · Cited by 108
Sextans: A Streaming Accelerator for General-Purpose Sparse-Matrix Dense-Matrix Multiplication
Song, L., Chi, Y., Sohrabizadeh, A., Choi, Y., Lau, J., & Cong, J. (2022) · ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA) · doi:10.1145/3490422.3502357 · Cited by 121
“An intuitive approach to paralleling SpMM on CPUs/GPUs is row based parallelization [6, 74, 80] as shown in Figure 1 (b).”
BackgroundMethodGiannoula, C., Fernandez, I., Gómez-Luna, J., Koziris, N., Goumas, G., & Mutlu, O. (2022) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3508041 · Cited by 104
“Numerous prior works propose optimized SpMV algorithms for CPUs [15, 25–27, 58, 78, 81, 101, 109, 110], GPUs [13, 18, 41, 47, 74, 97, 99, 111, 113, 114], heterogeneous CPU-GPU systems [6, 50, 115, 117], and distributed CPU systems [10, 16, 53, 65, 73, 86].”
MethodBridging the gap between deep learning and sparse matrix format selection
Zhao, Y., Li, J., Liao, C., & Shen, X. (2018) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/3178487.3178495 · Cited by 104
“There are some other efforts trying to optimize the computations over sparse matrices, including hand-tuning inputor architecture-related features [6, 25, 41], designing new sparse formats [6, 17, 33], and building automatically performance tuning (auto-tuning) systems [10, 20, 32, 38].”
BackgroundPerformance evaluation of the sparse matrix-vector multiplication on modern architectures
Goumas, G., Kourtis, K., Anastopoulos, N., Karakasis, V., & Koziris, N. (2008) · The Journal of Supercomputing · doi:10.1007/s11227-008-0251-8 · Cited by 102
“[29] have presented an evaluation of SpMxV on a set of emerging multicore architectures.”
BackgroundANNarchy: a code generation approach to neural simulations on parallel hardware
Vitay, J., Dinkelbach, H. Ü., & Hamker, F. H. (2015) · Frontiers in Neuroinformatics · doi:10.3389/fninf.2015.00019 · Cited by 100
“The situation is reversed with CUDA: the network with 1000 neurons only achieves a speedup ratio of 3.8, while the network with 4000 neurons achieves a ratio of 7.15. cache blocking, loop unrolling, prefetching and autotuning (Williams et al., 2007; Kelefouras et al., 2015).”
BackgroundInfluentialLINQits: big data on little clients
Chung, E. S., Davis, J. D., & Lee, J. (2013) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/2485922.2485945 · Cited by 99
“This provides an opportunity to optimize the algorithm and target specific hardware, as has been demonstrated by SEJITS, Copperhead and auto-tuning [26, 7, 45].”
MethodLattice Boltzmann simulation optimization on leading multicore platforms
Williams, S., Carter, J., Oliker, L., Shalf, J., & Yelick, K. (2008) · 2008 IEEE International Symposium on Parallel and Distributed Processing · doi:10.1109/ipdps.2008.4536295 · Cited by 98
“In the multithreaded experiments, the optimally auto-tuned TLB-blocking results in approximately 4.0 GB/s and 4.4 GB/s of memory bandwidth utilization for two and four cores (respectively), which is close to the practical limits of a single FSB [20].”
BackgroundInfluentialSelf-citationIshfaq Ahmad, D., Ranka, S., & Khan, S. U. (2008) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2008.4536420 · Cited by 96
“Although we can guarantee the existence of a Bargaining Point in this problem, the classical cooperative game theoretical techniques such as the Nash axiomatic technique cannot be used to identify the Bargaining Point due to low convergence rates and high complexity.”
MethodOptimizing sparse matrix-vector multiplication using index and value compression
Kourtis, K., Goumas, G., & Koziris, N. (2008) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/1366230.1366244 · Cited by 95
“[24] apply a simple index reduction technique, in which 16-byte indices are used when it is possible.”
MethodOptimising purely functional GPU programs
McDonell, T. L., Chakravarty, M. M. T., Keller, G., & Lippmeier, B. (2013) · ACM SIGPLAN International Conference on Functional Programming (ICFP) · doi:10.1145/2500365.2500595 · Cited by 92
“For test data we use a 14 matrix corpus derived from a variety of application domains [33].”
MethodGraphReduce: processing large-scale graphs on accelerator-based systems
Sengupta, D., Song, S. L., Agarwal, K., & Schwan, K. (2015) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/2807591.2807655 · Cited by 92
“…Size GPU In-Memory ak2010[3] 45,292 108,549 7.9MB coAuthorsDBLP[5] 299,067 977,676 69.5MB kron g500-logn20[31] 1,048,576 44,620,272 2.4GB webbase-1M[40] 1,000,005 The high compute power and multi-level parallelism provided by the SIMT (Single Instruction Multiple Threads) architectures of GPGPUs…”
MethodLoop and data transformations for sparse matrix code
Venkat, A., Hall, M. W., & Strout, M. M. (2015) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/2737924.2738003 · Cited by 91
“1h for the same set of 14 matrices used by Williams et al.[48] and obtained from the University of Florida Sparse Matrix Collection[16].”
BackgroundMethodInfluentialKanellopoulos, K., Vijaykumar, N., Giannoula, C., Azizi, R., Koppula, S., Ghiasi, N. M., Shahroodi, T., Gómez-Luna, J., & Mutlu, O. (2019) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1145/3352460.3358286 · Cited by 89
“A range of prior works also include general software frameworks, such as MKL [1] and TACO [40], that leverage these optimizations to produce more efficient code for CPUs [1, 14, 15, 22, 23, 34, 37, 40, 56, 57, 62, 79, 87, 88, 90], GPUs [10, 18, 31, 35, 51, 91, 93], or heterogeneous CPU-GPU systems [52, 55].”
MethodA scalable sparse matrix-vector multiplication kernel for energy-efficient sparse-blas on FPGAs
Dorrance, R., Ren, F., & Markovic, D. M. (2014) · ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA) · doi:10.1145/2554688.2554785 · Cited by 89
Aktulga, H. M., Buluç, A., Williams, S., & Yang, C. (2014) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2014.125 · Cited by 108
“…− ΨE‖F is small, and ΨTΨ = I; Orthonormalize the columns of Ψ0; P0 ← 0; for i = 0, 1, . . . , until convergence do Ei = Ψ T i ĤΨi; Ri ← ĤΨi − ΨiEi Apply the Rayleigh-Ritz procedure on span{Ψi, Ri, Pi}; Ψi+1 ← argmin Y ∈span{Ψi,Ri,Pi},Y T Y=I trace(Y T ĤY ) Pi+1 ← Ψi+1 − Ψi; Check convergence;”
Self-citationTileSpMV: A Tiled Algorithm for Sparse Matrix-Vector Multiplication on GPUs
Niu, Y., Lu, Z., Dong, M., Jin, Z., Liu, W., & Tan, G. (2021) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps49936.2021.00016 · Cited by 86
CVR: efficient vectorization of SpMV on x86 processors
Xie, B., Zhan, J., Liu, X., Gao, W., Jia, Z., He, X., & Zhang, L. (2018) · Proceedings of the CGO/Proceedings of the ... CGO · doi:10.1145/3168818 · Cited by 86
Sparse matrix computations on manycore GPU's
Garland, M. (2008) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1145/1391469.1391473 · Cited by 84
“[14] explore a number of such optimizations, using an autotuning framework to uncover the best mix of optimizations for various multicore architectures.”
MethodGuo, P., Wang, L., & Chen, P. (2013) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2013.123 · Cited by 83
“We evaluate our tool on 22 matrices from the sparse matrices collection [26], [27], as shown in Table 3.”
MethodThe Sparse Polyhedral Framework: Composing Compiler-Generated Inspector-Executor Code
Strout, M. M., Hall, M. W., & Olschanowsky, C. M. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2857721 · Cited by 83
“[6] S.”
Tuned and wildly asynchronous stencil kernels for hybrid CPU/GPU systems
Venkatasubramanian, S., & Vuduc, R. W. (2009) · International Conference on Supercomputing · doi:10.1145/1542275.1542312 · Cited by 82
“We evaluate these implementations in Section 4.”
Self-citationReducing Pagerank Communication via Propagation Blocking
Beamer, S., Asanović, K., & Patterson, D. A. (2017) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2017.112 · Cited by 82
Hwu, W., Keutzer, K., & Mattson, T. G. (2008) · IEEE Design & Test of Computers · doi:10.1109/mdt.2008.110 · Cited by 81
CSX: an extended compression format for spmv on shared memory systems
Kourtis, K., Karakasis, V., Goumas, G., & Koziris, N. (2011) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/1941553.1941587 · Cited by 80
TileSpGEMM: a tiled algorithm for parallel sparse general matrix-matrix multiplication on GPUs
Niu, Y., Lu, Z., Ji, H., Song, S., Jin, Z., & Liu, W. (2022) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/3503221.3508431 · Cited by 78
“[105] and are the classic dataset in much subsequent sparse matrix research.”
Background(2009) · Cited by 77
Compressed linear algebra for large-scale machine learning
Elgohary, A., Böehm, M., Haas, P. J., Reiss, F. R., & Reinwald, B. (2016) · Proceedings of the VLDB Endowment · doi:10.14778/2994509.2994515 · Cited by 76
Optimizing I/O Performance of HPC Applications with Autotuning
Behzad, B., Byna, S., Prabhat, & Snir, M. (2018) · ACM Transactions on Parallel Computing · doi:10.1145/3309205 · Cited by 76
“Extensive research has been done in developing optimized linear algebra libraries and matrix operation kernels using autotuning (Whaley et al. 2001; Frigo and Johnson 1998; Bilmes et al. 1997; Vuduc et al. 2005; Williams et al. 2007; Datta et al. 2008; Williams et al. 2008).”
BackgroundStatic Resilience of Large Flexible Engineering Systems: Axiomatic Design Model and Measures
Farid, A. M. (2015) · IEEE Systems Journal · doi:10.1109/jsyst.2015.2428284 · Cited by 76
“the knowledge bases and constraint matrices [25], [55].”
BackgroundAuto-tuning performance on multicore computers
Patterson, D. A., & Williams, S. (2008) · Cited by 83
Self-citationTechnological exploration of RRAM crossbar array for matrix-vector multiplication
Gu, P., Li, B., Tang, T., Yu, S., Cao, Y. K., Wang, Y., & Yang, H. (2015) · Asia and South Pacific Design Automation Conference (ASP-DAC) · doi:10.1109/aspdac.2015.7058989 · Cited by 81
High-Level Strategies for Parallel Shared-Memory Sparse Matrix-Vector Multiplication
Yzelman, A.-J. N., & Roose, D. (2013) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2013.31 · Cited by 72
Sustained Petascale Performance of Seismic Simulations with SeisSol on SuperMUC
Breuer, A., Heinecke, A., Rettenberger, S., Bader, M., Gabriel, A., & Pelties, C. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-07518-1_1 · Cited by 70
“[32,49,53].”
An efficient two-dimensional blocking strategy for sparse matrix-vector multiplication on GPUs
Ashari, A., Sedaghati, N., Eisenlohr, J., & Sadayappan, P. (2014) · International Conference on Supercomputing · doi:10.1145/2597652.2597678 · Cited by 69
Speculative segmented sum for sparse matrix-vector multiplication on heterogeneous processors
Liu, W., & Vinter, B. (2015) · Parallel Computing · doi:10.1016/j.parco.2015.04.004 · Cited by 69
“Thereofore, improving performance of SpMV using the most widely supported CSR format has also gained plenty of attention [1, 2, 13, 14, 15, 16, 17, 18].”
BackgroundMethodInfluential
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.