SC21 Proceedings

The International Conference for High Performance Computing, Networking, Storage, and Analysis

Dr. Top-k: Delegate-Centric Top-k Computation on GPUs


Authors: Anil Gaihre (Stevens Institute of Technology); Da Zheng (Johns Hopkins University); Scott Weitze (Stevens Institute of Technology); Lingda Li (Brookhaven National Laboratory); Shuaiwen Leon Song (University of Sydney, University of Washington); Caiwen Ding (University of Connecticut); Xiaoye S. Li (Lawrence Berkeley National Laboratory (LBNL)); and Hang Liu (Stevens Institute of Technology)

Abstract: Recent top-k computation efforts explore the possibility of revising various sorting algorithms to answer top-k queries on GPUs. These endeavors, unfortunately, perform significantly more work than needed. This paper introduces Dr. Top-k, a Delegate-centric top-k system on GPUs that can reduce the top-k workloads significantly. Particularly, it contains three major contributions: First, we introduce a comprehensive design of the delegate-centric concept, including maximum delegate, delegate-based filtering, and β delegate mechanisms to help reduce the workload for top-k up to more than 99%. Second, due to the difficulty and importance of deriving a proper subrange size, we perform a rigorous theoretical analysis, coupled with thorough experimental validations to identify the desirable subrange size. Third, we introduce four key system optimizations to enable fast multi-GPU top-k computation. Taken together, this work constantly outperforms the state-of-the-art.




Back to Technical Papers Archive Listing