PaperlayerView exact revision on arXiv

Source-linked AI summary

Design Principles for Sparse Matrix Multiplication on the GPU

Carl Yang, Aydin Buluc, John D. Owens

arXiv:1803.08601v2cs.DC

TL;DR

SpMM workloads on GPUs face uneven sparse-row lengths, while alternate sparse formats can require costly conversions. This paper implements CSR-based GPU algorithms combining load balancing and coalesced memory access. Across 157 SuiteSparse datasets, they achieve 31.7% geomean speed-up and up to 4.1x speed-up over state-of-the-art SpMM implementations.

  • Problem

    CSR-based SpMM must handle widely varying sparse-row lengths, while deviating from CSR can incur conversion and extra-storage costs.

    Source: §1 · p. 2, §2.2 · p. 3

  • Method

    The paper implements GPU SpMM algorithms using CSR, including merge-based load balancing and memory access patterns that coalesce accesses across matrices.

    Source: §1 · p. 2, §4.2 · p. 10, §6 · p. 13

  • Results

    31.7% geomean speed-up and up to 4.1x speed-up over state-of-the-art SpMM implementations were achieved across 157 SuiteSparse datasets.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The CSR-based approach avoids substantial format-conversion costs associated with using alternate formats for SpMM.

    Source: §1 · p. 2, §2.2 · p. 3

    The impact of the improved SpMM kernels on application codes remains for future investigation.

    Source: §6 · p. 14

Abstract

from arXiv · show

We implement two novel algorithms for sparse-matrix dense-matrix multiplication (SpMM) on the GPU. Our algorithms expect the sparse input in the popular compressed-sparse-row (CSR) format and thus do not require expensive format conversion. While previous SpMM work concentrates on thread-level parallelism, we additionally focus on latency hiding with instruction-level parallelism and load-balancing. We show, both theoretically and experimentally, that the proposed SpMM is a better fit for the GPU than previous approaches. We identify a key memory access pattern that allows efficient access into both input and output matrices that is crucial to getting excellent performance on SpMM. By combining these two ingredients---(i) merge-based load-balancing and (ii) row-major coalesced memory access---we demonstrate a 4.1x peak speedup and a 31.7% geomean speedup over state-of-the-art SpMM implementations on real-world datasets.

1 Introduction

SpMM organizes computation in applications including machine learning, data analysis, and graph analysis. The paper develops CSR-based GPU algorithms to address variable row lengths and reports improved performance over state-of-the-art implementations.

1 Introduction

  • SpMM is a computational primitive for applications including pruned neural-network inference, graph centrality, shortest paths, and iterative solvers.Source: §1 · p. 1
  • The proposed algorithms use CSR to avoid substantial format-conversion costs, while addressing the challenge of sparse rows with widely varying nonzero counts.Source: §1 · p. 2
  • 31.7% geomean speed-up and up to 4.1x speed-up over state-of-the-art SpMM implementations were achieved across 157 SuiteSparse datasets.Source: §1 · p. 2
  • The contributions include GPU implementations of row-splitting and merge-based algorithms, plus a heuristic that selects between kernels with 99.3% accuracy compared to optimal.Source: §1 · p. 2

2 Background & Preliminaries

Irregular GPU computations benefit from coalesced memory access, low warp divergence, and high occupancy. Sparse-matrix formats and dense-matrix layouts affect these behaviors, while non-CSR formats can add conversion and storage costs.

2.1 GPUs

  • Irregular GPU kernels need coalesced external-memory access, limited warp divergence, and high occupancy for good performance.Source: §2.1 · p. 2

2.2 Sparse matrix formats and SpMM

  • CSR stores nonzero values and column indices with row pointers, while row-major and column-major layouts place successive dense-matrix elements contiguously by row or column.Source: §2.2 · pp. 2–3
  • Prior SpMM approaches include specialized formats such as ELLPACK-R and SELL-P, and dynamic heavy/light-row processing with CSR and DCSR.Source: §2.2 · p. 3
  • Using a non-CSR format may require conversion before and after SpMM and additional memory for a second matrix copy.Source: §2.2 · p. 3

3 Design Principles

The paper frames irregular GPU performance around latency hiding and load balancing. It emphasizes balancing thread- and instruction-level parallelism while assigning work to avoid idle resources and inefficient memory access.

3 Design Principles

  • Good irregular-GPU performance calls for both effective latency hiding through TLP and ILP and efficient load balancing.Source: §3 · p. 3

3.1 Latency hiding with TLP and ILP

  • ILP exposes independent memory operations by assigning multiple tasks to a thread, but it competes with TLP for a fixed register supply.Source: §3.1 · p. 4

3.2 Load-balancing

  • Type 1 imbalance leaves some warps or CTAs underloaded while others remain busy; Type 2 imbalance wastes threads through insufficient work or divergence.Source: §3.2 · p. 4
  • The synthetic benchmark examines cuSPARSE performance across matrix dimensions alongside SpMM occupancy and warp efficiency, with long-row under-splitting and short-row over-allocation marking different imbalance extremes.Source: §3.2 · pp. 4–5, Figure 1 · p. 5

4 Parallelizations of CSR SpMM

The section extends CSR SpMV parallelizations to SpMM, balancing row-level simplicity against explicit nonzero load distribution while preserving coalesced access to dense B.

