Bandwidth-Optimized Parallel Algorithms for Sparse Matrix-Matrix Multiplication using Propagation Blocking

Symposium on Parallelism in Algorithms and Architectures (SPAA)


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 the outer product. 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.

Related Publications

All Publications

NeurIPS - December 16, 2020

Online Bayesian Persuasion

Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Nicola Gatti

WINE - December 7, 2020

The Ad Types Problem

Riccardo Colini Baldeschi, Julian Mestre, Okke Schrijvers, Christopher A. Wilkens

NBER - September 30, 2020

The Effects of COVID-19 on U.S. Small Businesses: Evidence from Owners, Managers, and Employees

Georgij Alekseev, Safaa Amer, Manasa Gopal, Theresa Kuchler, JW Schneider, Johannes Stroebel, Nils Wernerfelt

The Web Conference - April 30, 2020

Envy, Regret, and Social Welfare Loss

Riccardo Colini Baldeschi, Stefano Leonardi, Okke Schrijvers, Eric Sodomka

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookies Policy