基于gpu的串匹配算法研究

《基于gpu的串匹配算法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第26卷第7期计算机应用Vol.26No.72006年7月ComputerApplicationsJuly2006文章编号:1001一9081(2006)07一1735一03基于GPU的串匹配算法研究张庆丹，”，戴正华，,2冯圣中’，孙凝晖，(1.中国科学院计算技术研究所，北京100080;2.中国科学院研究生院，北京100080)(qingdan.zhang@gmail.com)摘要:BF算法是串匹配算法中最基础的算法，但它是串行算法，不适合图形处理器(GraphicProcessingUnit,GPU)的体系结构。结合GPU的特殊体系结构，通过数据存取方式和计算策略的改进，充分利用了G

2、PU的并行处理能力，从而基于GPU实现了BF算法。实验结果表明基于GPU的并行算法能够取得较好的加速比，同时也给出了在现有GPU架构上有效实现通用计算的瓶颈。关键词:图形处理器;通用计算;串匹配;并行中图分类号:TP301.6文献标识码:AStringmatchingalgorithmresearchbasedongraphicprocessingunitZHANGQing-dan''2,DAIZheng-hua''2,FENGSheng-zhong',SUNNing-hui'(1.InstituteofComputingTechnology,ChineseAcademyofScience

3、s,Beijing100080,China;2.GraduateSchool,ChineseAcademyofSciences,Beijing100080,China)Abstract:BFalgorithmisthebasicalgorithminstringmatchingfield,butitisnotparallel,anddoesnotmatchthesystemarchitectureoftheGraphicProcessingUnit(GPU).ConcerningthespecifichardwarearchitectureoftheGPU,newmethodofdataa

4、ccessingandcomputingstrategyoftheparallelBFalgorithmwasdesigned.AndbyfullyusingtheparallelcapaticityoftheGPU,theGPU-basedalgorithmcanoutperformtheCPU-basedalgorithm.ThebottlenecksofGPUarchitecturesalsopresented.Keywords:GraphicProcessingUnit(GPU);generalpurposecomputation;stringmatching;parallel0引

5、言1GPU串匹配方法随着计算技术和集成电路技术的发展，图形硬件的更新速本文主要根据GPU的硬件特性对BF朴素串匹配算法进度也越来越快。GPU自1999年由nVidia公司提出以来，其发行并行化的改进，使之适合于GPU的处理，充分利用GPU的展速度是CPU的三倍多。多流水线结构、向量处理特性以及并行及数据流处理能力，来提高朴素申匹配算法的速度。下32位IEEE标准浮点精度的实现使得它对于计算密集型的科面首先介绍串匹配算法的申行算法。学应用有非常大的吸引力，越来越成为通用计算的一个有效的1.1BF串匹配算法并行平台〔1,21。近年来很多的科学计算都已经被移植到了BF朴素串匹配算法的C语言描述如

6、下:GPU这个平台上，诸如矩阵乘、3-SAT等经典的数值计算等。char*stnnatch(char*subject,char*query)在计算机科学领域，串匹配问题一直都是研究的焦点之【一。在拼写检查、搜索引擎、计算机病毒特征码匹配、数据压inti,j,k;intm二strlen(query);//模式串长度缩以及生物信息学中的序列匹配等应用中，都需要进行串匹intn=strlen(subject);//目标串长度配。字符串的模式匹配性能的提高会给这些相关领域带来巨for(i二O;i<=n一m;i++)大的影响。目前对串行串匹配算法的研究已经相对成熟川，{而对并行串匹配算法的研究也发展

7、得正热。为了获得更高的j=0;k二i;性能，需要根据运行平台的不同对程序进行改进，以牺牲通用while(j