期刊文献+

多核CPU/GPU平台下的集合求交算法

List Intersection Algorithm on Multi-core CPU/GPU Platform
下载PDF
导出
摘要 提出一个多核CPU/GPU混合平台下的集合求交算法。针对CPU端求交问题,利用对数据空间局部性和中序求交的思想,给出内向求交算法和Baeza-Yates改进算法,算法速度分别提升0.79倍和1.25倍。在GPU端,提出有效搜索区间思想,通过计算GPU中每个Block在其余列表上的有效搜索区间来缩小搜索范围,进而提升求交速度,速度平均提升40%。在混合平台采用时间隐藏技术将数据预处理和输入输出操作隐藏在GPU计算过程中,结果显示系统平均速度可提升85%。 A list intersection algorithm on Multi-Core CPU/GPU platform is put forward. For CPU, inwards intersection algorithm and refined Baeza-Yates algorithm are proposed, by taking advantage of data locality and in-order intersection strategy. they gain 0.79 and 1.25 times speed up respectively. For GPU, effective search interval thought is proposed. The search range is reduced by computing effective search interval in other lists of each Block, thus enhance the speed of the intersection, which irfiproves the speed of list intersection by 40%. For mixed-platform, the operation of data preprocessing and I/O is hidden by time hiding technology, and the final system has a speed up of about 85%.
作者 王怀超 赵雷
出处 《计算机工程》 CAS CSCD 2013年第4期296-299,304,共5页 Computer Engineering
基金 国家自然科学基金资助项目(61073061)
关键词 集合求交 多核CPU GPU求交算法 并行算法 时间隐藏 有效搜索区间 list intersection multi-core CPU GPU intersection algorithm parallel algorithm time hiding valid search range
  • 相关文献

参考文献10

  • 1吴恩华.图形处理器用于通用计算的技术、现状及其挑战[J].软件学报,2004,15(10):1493-1504. 被引量:141
  • 2Barbay J, L6pez-Ortiz A, Salinger A, et al. An Experi- mental Investigation of Set Intersection Algorithms for Text Searching[J]. Journal of Experimental Algorithmics, 2009, 14(7): 7-24.
  • 3Wu Di, Zhang Fan, Ao Naiyong, et al. Efficient Lists Intersection by CPU-GPU Cooperative Computing[C]// Proc. of International Symposium on Parallel & Distributed Processing. Atlanta, USA: IEEE Press, 2010.
  • 4Ao Naiyong, Zhang Fan, Wu Di, et al. Efficient Parallel Lists Intersection and Index Compression Algorithms Using Graphics Processing Units[J]. Proceedings of the VLDB Endowment, 2011, 4(8): 470-481.
  • 5Bentley J L, Yao A C C. An Almost Optimal Algorithm for Unbounded Searching[J]. Information Processing Letters, 1976, 5(3): 82-87.
  • 6Krauthgamer R, Mehta A, Raman V, et al. Greedy List Intersection[C]//Proc. of the 24th International Conference on Data Engineering. Washington D. C., USA: IEEE Computer Society, 2008:1033-1042.
  • 7Wu Di, Zhang Fan, Ao Naiyong, et al. A Batched GPU Algorithm for Set lntersection[C]//Proc, of the 10th International Symposium on Pervasive Systems, Algo- rithms, and Networks. [S. 1.]: IEEE Press, 2009: 752-756.
  • 8陈伟,杜凌霞,陈红.多核架构下的数据处理算法优化策略综述[J].计算机科学与探索,2011,5(12):1057-1075. 被引量:7
  • 9Yang Canqun, Wang Feng, Du Yunfei, et al. Adaptive Optimization for Petascale Heterogeneous CPU/GPU Computing[C]//Proc. of International Conference on Cluster Computing. IS. 1.]: IEEE Press, 2010.
  • 10邹岩,杨志义,张凯龙.CUDA并行程序的内存访问优化技术研究[J].计算机测量与控制,2009,17(12):2504-2506. 被引量:17

二级参考文献7

  • 1吴恩华,柳有权.基于图形处理器(GPU)的通用计算[J].计算机辅助设计与图形学学报,2004,16(5):601-612. 被引量:227
  • 2NVIDIA Corporation. CUDA ProgrammingGuide 2. 0 [EB/OL]. http: //www. nvidia. com, Jun, 2008.
  • 3Luebke D, Humphreys G. How GPUs Work [J]. IEEE Computer, 2007, 40 (2): 96-100.
  • 4Nickolls J, Buck I, Garland M, et al. Scalable Parallel Programming with CUDA [J]. Queue, 2008, 6 (2): 40-53.
  • 5Halfhil T R. Parallel Processing With CUDA [R]. Microprocessor Report, Scottsdale, Arizona, 2008.
  • 6Owens J D, Houston M, Luebke D, et al.. GPU Computing [J]. Proceedings of the IEEE, 2008, 96 (5): 879-897.
  • 7邓亚丹,景宁,熊伟.基于共享Cache多核处理器的Hash连接优化[J].软件学报,2010,21(6):1220-1232. 被引量:4

共引文献162

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部