  Sparse matrix-matrix multiplication (SpGEMM) is a widely used kernel in
various graph, scientific computing and machine learning algorithms. It is well
known that SpGEMM is a memory-bound operation, and its peak performance is
expected to be bound by the memory bandwidth. Yet, existing algorithms fail to
saturate the memory bandwidth, resulting in suboptimal performance under the
Roofline model. In this paper we characterize existing SpGEMM algorithms based
on their memory access patterns and develop practical lower and upper bounds
for SpGEMM performance. We then develop an SpGEMM algorithm based on outer
product matrix multiplication. The newly developed algorithm called PB-SpGEMM
saturates memory bandwidth by using the propagation blocking technique and by
performing in-cache sorting and merging. For many practical matrices, PB-SpGEMM
runs 20%-50% faster than the state-of-the-art heap and hash SpGEMM algorithms
on modern multicore processors. Most importantly, PB-SpGEMM attains performance
predicted by the Roofline model, and its performance remains stable with
respect to matrix size and sparsity.
