PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Sparse Matrix-Vector Multiplication on GPUs: Implications for Graph Mining

Xintian Yang, Srinivasan Parthasarathy, Ponnuswamy Sadayappan

arXiv:1103.2405v1math.NAcs.MS

TL;DR

GPU graph-mining algorithms depend on SpMV, but power-law graph matrices create irregular accesses and tuning demands. The paper introduces a self-tunable representation combining tiling, composite storage, and GPU-aware optimization, achieving faster single-GPU performance and scalable web-scale execution. It also provides a performance model for runtime parameter selection and prediction, subject to assumptions about tuning and GPU occupancy.

  • Problem

    Efficient GPU SpMV for graph-mining algorithms remains difficult because power-law matrices produce irregular memory accesses, costly tiling, and input-dependent parameter choices.

  • Method

    The paper combines power-law-aware composite storage, texture-cache-conscious tiling, multi-GPU execution, and runtime autotuning for GPU SpMV.

  • Results

    Across moderately sized real datasets, the optimized SpMV and graph-mining methods are typically 1.8 to 2.1 times faster than an industrial-strength GPU competitor and 18 to 32 times faster than an optimized CPU implementation, while reaching up to 70% parallel efficiency on web-scale graphs.

  • Takeaways & Limitations

    The approach supports efficient graph mining on single GPUs and scalable processing of web-scale graphs across multiple GPUs.

  • Takeaways & Limitations

    The optimization approach requires tuning the number of tiles and each tile’s partitioning strategy, and the kernel assumes full occupancy of GPU multiprocessors.

Abstract

from arXiv · show

Scaling up the sparse matrix-vector multiplication kernel on modern Graphics Processing Units (GPU) has been at the heart of numerous studies in both academia and industry. In this article we present a novel non-parametric, self-tunable, approach to data representation for computing this kernel, particularly targeting sparse matrices representing power-law graphs. Using real data, we show how our representation scheme, coupled with a novel tiling algorithm, can yield significant benefits over the current state of the art GPU efforts on a number of core data mining algorithms such as PageRank, HITS and Random Walk with Restart.

1. INTRODUCTION

The paper develops a GPU approach for graph-mining algorithms built on SpMV, targeting sparse matrices from power-law graphs with architecture-conscious representation, tiling, and runtime parameter tuning.

  • 1. INTRODUCTION: The study is motivated by the computational demands of data-intensive algorithms and the increasing availability of commodity GPUs and other parallel processor architectures.The paper argues that these algorithms can benefit from such architectures when appropriately leveraged.
  • 1. INTRODUCTION: The work targets PageRank, HITS, and Random Walk with Restart because these graph-mining algorithms rely on the sparse matrix-vector multiplication kernel.The paper evaluates the proposed methods on these algorithms and the base SpMV kernel using real datasets.
  • 1. INTRODUCTION: The approach represents power-law graph matrices to enable tiling, exploit degree-distribution skew, and use GPU features such as the texture cache.It also extends to web-scale graphs with billions of edges across multiple GPUs.
  • 1. INTRODUCTION: The method automatically tunes two parameters at runtime and provides a performance model for predicting kernel performance under different settings.The model is intended to support adaptive algorithm designs for hybrid architectures.
  • 1. INTRODUCTION: 1.8 to 2.1 times faster than an industrial-strength GPU competitor, and 18 to 32 times faster than an optimized CPU implementation, across SpMV, HITS, PageRank, and Random Walk with Restart.These results come from moderately sized real datasets that fit on a single GPU.

2. RELATED WORK

Prior GPU SpMV work provides multiple sparse formats and tuning methods, but does not account for the skewed nonzero distributions of power-law graph matrices, whose performance can therefore be poor.

  • 2. RELATED WORK: Existing GPU SpMV efforts do not account for the skewed nonzero distributions characteristic of matrices representing power-law graphs.The paper identifies this omission as central to its distinction from prior work.
  • 2. RELATED WORK: Previously reported implementations perform poorly on matrices with power-law characteristics.This limitation is presented as a consequence of their failure to model the relevant distribution skew.
  • 2. RELATED WORK: NVIDIA’s SpMV library offers CSR, CSR-vector, COO, ELL, HYB, DIA, and PKT formats, while blocked ELL-pack introduces high memory overhead on power-law matrices.The blocked ELL-pack approach stores nonzeros in blocks indexed with ELL.
  • 2. RELATED WORK: Prior SpMV optimization studies span single-core CPUs, multicore platforms, and GPUs, including architecture models and model-driven autotuning frameworks.These efforts establish a broader context of platform-specific optimization and performance modeling.
  • 2. RELATED WORK: Earlier optimization methods require parameter tuning that depends on input-matrix characteristics, motivating performance models to guide tuning.The related work includes analytical GPU models and adaptive performance-modeling tools.

