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

doi:10.11772/j.issn.1001-9081.2014.11.3112

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

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

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

黄玉龙¹,邹循进²,刘奎¹,苏本跃¹

1. 安庆师范学院计算机与信息学院,安徽安庆 246133
2. 江西省国土资源厅信息中心,南昌 330025

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

GPU-accelerated segmented Top-k query algorithm

HUANG Yulong¹,ZOU Xunjin²,LIU Kui¹,SU Benyue¹

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-12-01 Published:2014-11-01
Contact: HUANG Yulong

摘要/Abstract

摘要：

现有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.

中图分类号:

黄玉龙邹循进刘奎苏本跃. GPU加速的分段Top-k查询算法[J]. 计算机应用, 2014, 34(11): 3112-3116.

HUANG Yulong ZOU Xunjin LIU Kui SU Benyue. GPU-accelerated segmented Top-k query algorithm[J]. Journal of Computer Applications, 2014, 34(11): 3112-3116.

参考文献

[1]FAGIN R, LOTEM A, NAOR M. Optimal aggregation algorithms for middleware[J]. Journal of Computer and System Sciences, 2003,66(4):614-656.
[2]GUNTZER U, BALKE W-T, KIEBLING W. Towards efficient multi-feature queries in heterogeneous environments [C]// Proceedings of the 2001 International Conference on Information Technology: Coding and Computing. Piscataway: IEEE Press,2001:622-628.
[3]MAMOULIS N, YIU M L, CHENG K H, et al. Efficient Top-k aggregation of ranked inputs[J]. ACM Transactions on Database Systems, 2007, 32(3): Article No. 19.
[4]YUAN J, SUN G, TIAN Y, et al. Selective-NRA algorithms for Top-k queries[C]// APWeb/WAIM 2009: Proceedings of the 2009 Joint International Conferences on Advances in Data and Web Management, LNCS 5446. Berlin: Springer-Verlag,2009:15-26.
[5]WU C, SUN G, CHEN G. Performance optimization of Top-k queries on multicore platform[J]. Journal of Chinese Computer Systems, 2012, 33 (7) :1489-1492.(吴超,孙广中,陈国良.多核平台上Top-k查询的性能优化[J].小型微型计算机统,2012,33(7):1489-1492.)
[6]LUO T, SUN G, CHEN G. Performance optimization of Top-k queries on GPU[C]// Proceedings of the 2011 Fourth International Symposium on Parallel Architectures, Algorithms and Programming. Piscataway: IEEE Press, 2011:9-13.
[7]HE J, LU M, HE B. Revisiting co-processing for Hash joins on the coupled CPU-GPU architecture[J]. Proceedings of the VLDB Endowment,2013, 6(10): 889-900.
[8]SEBASTIAN B, INGOLF G, EIKE S, et al. A framework for cost based optimization of hybrid CPU/GPU query plans in database systems [J]. Control and Cybernetics,2012,41(4):715-742.
[9]NVIDIA Corporation. NVIDIA CUDA compute unified device architecture programming guide [EB/OL].[2014-05-15]. http://www.docin.com/p-34710013.html.
[10]RONALD F, RAVI K, SIVAKUMAR D. Efficient similarity search and classification via rank aggregation[C]// Proceedings of the 22nd ACM SIGMOD. New York: ACM Press,2003:301-312.
[11]CHANG H, QIN T, LIU X,et al. Top-k queries processing with uncertain data on graphics processing units[C]// Proceedings of the Fourth International Symposium on Parallel Architectures, Algorithms and Programming. Piscataway: IEEE Press,2011: 310-314.
[12]CHEN N, YU M, HU D. An implementation of GPU-based parallel optimization for an extended uncertain data query algorithm[C]// Proceedings of the Fourth International Symposium on Parallel Architectures Algorithms and Programming. Piscataway: IEEE Press, 2011: 197-202.
[13]NATHAN B, JARED H. Thrust: a productivity-oriented library for CUDA[EB/OL].[2013-09-10]. http://sbel.wisc.edu/Courses/ME964/Literature/thrust GPUgems2011.pdf.

[1]	侯阳张琼赵紫煊朱正宇张晓博. 基于YOLOv5s的复杂场景下高效烟火检测算法——YOLOv5s-MRD[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	张奇业, 曾心蕊. 带高斯核的支持向量数据描述问题的高效积极集法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3808-3814.
[3]	曹晓意罗煦琼李景贺恩锋. 改进人工势场法下的多无人机编队路径规划方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[4]	袁志超杨磊田井林魏晓威李康顺. 面向复杂约束多目标优化问题的双种群双阶段进化算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[5]	冷琴, 毛政元. 考虑设施规模决策的两级选址-路径优化[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3513-3520.
[6]	彭庆媛, 王晓峰, 王军霞, 华盈盈, 唐傲, 何飞. 可满足性问题相变研究综述[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3503-3512.
[7]	孙仁科, 皇甫志宇, 陈虎, 李仲年, 许新征. 神经架构搜索综述[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 2983-2994.
[8]	孙安泰, 刘烨, 徐冬梅. 多智能体系统的动态面渐近补偿算法[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3151-3157.
[9]	颜超英, 张紫仪, 曲映楠, 李秋禹, 郑地翔, 孙丽珺. 基于联盟链的双向拍卖碳交易[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3240-3245.
[10]	杨志龙邹德旋李灿邵莹莹马乐杰. 融入限制反向学习与柯西-高斯变异的蜣螂优化算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	姚光磊, 熊菊霞, 杨国武. 基于神经网络优化的花朵授粉算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2829-2837.
[12]	力尚龙, 刘建华, 贾鹤鸣. 融合多狩猎协调策略的爬行动物搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2818-2828.
[13]	李焱, 潘大志, 郑思情. 多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1897-1904.
[14]	张倩婷胡丽莹陈黎飞. 时间序列的鲁棒形态表征方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[15]	胡林波倪志伟程家乐刘文涛朱旭辉. 基于融合社区检测的复杂协作众包任务分配方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.

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

GPU-accelerated segmented Top-k query algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics