PaperlayerView exact revision on arXiv

Source-linked AI summary

CSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector Multiplication

Weifeng Liu, Brian Vinter

arXiv:1503.05032v2cs.MScs.DCmath.NA

TL;DR

SpMV requires high-throughput execution across matrix structures and platforms, while existing formats face conversion costs and uneven performance. The paper introduces CSR5, a structure-insensitive tiled format with low-overhead conversion and a redesigned segmented-sum algorithm. Across four platforms, CSR5 matches or exceeds prior work on regular matrices and substantially improves performance on irregular ones.

  • Problem

    SpMV performance depends on specialized formats, but structure-dependent conversion costs and differing weaknesses on regular and irregular matrices limit a single practical approach.

  • Method

    CSR5 extends CSR with evenly partitioned 2D tiles, auxiliary descriptors, two tuning parameters, and a redesigned low-overhead segmented-sum SpMV algorithm.

  • Results

    CSR5 delivers comparable or better performance on 14 regular matrices and average improvements of 17.6%, 28.5%, 173.0% and 293.3% on 10 irregular matrices across four platforms.

  • Takeaways & Limitations

    CSR5 provides high throughput in isolated and iteration-based scenarios, with fast conversion making it practical for real-world applications with only tens of iterations.

  • Takeaways & Limitations

    Segmented-sum approaches can incur performance overhead from global synchronizations and memory accesses, while row-block approaches can suffer load imbalance.

Abstract

from arXiv · show

Sparse matrix-vector multiplication (SpMV) is a fundamental building block for numerous applications. In this paper, we propose CSR5 (Compressed Sparse Row 5), a new storage format, which offers high-throughput SpMV on various platforms including CPUs, GPUs and Xeon Phi. First, the CSR5 format is insensitive to the sparsity structure of the input matrix. Thus the single format can support an SpMV algorithm that is efficient both for regular matrices and for irregular matrices. Furthermore, we show that the overhead of the format conversion from the CSR to the CSR5 can be as low as the cost of a few SpMV operations. We compare the CSR5-based SpMV algorithm with 11 state-of-the-art formats and algorithms on four mainstream processors using 14 regular and 10 irregular matrices as a benchmark suite. For the 14 regular matrices in the suite, we achieve comparable or better performance over the previous work. For the 10 irregular matrices, the CSR5 obtains average performance improvement of 17.6\%, 28.5\%, 173.0\% and 293.3\% (up to 213.3\%, 153.6\%, 405.1\% and 943.3\%) over the best existing work on dual-socket Intel CPUs, an nVidia GPU, an AMD GPU and an Intel Xeon Phi, respectively. For real-world applications such as a solver with only tens of iterations, the CSR5 format can be more practical because of its low-overhead for format conversion. The source code of this work is downloadable at https://github.com/bhSPARSE/Benchmark_SpMV_using_CSR5

1. INTRODUCTION

SpMV needs specialized storage formats and algorithms for high performance, but structure-dependent conversion and differing behavior across matrix types complicate practical deployment. CSR5 addresses these constraints with low-overhead conversion and stable performance across regular and irregular matrices.

  • SpMV multiplies a sparse m×n matrix by a dense n-dimensional vector to produce a dense m-dimensional vector.
  • Structure-dependent parameter tuning makes format conversion expensive, while hybrid formats may require different partitioning parameters for different matrices.
  • Row block methods can suffer load imbalance on irregular matrices, whereas segmented sum methods incur synchronization and global memory-access overhead.
  • An efficient format should avoid structure-dependent tuning and support fast SpMV on both regular and irregular matrices.
  • CSR5 extends CSR with tile-transposed storage and auxiliary information, using hardware-dependent and structure-independent sparsity parameters for conversion.
  • CSR5 uses a redesigned low-overhead segmented sum algorithm and is evaluated on four devices in isolated and iteration-based SpMV scenarios.The evaluation compares CSR5 with 11 state-of-the-art formats and algorithms.
  • 17.6%, 28.5%, 173.0% and 293.3% average improvement is reported for 10 irregular matrices over the second-best work across four platforms.For 14 regular matrices, CSR5 delivers comparable or better performance than previous work.

2. PRELIMINARIES

