Efficient GPU acceleration of Compressed Matrix Multiplication - Implementation and analysis of Pagh’s algorithm for compressed matrix multiplication on massively parallel hardware

Abstract

Compressed Matrix Multiplication (CMM), introduced by Rasmus Pagh in 2013, is an approximation algorithm for computing matrix products where the result os dominated by a small number of large entries. The algorithm decomposed the matrix product into a sum of outer products, where each outer product is independently compressed into polynomial coefficients. Since these are independent of one another, the algorithm is inherently highly parallelizable. The research path being approached is therefore focused on how Compressed Matrix Multiplication can utilize the massively parallel hardware of GPUs to surpass the performance of standard General Matrix Multiplication, specifically NVIDIA’s cuBLAS. To evaluate this, we developed a implementation of Pagh’s Compressed Matrix Multiplication on the GPU using the CUDA platform. This implementation was benchmarked against the cuBLASXt library using dense matrices of sizes 210 to 217 with result matrices with few elements impacting the Frobenius norm. The benchmarking results demonstrate that it was able to surpass cuBLAS with a maximum recorded speedup of 60.38 on generated matrices tailored for CMM. This suggests that Pagh’s algorithm can be useful on massively parallel hardware for certain matrices and that further work should be pursued to realize more concrete implementations.