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

Sammanfattning

Compressed Matrix Multiplication (CMM), introduced by Rasmus Pagh in 2013,is an approximation algorithm for computing matrix products where the result osdominated by a small number of large entries. The algorithm decomposed the matrixproduct into a sum of outer products, where each outer product is independentlycompressed 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 surpassthe performance of standard General Matrix Multiplication, specifically NVIDIA’scuBLAS.To evaluate this, we developed a implementation of Pagh’s Compressed MatrixMultiplication on the GPU using the CUDA platform. This implementation wasbenchmarked against the cuBLASXt library using dense matrices of sizes 210 to217 with result matrices with few elements impacting the Frobenius norm. Thebenchmarking results demonstrate that it was able to surpass cuBLAS with amaximum recorded speedup of 60.38 on generated matrices tailored for CMM. Thissuggests that Pagh’s algorithm can be useful on massively parallel hardware forcertain matrices and that further work should be pursued to realize more concreteimplementations.