  This paper is the first to assess the state of existing sparse matrix
multiplication algorithms on GPU for the butterfly structure, a promising form
of sparsity. This is achieved through a comprehensive benchmark that can be
easily modified to add a new implementation. The goal is to provide a simple
tool for users to select the optimal implementation based on their settings.
Using this benchmark, we find that existing implementations spend up to 50% of
their total runtime on memory rewriting operations. We show that these memory
operations can be optimized by introducing a new CUDA kernel that minimizes the
transfers between the different levels of GPU memory, achieving a median
speed-up factor of x1.4 while also reducing energy consumption (median of
x0.85). We also demonstrate the broader significance of our results by showing
how the new kernel can speed up the inference of neural networks.
