Accelerating Sparse Matrix Operations in Neural Networks on Graphics Processing Units

Arturo Argueta, David Chiang

Introduction

While Graphics Processing Units (GPUs) are the primary computational engines for modern deep learning, optimization efforts have historically prioritized dense matrix operations. However, Natural Language Processing (NLP) models, particularly in Neural Machine Translation (NMT), exhibit significant sparsity at their boundaries. At the input layer, models often utilize "few-hot" vectors to represent subwords or linguistic tags. At the output layer, the decoding process—often involving beam search—requires calculating a softmax distribution followed by a top-$N$ selection.

Standard hardware-agnostic APIs frequently lack the task-specific optimizations required for these sparse patterns. In NMT, finding the top-$N$ elements can account for nearly 37% of total decoding time. This research introduces specialized GPU kernels designed to address these bottlenecks by directly leveraging GPU architecture.

Methodology

The researchers developed two primary algorithmic improvements:

Sparse N-Hot Lookups

Instead of standard matrix multiplication, the authors utilize the Compressed Sparse Row (CSR) format to represent sparse inputs. Their algorithm processes 32 rows and columns in parallel, aligning with the GPU's warp size. This approach allows the GPU to bypass zero entries, focusing computational resources exclusively on relevant embedding data.

Fused Softmax and Top-N Selection

The traditional approach involves calculating softmax for the entire vocabulary and then sorting the results. This research "fuses" these steps into a single GPU kernel to minimize memory overhead.

Algorithm for fused softmax and top-N selection.

Key innovations in this fusion include:

  • Modified Insertion Sort: While typically $O(K^2)$, insertion sort is highly efficient for the small arrays characteristic of NMT beam sizes.
  • Bit-Packed Atomic Operations: To enable parallel updates, the algorithm uses the CUDA atomicMax operation on a packed 64-bit integer. This integer stores the probability in the upper 32 bits and the word index in the lower 32 bits, ensuring that the atomicMax sorts by probability while maintaining index integrity without complex synchronization.

Experimental Setup

The algorithms were evaluated using synthetically generated matrices to test scalability across various parameters:

  • Batch sizes ($L$): 1 to 1024.
  • Vocabulary sizes ($K$): Fixed at 10,240.
  • Sparsity levels ($N$): 1 to 400 non-zero elements.
  • Hardware: NVIDIA Tesla V100 (Volta) and TITAN X (Pascal).

Results and Discussion

The specialized kernels demonstrated significant performance gains over standard baselines. The sparse lookup method achieved up to a $7\times$ speedup over NVIDIA’s cuBLAS and cuSPARSE on the V100 for highly sparse inputs.

Performance comparison of the proposed method against standard libraries for varying N.

The fused softmax/top-$N$ kernel showed even more dramatic improvements, reaching a $50\times$ speedup for small beam sizes ($N=10$) compared to previous state-of-the-art methods. A "crossover point" was identified at $N \approx 300$. For $N$ values below this threshold, the specialized sorting method is superior. Beyond this point, the overhead of insertion sort makes standard library functions more efficient.

Conclusion

By tailoring GPU operations to the specific sparsity patterns of NMT, this work significantly reduces the computational bottleneck of the decoding process. Future work aims to further fuse operations, potentially combining the final affine transformation with the softmax and top-$N$ selection to further alleviate memory bottlenecks in real-time translation systems.

Summary updated

BibTeX
@inproceedings{argueta2019accelerating,
  author = {Arturo Argueta and David Chiang},
  title = {{Accelerating Sparse Matrix Operations in Neural Networks on Graphics Processing Units}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2019},
  doi = {10.18653/v1/p19-1626},
}
Figure