Dr. Top-k: Delegate-Centric Top-k on GPUs
Dr. Top-k: Delegate-Centric Top-k on GPUs
复制标题
DOI：
10.1145/3458817.3476141
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
Anil Gaihre;Da Zheng;Scott Weitze;Lingda Li;S. Song;Caiwen Ding;X. Li;Hang Liu
中科院分区：
文献类型：
--
作者：
Anil Gaihre;Da Zheng;Scott Weitze;Lingda Li;S. Song;Caiwen Ding;X. Li;Hang Liu
最近的top-k计算工作探索了修改各种排序算法以回答gpu上top-k查询的可能性。不幸的是，这些努力执行的工作比需要的多得多。本文介绍了Dr. Top-k，这是一个基于gpu的以delegate为中心的Top-k系统，可以显著减少Top-k工作负载。特别是，它包含三个主要贡献：首先，我们引入了以委托为中心概念的全面设计，包括最大委托、基于委托的过滤和$\beta$委托机制，以帮助将top-k的工作量减少99%以上。其次，由于获得适当的子范围尺寸的难度和重要性，我们进行了严格的理论分析，并结合彻底的实验验证来确定理想的子范围尺寸。第三，我们介绍了四个关键的系统优化，以实现快速的多gpu top-k计算。总的来说，这项工作不断超越最先进的技术。
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 $\beta$ 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.