计算机应用 ›› 2014, Vol. 34 ›› Issue (11): 3112-3116.DOI: 10.11772/j.issn.1001-9081.2014.11.3112

• 2014年全国开放式分布与并行计算学术年会(DPCS 2014)论文 • 上一篇    下一篇

GPU加速的分段Top-k查询算法

黄玉龙1,邹循进2,刘奎1,苏本跃1   

  1. 1. 安庆师范学院 计算机与信息学院,安徽 安庆 246133
    2. 江西省国土资源厅 信息中心,南昌 330025
  • 收稿日期:2014-07-28 修回日期:2014-08-06 出版日期:2014-11-01 发布日期:2014-12-01
  • 通讯作者: 黄玉龙
  • 作者简介:黄玉龙(1979-),男,江西吉水人,讲师,博士,CCF会员,主要研究方向:数据库、并行计算、无线传感器网络;邹循进(1980-),男,江西抚州人,高级工程师,硕士,主要研究方向:数字图像处理、移动通信、Ad Hoc网络;刘奎(1975-),男,安徽安庆人,副教授,博士研究生,主要研究方向:计算机视觉、数字图像处理;苏本跃(1971-),男,安徽芜湖人,教授,博士,CCF高级会员,主要研究方向:多媒体与可视媒体计算、数字图像与视频处理。
  • 基金资助:

    国家自然科学基金资助项目

GPU-accelerated segmented Top-k query algorithm

HUANG Yulong1,ZOU Xunjin2,LIU Kui1,SU Benyue1   

  1. 1. School of Computer and Information, Anqing Normal University, Anqing Anhui 246133,China;
    2. Information Center, Department of Land and Resources of Jiangxi Province, Nanchang Jiangxi 330025,China
  • Received:2014-07-28 Revised:2014-08-06 Online:2014-11-01 Published:2014-12-01
  • Contact: HUANG Yulong

摘要:

现有Top-k查询优化算法无法充分利用图形处理器(GPU)强大的并行吞吐量及时获取查询结果,为此提出了一种基于统一计算设备架构(CUDA)模型的大规模分段查询算法。通过划分查询过程以及采用分段并行处理策略,该算法可最大限度地提升查询过程中的计算和比较效率。实验结果表明,与4线程多核优化算法相比,所提算法具有明显的性能优势,当有序列表数量为6,遍历步长为120时,性能达到最优,此时比多核算法快40倍。

Abstract:

The existing algorithms of Top-k query can not make full use of the powerful parallel throughput of Graphic Processing Unit (GPU) to timely return the query results. So, a segmented query algorithm based on Compute Unified Device Architecture (CUDA) model was proposed. By dividing the query process and using the strategy of segmented parallel process, the maximal calculation and comparison efficiency in query process could be obtained in this algorithm. The experimental results show that this algorithm has obvious performance advantages compared with four-thread parallel optimization algorithm on multi-core CPU. When the number of ordered lists is 6 and the traversal stride is 120, the optimal performance can be obtained which is 40 times faster than multi-core CPU algorithm.

中图分类号: