Introduction
Standard GPU libraries like cuBLAS are highly optimized for square or "regular-shaped" matrices. However, they often underperform when dealing with "tall-and-skinny" matrices, where one dimension is significantly larger than the others. This paper introduces TSM2 and ISM2, two specialized algorithms designed to bridge this efficiency gap. By employing outer-product computation, optimized shared memory tiling, and aggressive data prefetching, these methods achieve up to a 3.5x speedup over state-of-the-art libraries across multiple GPU generations.
The Challenge of Irregular Shapes
In High-Performance Computing (HPC), General Matrix-Matrix Multiplication (GEMM) is a foundational operation. While regular-shaped inputs are typically compute-bound, irregular-shaped matrices—common in K-means clustering, finite element methods, and checksum calculations—often become memory-bound or latency-bound. Standard libraries like cuBLAS frequently utilize less than 20% of a GPU's theoretical memory bandwidth in these scenarios because their internal tiling strategies do not adapt to the low compute-to-load ratio of skinny matrices.
Proposed Methodology
The authors propose two distinct algorithms to address the spectrum of irregular shapes:
- TSM2: Optimized for one tall-and-skinny matrix multiplying a large-to-medium regular matrix.
- ISM2: Tailored for cases where a tall-and-skinny matrix multiplies a very small regular matrix (e.g., $4 \times 4$ or $16 \times 16$).
Architectural Innovations
A core component of these algorithms is the use of Outer-Product Style Computation. Unlike traditional inner-product methods that may load elements of a large matrix multiple times, the outer-product approach ensures each element of the large matrix is loaded into registers exactly once, significantly reducing global memory traffic.
To further enhance throughput, the authors address Bank-Conflict-Free Shared Memory. By utilizing a column-major storage format for tiles in shared memory, the algorithms avoid the performance degradation caused by multiple threads accessing the same memory bank simultaneously.
Additionally, the implementation uses Double-Buffered Prefetching to overlap computation with data movement. While the GPU processes the current tile, the next tile is simultaneously loaded into registers or shared memory, effectively hiding memory latency.
For extremely small matrices where thread occupancy is low, ISM2 introduces a "thread count factor" ($tcf$). This technique consolidates work into fewer, more compute-intensive threads to better fill the GPU's execution pipeline and hide latency.
Performance Evaluation
The algorithms were tested using synthetic matrices of various sizes (up to $30,720 \times 30,720$) with skinny dimensions as small as 2. Testing spanned four NVIDIA GPU generations: Kepler (K40c), Maxwell (M40), Pascal (P100), and Volta (V100).
Key Results
- Speedup: TSM2 and ISM2 achieved speedups ranging from 1.1x to 3.5x over cuBLAS 9.0.
- Resource Efficiency: On the Tesla K40c, memory bandwidth utilization improved by up to 47.6%, and computing power utilization increased by up to 37.3% compared to the baseline.
- Latency Mitigation: In latency-bound scenarios where cuBLAS struggled, ISM2 improved memory bandwidth utilization by up to 55%.
Conclusion and Future Work
The fundamental insight of this work is that GEMM performance bottlenecks shift based on the input's aspect ratio. By trading register usage for reduced memory traffic and carefully managing thread-level work distribution, TSM2 and ISM2 significantly outperform general-purpose libraries for irregular shapes. Future research directions include adapting these optimizations for non-NVIDIA architectures and exploring performance for "ragged" matrices where irregularity is even more pronounced.
Summary updated