4 Parallelizations of CSR SpMM

  • CSR SpMM draws on row split, nonzero split, and merge path; nonzero split and merge path explicitly rebalance work and link balanced work to per-thread ILP.Merge path uses a two-dimensional search over row offsets and nonzero indices, whereas nonzero split uses a one-dimensional search on row offsets.Source: §4 · p. 5
  • Because merge path is harder to implement and assumes C writes cost like A and B reads, the authors extend Baxter's nonzero split as merge-based SpMM.The authors also note that merge path addresses matrices with infinitely many empty rows.Source: §4 · p. 6

4.1 Algorithm I: Row-splitting SpMM

  • Row splitting assigns each row to a thread, warp, or CTA; the authors choose one warp per row for simple design and coalesced B accesses.For matrices with few nonzeroes per row, assigning a thread per matrix row may be more efficient.Source: §4.1 · p. 6
  • Assigning threads to B columns enables 32 independent instructions and coalesced accesses when B is row-major, while row lengths not divisible by 32 can require dummy work.The authors note that batches of 32 amortize this overhead for very long rows.Source: §4.1 · p. 7

4.2 Algorithm II: Merge-based SpMM

  • Merge-based SpMM distributes nonzero work across threads, determines CTA starting rows in a partition phase, then broadcasts B values for coalesced access.The algorithm computes partial C values and fixes carry-outs for rows that span CTA boundaries.Source: §4.2 · pp. 8–9
  • Merge-based SpMM adds a kernel to find block starting rows and global carry-out writes; their overhead trades off against coalescing, with 32 columns per CTA performing better than 4.The carry-out overhead scales with the number of B columns.Source: §4.2 · pp. 9–10

5 Experimental Results

The experiments compare the proposed GPU SpMM kernels across row-length regimes and SuiteSparse matrices. A mean-row-length heuristic combines their complementary performance into an overall improvement over cuSPARSE.

5.1 Experimental Setup

  • Experiments ran on an NVIDIA K40c, and all results exclude disk-to-memory and CPU-to-GPU transfer times.The 157 SuiteSparse datasets were a random sample; the microbenchmark also varied row counts and nonzeroes per row.Source: §5.1 · p. 10

5.2 Algorithm I: Row-split

  • 30.8% geomean speed-up over the next-fastest implementation and 39% peak improvement were reported on 10 long-row datasets.For a 128-by-131072 matrix, executed instructions per cycle improved 102%. Transpose-configuration texture loads underperformed cuSPARSE on average, while column-major output writes cost up to 3–4 GFlops and shuffle broadcast saved shared memory.Source: §5.2 · pp. 10–11, Figure 5 · p. 12

5.3 Algorithm II: Merge-based

  • 53% geomean speed-up over cuSPARSE csrmm2 and 237% peak improvement were reported for the merge-based kernel on short-row datasets.Allocating more rows to a CTA handles short-row imbalance. Merge path adds overhead, and its SpMM ILP advantage is less assured because T must remain 1 to control register use.Source: §5.3 · pp. 11–12, Figure 5 · p. 12

5.4 Heuristic

  • 31.7% geomean speed-up and up to 4.1× peak speed-up over cuSPARSE csrmm2 were achieved with the heuristic.Figure 6 compares the proposed kernels with cuSPARSE csrmm2 across SuiteSparse matrices.Source: Figure 6 · p. 13, §5.4 · p. 13
  • 99.3% oracle-choice accuracy came from switching kernels at a mean row length of 9.35.Individually, row split yields a 13.2% geomean gain and merge-based a 21.5% slowdown against the fastest vendor-supplied SpMM; their advantages occur in separate irregularity regions.Source: §5.4 · pp. 12–13

6 Conclusion and Future Work

The authors report considerable performance improvement over vendor-supplied SpMM on a wide spectrum of graphs, and merge-based SpMM outperforms dense GEMM below 9% fill in their random-matrix experiment. They identify higher-density tiling, alternate formats, load-balancing libraries, and application-level evaluation as future directions.

6 Conclusion and Future Work

  • The authors report considerable performance improvement over vendor-supplied SpMM on a wide spectrum of graphs.They identify coalesced access into all three matrices as one key to performance.Source: §6 · p. 13
  • Below 9% fill, merge-based SpMM is faster than GEMM for a 100,000 × 100,000 random matrix multiplied by a 100,000 × 64 dense matrix.The sparse matrix is generated with a fixed percentage of nonzeroes in each row, with indices sampled without replacement.Source: §6 · p. 13, Figure 7 · p. 14
  • Above a hardware threshold of m/M nonzeroes per row, tiling A and B is expected to outperform the paper’s access pattern; whether it extends effectiveness beyond 9% sparsity remains open.Here, m is the sparse matrix’s row count and M is device fast-memory size.Source: §6 · pp. 13–14
  • The implementation uses CSR to avoid format-conversion costs, while whether GPUs suit CSB for irregular matrices remains unclear.CSB is designed for codes that multiply a sparse matrix and its transpose.Source: §6 · p. 14
  • Future work includes separating merge-path load-balancing from computation and evaluating application impact; the authors expect co-design to benefit applications more than kernel replacement.The current code tightly couples computation and load-balancing.Source: §6 · pp. 14–15
Loading 1803.08601v2…