SpMV uses sparse matrix storage and parallel algorithms to compute dense outputs, but CSR-based approaches face load-balance and synchronization trade-offs. Segmented-sum methods improve balance, while CSR5 combines segmented-sum parallelism with compressed row storage to improve efficiency.

  • The CSR Format: CSR stores row pointers, column indices, and nonzero values for sparse matrices.The row_ptr array has size m + 1, while col_idx and val each have size nnz.
  • Row Block Methods: CSR-scalar and CSR-vector parallelize SpMV over independent row blocks, using scalar or SIMD reductions respectively.Each processing unit computes dot products for assigned rows and writes results to y.
  • Row Block Methods: Uneven row lengths cause load imbalance in CSR row-block methods, leaving processing cores idle and limiting scalability.Existing strategies mitigate but do not fundamentally solve this problem.
  • Segmented Sum Methods: Segmented-sum CSR SpMV generates row flags, computes entry-wise products, reduces each row segment, and writes row results to y.The method uses auxiliary arrays bit_flag and product, each associated with the nnz nonzeros.
  • Segmented Sum Methods: Nearly perfect load balance does not guarantee high performance because CSR segmented sum incurs scatter, gather, synchronization, and global-memory overheads.These costs can make cuSPARSE row-block SpMV outperform cuDPP segmented sum on relatively regular matrices.
  • CSR5: CSR5 combines segmented-sum load balance with compressed row data and achieves up to 4x speedup over CSR-based segmented-sum SpMV.Its storage includes row_ptr, tile_ptr, col_idx, val, and tile_desc.

3. THE CSR5 STORAGE FORMAT

CSR5 partitions nonzeros into fixed-size 2D tiles, integrates transposed CSR data with auxiliary metadata, and tunes only hardware- and sparsity-dependent parameters. Its metadata supports parallel partial-sum placement, segmented sums, empty-row correction, and fast conversion back to CSR.

  • 3.1 Basic Data Layout: CSR5 evenly partitions nonzero entries into equal-sized 2D tiles, using width ω and height σ as its only tuning parameters.The tile width matches the processor’s SIMD execution unit, while tile height is selected using hardware and, on GPUs, average nonzeros per row.
  • 3.1 Basic Data Layout: CSR5 integrates CSR arrays while storing complete tiles’ col_idx and val in tile-level column-major order for contiguous SIMD memory access.The format retains row_ptr and adds tile_ptr and tile_desc; incomplete tiles do not receive tile descriptors.
  • 3.2 Auto-Tuned Parameters ω and σ: ω is chosen from SIMD width, whereas σ accounts for cache, prefetching, and GPU nnz/row trade-offs between local work and output-write pressure.For double precision, the paper uses ω values of 4, 32, 64, and 8 on CPUs, nVidia GPUs, AMD GPUs, and Xeon Phi, respectively; σ is 16 on CPUs and 12 on Xeon Phi.
  • 3.2 Auto-Tuned Parameters ω and σ: The tuning time becomes negligible because ω and σ are easily obtained, reducing preprocessing time.Hardware-dependent bounds can be fixed for a processor, while future architectures can derive them from initialization benchmarks.
  • 3.3 Tile Pointer Information: tile_ptr records each tile’s first matrix-row index, enabling tiles to locate partial-sum destinations and execute in parallel.The array has p + 1 entries, with p = ⌈nnz/(ωσ)⌉, and is built by binary-searching tile boundaries in row_ptr.
  • 3.4 Tile Descriptor Information: CSR5 tile descriptors combine bit_flag, y_offset, seg_offset, and empty_offset to identify row starts, partial-sum destinations, local segments, and empty-row corrections.empty_offset is used only for tiles containing empty rows, whose row-pointer ambiguity can otherwise misplace partial sums.
  • 3.4 Tile Descriptor Information: seg_offset converts local segmented sums into an inclusive prefix-sum scan followed by arithmetic operations, using a SIMD-friendly primitive.This auxiliary array supplies distances between segment heads and tails so partial sums can be deduced from scan results.
  • 3.6 The CSR5 for Other Matrix Operations: CSR5-to-CSR conversion removes tile metadata and transposes col_idx and val back to row-major order, while direct CSR-compatible accesses remain possible.Because CSR5 is a superset of CSR, slight changes or entry accesses can be performed without conversion.

4. THE CSR5-BASED SPMV ALGORITHM

The CSR5 SpMV algorithm assigns independent tiles and their columns to processor execution units, computes local products, and combines partial segments as needed. Complete segments write directly to y, while boundary segments use segmented sums, atomics, or reductions.

  • Tile Execution: Independent tiles execute concurrently, with warps or wavefronts assigned on GPUs and OpenMP-assigned tiles on CPUs and Xeon Phi.Columns within each tile are likewise mapped to GPU threads or x86 SIMD lanes.
  • Segment Classification: Each tile column classifies local segments as red, green, or blue according to whether they are unsealed at the top, complete, or unsealed at the bottom.A column unsealed at both ends is classified as red.
  • Partial-Sum Accumulation: Green segments write partial sums directly to y, whereas red and blue sub-segments require an additional segmented sum before off-chip storage.The extra sum combines contributions from sub-segments belonging to the same matrix row.
  • Tile Synchronization: First and last tile segments use atomic adds, or device-level auxiliary reductions, when concurrent tiles contribute to the same matrix row.This synchronization handles rows influenced by multiple 2D tiles running concurrently.
  • Incomplete Tile Handling: Incomplete trailing entries fall back to conventional CSR-vector processing after all complete tiles are consumed.The incomplete tile needs no tile_desc because it obtains its starting position from tile_ptr.
  • Fast Segmented Sum: The main CSR5 computation uses basic arithmetic and logic, while its most complex operation is the fast segmented sum based on prefix-sum scans.Prefix-sum scans are efficient on CUDA, OpenCL, and x86 SIMD implementations.

