Abstract
Top-k selection algorithms are fundamental in a wide range of applications, including high-performance computing, information retrieval, big data processing, and neural network model training. In this paper, we present RTop-K, a highly efficient parallel row-wise top-k selection algorithm specifically designed for GPUs. RTop-K leverages a binary search-based approach to optimize row-wise top-k selection, providing a scalable and accelerated solution. We conduct a detailed analysis of early stopping in our algorithm, showing that it effectively maintains the testing accuracy of neural network models while substantially improving performance. Our GPU implementation of RTop-K demonstrates superior performance over state-of-the-art row-wise top-k GPU implementations, achieving an average speed-up of up to 11.49$\times$ with early stopping and 7.29$\times$ without early stopping. Moreover, RTop-K accelerates the overall training workflow of MaxK-GNNs, delivering speed-ups ranging from 11.97% to 33.29% across different models and datasets.
Introduction
Top-$k$ selection—finding the $k$ largest elements in a set—is a fundamental operation in computer science. In modern deep learning, particularly for sparse training and specialized architectures like MaxK-GNNs, this operation must be performed "row-wise": given a large matrix, find the top-$k$ values in every single row.
Existing GPU top-$k$ implementations, such as those in PyTorch, are often optimized for either a single massive vector or a small batch of very large vectors. However, neural networks frequently operate in a "many-small-vectors" regime, involving millions of rows with lengths typically $\le$ 1024. Standard algorithms like RadixSelect introduce significant overhead in these scenarios, leading to high memory consumption and slower training.
The RTop-K Algorithm
RTop-K addresses these challenges by replacing complex sorting or radix-based methods with a streamlined binary search approach.
Binary Search for Thresholds
Instead of sorting elements, RTop-K searches for a threshold value such that exactly $k$ elements in a row are greater than or equal to it. The algorithm iteratively narrows the range between the row's minimum and maximum values.
Early Stopping
A key innovation in RTop-K is the "early stopping" mechanism. Recognizing that neural networks are inherently robust to noise, the authors propose stopping the binary search after a fixed number of iterations (e.g., 5–8). This produces an "approximate" top-$k$ set that is much faster to compute but still contains the most important features for the model.
GPU-Centric Implementation
The implementation of RTop-K is highly optimized for GPU architectures, specifically targeting the warp level.
- Warp-Level Parallelism: RTop-K assigns exactly one warp (32 threads) to handle one row. This mapping allows the algorithm to stay entirely within fast on-chip registers and shared memory during the search phase.
- Warp Primitives: The search phase uses high-speed warp primitives like
shuffleandballotfor inter-thread communication, avoiding slow global memory accesses. - Phased Execution: The process is divided into three main phases: Loading, Searching (the iterative binary search), and Selecting (extracting the final indices and values).
Experimental Evaluation
The authors evaluated RTop-K by integrating it into the training of various GNN models (GraphSAGE, GCN, and GIN) using large-scale graph datasets like Ogbn-products, Yelp, Reddit, and Flickr.
Performance Results
- Raw Speedup: RTop-K achieves an average speedup of 11.49$\times$ with early stopping and 7.29$\times$ for exact top-$k$ selection compared to
torch.topk. - End-to-End Training: Total training time for MaxK-GNNs was reduced by 11.97% to 33.29% across different datasets.
- Accuracy Preservation: The impact of using approximate top-$k$ selection on final model accuracy was negligible, often staying within 0.1% of the baseline. In some instances, the approximation even slightly improved accuracy, likely providing a regularizing effect.
Conclusion
RTop-K provides a highly efficient solution for row-wise top-$k$ selection on GPUs, particularly for the vector sizes common in neural network hidden layers. By leveraging binary search and warp-level optimizations, it significantly outperforms existing libraries. Future work includes scaling this approach to larger vector sizes through multi-warp coordination or further exploring approximate selection as a deliberate architectural feature.
Summary updated