Implementing sparse matrix-vector multiplication on throughput-oriented processors

By Nathan Bell, Michael Garland. Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, 2009

974 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/1cd294f3bcd647c8a2b2bbce47e827a8ece8b973

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Hardware and Architecture

Citations in the corpus

High-order finite-element seismic wave propagation modeling with MPI on a large GPU cluster (2010, methodology): “In finite-element applications, whether low or high order, contributions must be added between adjacent elements, which leads to dependencies for degrees of freedom that require the summation of contributions from several elements.”
CSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector Multiplication (2015, methodology): “The ﬁrst 20 matrices have been widely adopted in previous SpMV research [2, 4, 17, 24, 29, 33, 34].”
Where is the data? Why you cannot debate CPU vs. GPU performance without the answer (2011, methodology): “We benchmarked an implementation described in Bell and Garland [20] for the coordinate (or “triplet”) format that has a storage size proportional to the number of nonzeros in the sparse matrix.”
AWB-GCN: A Graph Convolutional Network Accelerator with Runtime Workload Rebalancing (2019, methodology): “Researchers also conduct software optimizations for SpMM on GPUs and general-purpose multicore CPUs [61]–[65].”
PyCUDA and PyOpenCL: A scripting-based approach to GPU run-time code generation (2009, methodology): “Using the array infrastructure, PyCUDA also implements GPU-based sparse matrix-vector multiplication, as described by Garland and Bell [1].”
Scalable GPU graph traversal (2012, methodology): “Hong et al. [18] describe a vectorized version of the vertexoriented method that is similar to the CSR sparse matrix-vector (SpMV) multiplication approach by Bell and Garland [6].”
GPU-accelerated preconditioned iterative linear solvers (2013, methodology): “Existing implementations of the GPU Sparse matrix-vector product (SpMV) include CUDPP (CUDA Data Parallel Primitives) library [24], NVIDIA CUSPARSE library [5] and the IBM SpMV library [4].”
Multicore bundle adjustment (2011, methodology): “This includes general purpose libraries like nVidia’s Sparse Matrix-Vector Multiplication [3] and Li and Saad’s work on various GPU-based PCG algorithms and preconditioning techniques [10].”
Efficient, high-quality image contour detection (2009, methodology): “Utilizing similar optimizations as described in [4], our SpMV routine achieves 40 GFlops/s on matrices derived from the intervening contour approach, with r = 5, leading to 81 nonzero diagonals.”
EIE: Efficient Inference Engine on Compressed Deep Neural Network (2016, methodology): “[44] developed SPMV techniques that utilizes large percentages of peak bandwidth for throughput-oriented architectures like the GPU.”
Debunking the 100X GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU (2010, background): “SpMV (SpMV) [50, 8, 47] Sparse Solver Gather Across non-zero BW bound for typical large matrices”
A quantitative performance analysis model for GPU architectures (2011, methodology): “Although we have not built a texture cache simulator into our model, we tried using texture cache for vector entries, as what the two previous studies [14, 20 ] did.”
Towards Evolutionary Compression (2018, background): “Therefore, Han et al. [14] demonstrated that most of parameters could be removed without affecting the performance of the pre-trained network, and [13] further compactly stored the generated sparse networks in sparse row format (CSR) [3] and Huffman encoding [19].”