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

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

作　　者：崔文科[1,2] 徐克付[2] 李娜娜[2] 胡玥[1] 

机构地区：[1]北京科技大学计算机与通信工程学院,北京100083 [2]中国科学院计算技术研究所信息内容安全技术国家工程实验室,北京100190

出　　处：《计算机工程》2012年第22期267-270,275,共5页Computer Engineering

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

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

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

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]