作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (22): 267-270. doi: 10.3969/j.issn.1000-3428.2012.22.067

• 开发研究与设计技术 • 上一篇    下一篇

基于CUDA的位并行近似串匹配算法

崔文科 1,2,徐克付 2,李娜娜 2,胡 玥 1   

  1. (1. 北京科技大学计算机与通信工程学院,北京 100083; 2. 中国科学院计算技术研究所信息内容安全技术国家工程实验室,北京 100190)
  • 收稿日期:2012-01-11 修回日期:2012-03-21 出版日期:2012-11-20 发布日期:2012-11-17
  • 作者简介:崔文科(1986-),男,硕士研究生,主研方向:匹配算法,GPU通用计算;徐克付,博士;李娜娜,硕士研究生;胡 玥,教授
  • 基金资助:

    国家“863”计划基金资助项目(2011AA010705);国家自然科学基金资助项目(61003295)

Bit-parallel Approximate String Matching Algorithm Based on Compute Unified Device Architecture

CUI Wen-ke 1,2, XU Ke-fu 2, LI Na-na 2, HU Yue 1   

  1. (1. School of Computer & Communication Engineering, University of Science & Technology Beijing, Beijing 100083, China; 2. National Engineering Laboratory for Information Security Technologies, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China)
  • Received:2012-01-11 Revised:2012-03-21 Online:2012-11-20 Published:2012-11-17

摘要: 为满足文本检索、计算生物学等领域海量数据匹配对高性能计算的要求,提出一种基于计算统一设备架构(CUDA)的位并行近似串匹配算法。结合图形处理器(GPU)的高并行计算结构及存储带宽特性,通过优化数据存储方式,实现并行化动态规划矩阵算法(BPM)的加速,并对加速性能进行对比测试。实验结果表明,BPM算法通过GPU加速能获得20倍左右的加速比。

关键词: 图形处理器, 计算统一设备架构, 位并行, 近似匹配, 存储访问

Abstract: Aiming at the increasingly high performance requirements of text retrieval and computational biology, this paper proposes a bit-parallel approximate string matching based on Compute Unified Device Architecture(CUDA). Taking advantage of highly parallel computing architecture and high memory bandwidth characteristics of Graphic Processing Unit(GPU), it researches and realizes the acceleration of Bit-parallel dynamic Programming Matrix(BPM) algorithm based on CUDA through improving data accessing and computing strategy, and a comparison test about the GPU accelerated performance has also been carried out. Experimental results show that BPM algorithm can achieve 20 times speedup by GPU.

Key words: Graphic Processing Unit(GPU), Compute Unified Device Architecture(CUDA), bit-parallel, approximate matching, memory access

中图分类号: