Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Efficient Sparse Matrix Kernels based on Adaptive Workload-Balancing and
  Parallel-Reduction   Sparse matrix-vector and matrix-matrix multiplication (SpMV and SpMM) are
fundamental in both conventional (graph analytics, scientific computing) and
emerging (sparse DNN, GNN) domains. Workload-balancing and parallel-reduction
are widely-used design principles for efficient SpMV. However, prior work fails
to resolve how to implement and adaptively use the two principles for SpMV/MM.
To overcome this obstacle, we first complete the implementation space with
optimizations by filling three missing pieces in prior work, including: (1) We
show that workload-balancing and parallel-reduction can be combined through a
segment-reduction algorithm implemented with SIMD-shuffle primitives. (2) We
show that parallel-reduction can be implemented in SpMM through loading the
dense-matrix rows with vector memory operations. (3) We show that vectorized
loading of sparse rows, being a part of the benefit of parallel-reduction, can
co-exist with sequential-reduction in SpMM through temporally caching
sparse-matrix elements in the shared memory. In terms of adaptive use, we
analyze how the benefit of two principles change with two characteristics from
the input data space: the diverse sparsity pattern and dense-matrix width. We
find the benefit of the two principles fades along with the increased total
workload, i.e. the increased dense-matrix width. We also identify, for SpMV and
SpMM, different sparse-matrix features that impact workload-balancing
effectiveness. Our design consistently exceeds cuSPARSE by 1.07-1.57x on
different GPUs and dense matrix width, and the kernel selection rules involve
5-12% performance loss compared with optimal choices. Our kernel is being
integrated into popular graph learning frameworks to accelerate GNN training.

29
The categories of this paper are: funct-an
18
The categories of this paper are: econ
3
The categories of this paper are: physics
14
The categories of this paper are: math-ph
4
The categories of this paper are: cond-mat
22
The categories of this paper are: chao-dyn
24
The categories of this paper are: dg-ga
15
The categories of this paper are: nucl-ex
12
The categories of this paper are: nucl-th
35
The categories of this paper are: mtrl-th
32
The categories of this paper are: atom-ph
8
The categories of this paper are: hep-ex
36
The categories of this paper are: cmp-lg
34
The categories of this paper are: chem-ph
19
The categories of this paper are: eess
6
The categories of this paper are: astro-ph