3. METHODOLOGY

The methodology transforms power-law sparse matrices into tiled and composite representations that improve GPU SpMV locality and workload balance, while automatically tuning key parameters with a performance model.

  • 3. METHODOLOGY: The approach combines matrix tiling, composite storage, GPU texture-cache reuse, and runtime parameter tuning for SpMV on power-law matrices.Tiling restricts vector accesses to cache-sized segments, while composite storage addresses power-law row-length imbalance.
  • 3.1 Single-GPU SpMV: Tiling partitions matrix A and vector x so each tile accesses one vector segment, allowing cached elements to be reused during tile computation.The texture-cache size determines tile width, and benchmarking fixes the width at 64K columns.
  • 3.1 Single-GPU SpMV: Whole-matrix tiling performs poorly because many sparse-column tiles require kernel restarts and incur non-coalesced writes despite limited vector reuse.Power-law column lengths motivate separating denser and sparser sub-matrices before tiling.
  • 3.1 Single-GPU SpMV: The method targets GPU-kernel inefficiencies caused by COO thread divergence, CSR-vector and ELL workload imbalance, and power-law tile row lengths.These observations motivate the composite representation and its workload partitioning strategy.
  • 3.1 Single-GPU SpMV: Composite tile storage ranks rows by length and packs them into approximately balanced workloads, combining CSR and ELL formats for power-law row distributions.The scheme applies to dense tiles and can also represent sparse sub-matrices whose row lengths follow a power-law distribution.
  • 3.3 Automatic Parameter Tuning: A performance model automatically selects viable tiling and workload parameters using offline kernel benchmarks and online input-matrix distributions.This removes the need to manually tune the number of tiles and partitioning strategy.

4. EXPERIMENTS

Experiments evaluate the proposed kernels on SpMV and graph-mining workloads, including single-GPU power-law matrices, PageRank, multi-GPU web graphs, and runtime auto-tuning. The methods generally outperform NVIDIA’s GPU baselines, scale across GPUs, and select near-optimal parameters.

  • Single-GPU SpMV Kernel: 1.95x average speedup over NVIDIA’s HYB kernel on Flickr, LiveJournal, and Wikipedia, with smaller gains of 13% on Webbase and 36% on Youtube.The proposed tile-composite kernel dominates the compared kernels most clearly on the larger power-law matrices.
  • Graph Mining Applications: About 2x speedup over COO and HYB for PageRank on Flickr, LiveJournal, and Wikipedia, while improvements on Youtube are marginal.Similar results are reported for HITS and Random Walk with Restart.
  • Multi-GPU PageRank on Web Graphs: About 23G-FLOPS with 70% parallel efficiency on sk-2005 using 10 GPUs, while speedup eventually flattens as communication overhead dominates.On smaller datasets, the Tile-Composite kernel reaches about 80% efficiency with 4 GPUs and 60% with 6 GPUs.
  • Parameter Auto-tuning: Auto-tuning matches exhaustive-search performance on Webbase and Wikipedia and remains within 3% of optimal on the other datasets.The parameter search selects tile counts and partitioning strategies using the performance model.
  • Parameter Auto-tuning: Predicted absolute performance is within roughly 20% of measured performance, with error attributed to average-warp estimates and synthetic benchmark shapes.The authors state that relative performance accuracy is sufficient for selecting parameters automatically.

5. DISCUSSION

