基于gpu的串匹配算法的实现

《基于gpu的串匹配算法的实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学院计算技术研究所硕士学位论文基于GPU的串匹配算法的实现姓名：张庆丹申请学位级别：硕士专业：计算机系统结构指导教师：孙凝晖20060601摘要随着集成电路技术的发展，GPU(GraphicsprocessingUnit，图形处理器)的发展相当的迅速。当前，一个典型的GPU的实际程序运算速度可达20GFLoPs，内存带宽可达25．3GB／see，远远超过通用的CPU处理器。由于GPu具有如此巨大的运算潜力，越来越多的应用试图将通用计算任务移植到GPU上来做。利用GPU的SIMD流处理器作为通用计算平台已经得到了广泛的研究和应用，这使得GPU能够成为一个有效的C'PU协处理器，

2、获得较高的性价比。串匹配算法是生物信息学、信息检索领域的基础算法。随着近年来基因数据和网络数据的爆炸式增长，对串匹配算法性能的需求也日益增长。但是串匹配算法本身所具有的较强的数据依赖关系和很差的数据重用性的特点极大地限制了该算法在现有的cPu结构上的效率。尽管数据重用性差限制了在C'PU上的性能，但是其流式的特点比较适合流媒体的结构，然而其数掘依赖关系给在GPU上挖掘其并行性提出了挑战。本文从GPU的体系结构出发，研究如何在GPU上有效编程，如何开发串匹配算法的数据并行性，以及适合在GPU上运行的串匹配算法。本文的主要工作包括：(1)GPU上通用计算编程方法的研究：研究了OpenG

3、L、BROOK、CG等GPU上通用计算的编程方法，以及如何开发基于GPU的数据并行性。在此基础上，进行了GPU数据存取方式的研究，以串匹配操作中涉及的字符串文件为例，研究了充分利用了图形处理中纹理这一数据结构，将一般通用计算的数据结构映射到GPU中去的方法，以及在GPU中利用二维纹理方式高效计算的算法设计方法。(2)适合GPU的串匹配算法的设计与实现：BF算法是串匹配算法中最基础的算法，但它是串行算法，不适合GPU的体系结构。本文对BF算法进行了重新设计，将条件分支语句转化为计算语句，以充分利用GPU的并行处理能力．实验结果表明，基于GPU的并行算法能够取得较好的加速比。(3)研究

4、提高GPU体系结构下通用算法效率的方法：以BF串匹配算法为例，测试了各种参数变化对GPU性能的影响，从而给出了在现有GPU架构上有效实现通用计算的瓶颈，并推导出了在GPU体系结构上提高通用算法效率的一些方法。关键词：GPtl；SIMD；通用计算；串匹配算法：并行；算法优化ABSTRACTImplementationofStringMatchingAlgorithmBasedonGPUZhangQingdan(ComputerArchiecture)DirectedbySunNinghniWiththeachievementofIC(IntegratedCircuit)technol

5、ogy,GPU(GraphicsProcessingunioisbecomingverypowerful．Recently,atypicalshadingprogramrunningOiltheGPUcanreachthepeakperformanceof20GFLOPSandthememoryband谢dthof25．3GB／sec,whichismuchbetterthanthatoftheCPU．Forsakeofsuchhugepotentialcomputingcapability,II加怫andmoreapplications骶wringtoporttheircompu

6、tingtaskstotheGPU．UtilizingtheGPU勰aSIMDstreamprocessorforgeneralpurposecomputations．ithasb_EgxRneatopicofconsiderableinterestnowadays．n圮GPUcouldbooolneanefficientco-processoroftheCPU,gainingthehighperformancepriceratio．Thestringmatchingalgorithmisabasicalgorithminthebioinfonnatiesandinformatio

7、nsearchingfields．Withthebombinggrowingofthegenedataandwebdata,theneedforhi出performancesuingmatchingalgorithmsisgrowin吕Butthestringmatchingalgorithmshavethedatadependencyproblems,whichbadlyrestricttheefficiencyinCPU．11listhesisisconcentr