Accelerating Sparse Approximate Matrix Multiplication on GPUs

Abstract

Although the matrix multiplication plays a vital role in computational linear algebra, there are few efficient solutions for matrix multiplication of the near-sparse matrices. The Sparse Approximate Matrix Multiply (SpAMM) is one of the algorithms to fill the performance gap neglected by traditional optimizations for dense/sparse matrix multiplication. However, existing SpAMM algorithms fail to exploit the performance potential of GPUs for acceleration. In this paper, we present cuSpAMM, the first parallel SpAMM algorithm optimized for multiple GPUs. Several performance optimizations have been proposed, including algorithm re-design to adapt to the thread parallelism, blocking strategies for memory access optimization, and the acceleration with the tensor core. In addition, we scale cuSpAMM to run on multiple GPUs with an effective load balance scheme. We evaluate cuSpAMM on both synthesized and real-world datasets on multiple GPUs. The experiment results show that cuSpAMM achieves significant performance speedup compared to vendor optimized cuBLAS and cuSPARSE libraries.

References in corpus (13)

• Area laws for the entanglement entropy - a review
• O(N) methods in electronic structure calculations
• Exploring Modern GPU Memory System Design Challenges through Accurate Modeling
• NVIDIA Tensor Core Programmability, Performance & Precision
• Deep Roots: Improving CNN Efficiency with Hierarchical Filter Groups
• An entanglement-area law for general bosonic harmonic lattice systems
• Correlations, spectral gap, and entanglement in harmonic quantum systems on generic lattices
• Quantum states on Harmonic lattices
• Low-memory GEMM-based convolution algorithms for deep neural networks
• Pedagogical introduction to equilibrium Green's functions: condensed matter examples with numerical implementations
• Chunks and Tasks: a programming model for parallelization of dynamic algorithms
• Fast Multiplication of Matrices with Decay
• Implementing Strassen's Algorithm with CUTLASS on NVIDIA Volta GPUs