Optimization of sparse matrix-vector multiplication on emerging multicore platforms

By Samuel Williams, Leonid Oliker, R. Vuduc, John M. Shalf, K. Yelick, J. Demmel. International Conference on Software Composition, 2007

866 citations recorded by the source corpus.

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.

View Paper: https://www.semanticscholar.org/paper/8138ab11231447708f13d1a593389ded2b845b1b

How researchers see this paper

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

Citations in the corpus

State-of-the-art in heterogeneous computing (2010, methodology): “…Use of registers instead of shared memory (GPU) [180]; Linpack (CBEA) [99]; Mixed precision (FPGA) [164] Sparse linear algebra Blocking (CBEA) [182]; Data structures (GPU) [23] Fast Fourier transform Auto-tuning (GPU) [124]; Hierarchically decomposed (GPU) [66]; Iterative out-of-place (CBEA)…”
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”
LINQits: big data on little clients (2013, methodology): “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].”
Understanding sources of inefficiency in general-purpose chips (2010, background): “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.”
The tensor algebra compiler (2017, methodology): “…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].”
CSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector Multiplication (2015, methodology): “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].”
Roofline: An Insightful Visual Performance Model for Floating-Point Programs and Multicore Architectures (2008, background): “Indeed, three of the results were considered significant enough to be accepted for publication at major conferences [12][25][26].”
Implementing sparse matrix-vector multiplication on throughput-oriented processors (2009, background): “All of our experiments are run on a system comprised of an NVIDIA GTX 285 GPU paired with an Intel Core i7 965 CPU.”
Where is the data? Why you cannot debate CPU vs. GPU performance without the answer (2011, background): “It can also run as a nonstreaming application, so its secondary category is DD.”
A quantitative performance analysis model for GPU architectures (2011, methodology): “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].”
Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks (2009, background): “Sublinear speedup of SpMV on superscalar multicore architectures has been noted by others as well [41].”