5. EXPERIMENTAL RESULTS

The experiments evaluate CSR5 against 11 state-of-the-art formats and algorithms across four platforms and 24 matrices divided into regular and irregular groups. CSR5 is competitive on regular matrices, substantially faster on irregular matrices, and retains an advantage when preprocessing cost is included.

  • 5.1 Experimental Setup: The evaluation uses double-precision SpMV on dual-socket Intel CPUs, an nVidia GPU, an AMD GPU, and an Intel Xeon Phi.Each participating method is evaluated 10 times, with each trial containing 1000 runs; the best observed result is reported.
  • 5.2 Benchmark Suite: The benchmark suite contains 24 matrices, classified as 14 regular and 10 irregular according to row-length statistics.The irregular matrix dc2 has a 114K-entry longest row, representing 15% of a matrix with 117K rows.
  • 5.3 Isolated SpMV Performance: CSR5 delivers better performance on the two GPUs and comparable performance on the two x86 platforms for the 14 regular matrices.On the Xeon Phi, Intel MKL and ESB outperform CSR5 because vector-x gathering latency is a bottleneck, while ESB benefits from column-based reordering or partitioning.
  • 5.4 Effects of Auto-Tuning: CSR5’s auto-tuned GPU parameter σ incurs average performance losses of -4.2% on nVidia GPUs and -2.5% on AMD GPUs versus the best σ from 4 to 48.The auto-tuned parameter does not show obvious performance loss relative to selecting the best tested value.
  • 5.6 Iteration-Based Scenarios: CSR5 achieves the highest overall speedups in the iteration-based scenarios with n = 50 and n = 500, and is the only format faster than CSR for 50 iterations on all platforms.The comparison includes preprocessing and SpMV execution costs against the fastest CSR-based implementation on each platform.

6. RELATED WORK

Prior SpMV formats and algorithms specialize in block structure, irregular matrices, row blocking, or segmented sums, often creating performance or conversion trade-offs. CSR5 instead targets high-throughput SpMV across regular and irregular matrices and across CPUs, GPUs, and Xeon Phi.

  • Block-Based Formats: Block-based formats exploit natural substructures and can reduce off-chip loads, but they are less suitable for matrices without block structure.Their effectiveness depends on matrix characteristics rather than applying uniformly across inputs.
  • Hybrid Formats: Hybrid formats such as HYB target irregular matrices but incur kernel-launch and cache costs, may fail to saturate devices, and complicate operations requiring a single matrix representation.Partitioning the input into multiple parts can make relatively simple operations such as triangular solves more complex.
  • Row Block Methods: Row block methods perform well for either regular or irregular matrices, whereas CSR5 is reported to deliver higher throughput for both.This contrasts with the specialization of earlier row-block approaches.
  • Segmented Sum Methods: Segmented sum methods require COO-like formats, while CSR5 retains row-index information compactly to support efficient conversion and SpMV.The comparison highlights a representation trade-off between segmented-sum execution and CSR5’s compact row information.
  • Automatic Format Selection: CSR5 can simplify format selection because its performance is insensitive to the input matrix’s sparsity structure.This contrasts with machine-learning classifiers designed to select the best format for a matrix and target GPU.
  • Cross-Platform Support: CSR5 is presented as the only format supporting high-throughput cross-platform SpMV on CPUs, nVidia GPUs, AMD GPUs, and Xeon Phi simultaneously.The paper states that this may simplify scientific-software development for processors with massive on-chip parallelism.

7. CONCLUSIONS

CSR5 is designed for efficient cross-platform SpMV on CPUs, GPUs, and Xeon Phi. Its conversion is fast and its redesigned segmented-sum algorithm improves SIMD utilization, supporting high throughput in isolated and iterative tests.

  • CSR5 targets efficient cross-platform SpMV on CPUs, GPUs, and Xeon Phi.
  • Fast CSR-to-CSR5 conversion follows from CSR5’s insensitivity to input sparsity structure.
  • A redesigned segmented-sum algorithm increases SIMD utilization compared with classic methods.
  • CSR5 delivers high throughput in isolated SpMV tests and iteration-based scenarios.
Loading 1503.05032v2…