A model-driven partitioning and auto-tuning integrated framework for sparse matrix-vector multiplication on GPUs

Ping Guo, He Huang, Qichang Chen, Liqiang Wang, En-Jui Lee, Po ChenTG 2011 · DOI

TL;DR

This paper introduces a novel framework that significantly accelerates sparse matrix-vector multiplication (SpMV) on GPUs. By creating a performance model to predict kernel execution times and using it to intelligently partition matrices and tune GPU parameters, they achieve substantial speedups over existing GPU implementations.

What Problem Does This Paper Address?

Sparse matrix-vector multiplication (SpMV) is a fundamental operation in many scientific and engineering simulations, particularly for solving systems of linear equations and partial differential equations. As datasets grow, the efficiency of SpMV becomes critical. Graphics Processing Units (GPUs) offer massive parallel processing power, making them attractive for accelerating these computations. However, SpMV performance on GPUs is highly sensitive to how the sparse matrix is stored (its format) and how the computation is mapped to the GPU's architecture. Existing GPU SpMV implementations often struggle to find the optimal storage format and computational configuration for a given matrix and GPU, leading to suboptimal performance. This paper tackles the challenge of automatically optimizing SpMV performance on GPUs by addressing both matrix partitioning and kernel parameter tuning.

Methods

The core of this work lies in a two-pronged approach:

  1. Model-Driven Partitioning:
    • Empirical Performance Model: The authors develop a model that predicts the execution time of SpMV CUDA kernels for different sparse matrix storage formats (CSR, ELL, HYB). This model is "empirical," meaning it's built from experimental data and observations rather than purely theoretical derivations.
  2. Matrix Partitioning: Based on the performance model, the framework intelligently partitions a large sparse matrix into smaller "strips." Each strip can then be transformed into an optimal storage format (CSR, ELL, or HYB) that best suits its characteristics (e.g., number of non-zero elements per row). This is crucial because different formats excel under different sparsity patterns. The partitioning process aims to minimize the total predicted execution time across all partitions.
  3. Auto-Tuning CUDA Kernels:
    • Parameter Optimization: The framework integrates with a previously developed auto-tuning mechanism. This mechanism automatically adjusts key CUDA kernel parameters (like Num_Threads, Block_Size, and Warp_Size) to find the configuration that yields the best performance for a specific GPU and matrix format.

The overall workflow involves first building a GPU-specific performance model, then using this model to partition the input matrix and select optimal storage formats for each partition, and finally auto-tuning the CUDA kernel parameters for each partition.

Datasets

The paper evaluates its approach using a collection of "widely-used sparse matrix benchmarks." They specifically mention using the 14 matrices from reference [3] (Bell and Garland, 2009) for their experiments. No new benchmarks were introduced; instead, they leverage existing, commonly used datasets in the sparse matrix research community.

Key Insights and Ideas

  • Storage Format Matters Greatly: The paper strongly reinforces the idea that the choice of sparse matrix storage format (CSR, ELL, HYB) has a significant impact on SpMV performance on GPUs. No single format is universally best; the optimal choice depends on the matrix's sparsity pattern.
  • Partitioning is Key for Heterogeneity: For large matrices, partitioning them into smaller segments and applying different storage formats to each segment can unlock performance gains that wouldn't be possible with a single format for the entire matrix.
  • Model-Based Prediction is Powerful: An empirical performance model, even if not perfectly precise, can effectively guide complex decisions like matrix partitioning and format selection, leading to better overall performance than heuristic or brute-force approaches.
  • Auto-Tuning is Complementary: While partitioning and format selection are crucial, fine-tuning CUDA kernel parameters remains essential for squeezing out the last bits of performance from the GPU architecture.

Key Results

The paper demonstrates substantial performance improvements over NVIDIA's existing SpMV CUDA kernels [3]:

  • CSR vector kernel: 222% performance improvement on average.
  • ELL kernel: 197% performance improvement on average.
  • HYB kernel: 33% performance improvement on average.

These improvements are attributed to the combined effect of model-driven partitioning and auto-tuning.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that the ELL kernel cannot process certain matrices ("Webase" and "LP") due to GPU memory limitations.
  • The performance evaluation does not include the time taken for sorting the target matrix or adjusting the result order, which might add overhead in some applications.
  • The current partitioning strategy primarily focuses on CSR and ELL, with HYB being considered as a potential outcome.
  • Future Work:
    • Refine the performance model for even more accurate prediction of matrix partitioning.
  • Extend the framework to support and integrate more SpMV kernels.
  • Apply the developed approach to a broader range of scientific and engineering applications beyond SpMV.

Summary updated

BibTeX
@inproceedings{guo2011model,
  author = {Ping Guo and He Huang and Qichang Chen and Liqiang Wang and En-Jui Lee and Po Chen},
  title = {{A model-driven partitioning and auto-tuning integrated framework for sparse matrix-vector multiplication on GPUs}},
  booktitle = {TG},
  year = {2011},
  doi = {10.1145/2016741.2016744},
}
Figure