The discussion explains where the optimizations generalize beyond power-law matrices and where their benefits depend on matrix structure. Tiling offers the strongest structural advantage for power-law distributions, while composite storage and performance modeling have broader applicability with stated constraints.

  • Tiling: Tiling is most beneficial when nonzeros concentrate in early dense columns, a pattern that includes power-law matrices.The greedy heuristic starts with densest columns so much of the computation can finish without extra cost for sparse columns.
  • Tiling: Tile-COO consistently outperforms COO on power-law matrices, but its advantage on non-power-law matrices is very marginal.The comparison is attributed specifically to the tiling optimization.
  • Composite Storage: The tile-composite kernel outperforms tile-COO on both power-law and non-power-law matrices, although padded zeros create memory overhead.Composite storage combines CSR and ELL storage and pads workloads to warp size.
  • Performance Modeling: The performance model does not rely on the power-law property and can predict tile-composite performance for arbitrary matrices on the same hardware.The model needs to be built once for a given hardware platform before large-scale experiments.

6. CONCLUSIONS

The paper presents architecture-conscious SpMV optimizations for GPU graph mining, extending them to web graphs on MPI-based clusters. Its best kernel improves performance over GPU and CPU baselines while using a performance model for automatic parameter tuning.

  • 6. CONCLUSIONS: 1.8 to 2.1 times faster than an industrial-strength GPU competitor and 18 to 32 times faster than a similar CPU implementation, across PageRank, Random Walk with Restart, and HITS.The reported comparison covers the graph-mining algorithms evaluated with the optimized kernels.
  • 6. CONCLUSIONS: The optimizations improve GPU SpMV by combining architecture-aware processing with tiling and composite representation for power-law graphs.The approach targets both GPU architectural features and graph characteristics.
  • 6. CONCLUSIONS: A performance model automatically tunes the tile-composite parameters, reducing reliance on manual parameter tuning.The conclusion identifies careful tuning as important to achieving high performance.
  • 6. CONCLUSIONS: The authors extend the optimizations to web graphs that cannot fit on one GPU using an MPI-based cluster.This extension addresses larger web graphs through distributed processing.

A. GPU BACKGROUND

CUDA GPUs organize computation across streaming multiprocessors and thread blocks, with a memory hierarchy that affects data access. The section introduces the hardware and memory organization relevant to GPU kernel design.

  • A. GPU BACKGROUND: The section uses Figure 6 to describe CUDA hardware organization and its memory hierarchy.The supplied table passage only identifies a separate matrix-and-graph dataset table and does not add hardware details.
  • A. GPU BACKGROUND: CUDA devices consist of streaming multiprocessors containing streaming processors, while programs partition parallel work into grids of thread blocks.Thread blocks are distributed across multiprocessors, and warps execute groups of 32 concurrent threads.
  • A. GPU BACKGROUND: Global memory is visible to all device threads but has high access latency, making memory access organization important for performance.Memory requests from half warps are served together using fixed-size global-memory segments.

B. NVIDIA’S SPMV LIBRARY

NVIDIA’s SpMV library provides several sparse matrix formats and kernels, each with different assumptions about row structure and memory access. Some formats are unsuitable for the power-law graph matrices studied here.

  • B. NVIDIA’S SPMV LIBRARY: CSR stores row nonzeros contiguously with column indices and row pointers, assigning one matrix row to each thread.The CSR kernel is the baseline format described for sparse matrix-vector multiplication.
  • B. NVIDIA’S SPMV LIBRARY: COO handles variable row lengths but uses segmented reduction, where synchronization and warp divergence can occur.ELL instead bounds row lengths and stores a dense n by k representation in column-major order for efficient global-memory access.
  • B. NVIDIA’S SPMV LIBRARY: NVIDIA’s HYB kernel combines ELL with COO, while DIA and PKT impose additional structural requirements and cannot run on the studied power-law matrices.DIA targets banded matrices, whereas PKT clusters nonzeros into dense sub-blocks processed from shared memory.

C. DATASET AND HARDWARE DETAIL

The experiments use real web and unstructured matrix datasets on CPU and GPU systems in an MPI-based cluster. The web graphs exhibit power-law structure and include both single- and multi-GPU settings.

  • DATASET AND HARDWARE DETAIL: The single-GPU evaluation uses Flickr, LiveJournal, YouTube, and Wikipedia web graphs, all described as having power-law characteristics.Six unstructured matrix datasets are also included, including one dense 2000 by 2000 matrix as a bandwidth benchmark.
  • DATASET AND HARDWARE DETAIL: The cluster nodes use Opteron X2 2218 CPUs with 8 GB of memory and two NVIDIA Tesla C1060 GPUs per node.Each Tesla C1060 has 30 multiprocessors, 240 processing cores, and 4 GB of global memory.
  • DATASET AND HARDWARE DETAIL: Single-GPU experiments use one node and one GPU, whereas multi-GPU experiments use multiple nodes with one GPU per node.The GPU code uses CUDA 3.0 and the CPU code uses GCC 4.1.2.

