  General sparse matrix-matrix multiplication (SpGEMM) is a fundamental
building block for numerous applications such as algebraic multigrid method
(AMG), breadth first search and shortest path problem. Compared to other sparse
BLAS routines, an efficient parallel SpGEMM implementation has to handle extra
irregularity from three aspects: (1) the number of nonzero entries in the
resulting sparse matrix is unknown in advance, (2) very expensive parallel
insert operations at random positions in the resulting sparse matrix dominate
the execution time, and (3) load balancing must account for sparse data in both
input matrices.
  In this work we propose a framework for SpGEMM on GPUs and emerging CPU-GPU
heterogeneous processors. This framework particularly focuses on the above
three problems. Memory pre-allocation for the resulting matrix is organized by
a hybrid method that saves a large amount of global memory space and
efficiently utilizes the very limited on-chip scratchpad memory. Parallel
insert operations of the nonzero entries are implemented through the GPU merge
path algorithm that is experimentally found to be the fastest GPU merge
approach. Load balancing builds on the number of necessary arithmetic
operations on the nonzero entries and is guaranteed in all stages.
  Compared with the state-of-the-art CPU and GPU SpGEMM methods, our approach
delivers excellent absolute performance and relative speedups on various
benchmarks multiplying matrices with diverse sparsity structures. Furthermore,
on heterogeneous processors, our SpGEMM approach achieves higher throughput by
using re-allocatable shared virtual memory.
  The source code of this work is available at
https://github.com/bhSPARSE/Benchmark_SpGEMM_using_CSR