D. PERFORMANCE ON UNSTRUCTURED MATRIXANDCOMPARISONWITHCPU

On non-power-law matrices, no single SpMV kernel dominates across datasets, although the proposed tiling with composite storage is competitive and can excel on dense inputs. GPU kernels generally outperform the CPU implementation, except for the GPU CSR kernel on dense data.

  • Performance on Unstructured Matrix Data: No single kernel outperforms all others across the evaluated non-power-law matrices.The proposed methods compare favorably on some kernels but do not consistently perform as strongly as the best alternative.
  • Performance on Unstructured Matrix Data: 17.57 GFLOPS and 105.5 GB/s make the tiling with composite storage kernel best on the 2000 by 2000 dense matrix.Its bandwidth exceeds NVIDIA’s specified 102 GB/s peak, attributed to texture-cache fetching of vector x.
  • Performance on Unstructured Matrix Data: The proposed kernel is 10.5% slower than HYB on Circuit and remains among the top four in speed and bandwidth on all four non-power-law matrices.Baskaran and Bordawekar’s CSR is best on FEM/Harbor and Protein, while HYB is best on Circuit and LP.
  • Performance on Unstructured Matrix Data: Balanced nonzero distributions limit the proposed methods because dense-matrix tiling adds overhead without enough performance benefit.The methods exploit skewed power-law structure, which is weaker in these matrices.
  • Comparison with CPU: GPU kernels achieve speedups ranging from 2.05x to 37.31x over the CPU kernel in all settings except dense-matrix GPU CSR.The GPU CSR kernel is slower than the CPU kernel on dense data, while GPU kernels significantly outperform CPU in almost all other settings.

E. AUTOTUNING PSEUDOCODE

The auto-tuning procedure determines tile count and partition sizes from matrix structure, then selects each tile’s workload using a performance model. It searches feasible workload sizes and returns the predicted best choice.

  • Algorithm 1 Tile-Composite Kernel Auto-tuning: The tile auto-tuner sorts the matrix by column lengths, processes fixed-width 64K-column groups, and returns the number of tiles and partition sizes.It stops when the next tile begins with a column of length at most one.
  • Algorithm 2 Partition(T): For each tile, partition tuning searches workload sizes from the shortest row length to the maximum active-warp bound.Candidate sizes increase by the shortest row length.
  • Algorithm 2 Partition(T): The performance model evaluates every feasible workload size and returns the size with minimum predicted time.The algorithm also returns the corresponding optimal modeled time.

F. GRAPH MINING ALGORITHMS

PageRank, HITS, and Random Walk with Restart repeatedly apply SpMV-based power iterations to graph-derived matrices, whose power-law structure creates GPU load-balancing and memory-efficiency challenges. The paper models these workloads with tile-level performance estimation and reports substantial GPU advantages over CPU implementations.

  • Performance Modeling: The performance-modeling procedure estimates total tile runtime by partitioning rows across workloads, aggregating modeled performance, and returning total time.It accounts for padding and accumulates per-partition time across the tile.
  • Motivation: Power-law graph matrices create skewed row and column nonzero distributions, causing poor GPU load balancing and inefficient memory access.The affected algorithms repeatedly use SpMV within iterative computations, making the kernel’s running time dominant within each power-method iteration.
  • PageRank: PageRank iteratively updates its vector using the row-normalized adjacency matrix with damping factor c=0.85 until convergence.The initial vector is uniform with each element equal to 1/n.
  • HITS: HITS assigns authority and hub scores through recursive matrix-vector products, which are rewritten as one matrix-vector multiplication for power-method computation.Each implementation iteration includes one SpMV, normalization operations, and convergence checking.
  • HITS: 17x to 29x GPU speedups over CPU are observed for the HITS implementations.The comparison reports total running time after the GPU optimizations.
  • Random Walk with Restart: RWR computes query-node relevance with a restart probability of 0.9 using matrix-vector multiplication, vector addition, and convergence checking.The implementation uses GPU SpMV, parallel reduction, and vector addition kernels.
Loading 1103.2405v1…