基于分层存储理论模型的近似字符串匹配并行算法研究

发布时间：2017-09-03 16:01

  本文关键词：基于分层存储理论模型的近似字符串匹配并行算法研究

  更多相关文章： 近似字符串匹配 分层存储理论模型 并行算法 CUDA

【摘要】：CUDA(Compute Unified Device Architecture)是一种重要的并行处理架构,但其具有相对复杂的线程管理机制和多重存储模块,从而使得基于CUDA的算法时间复杂度很难量化。针对这一问题,提出了一种分层存储理论模型—HMM(Hierarchical Memory Machine)模型,该模型所具有的分层存储结构可以有效地描述图形处理单元设备不同存储模块的物理特性,因此非常适用于对CUDA算法时间复杂度的量化评估。作为HMM模型的应用实例,文章提出了一种基于HMM模型的并行近似字符串匹配算法,并给出了相应算法时间复杂度的计算过程。与串行算法相比,该算法可以获得60倍以上的加速比。
【作者单位】： 中国科学院深圳先进技术研究院;
【关键词】： 近似字符串匹配 分层存储理论模型 并行算法 CUDA
【分类号】：TP391.1;TP333
【正文快照】： 1引言众所周知,最初GPU(Graphics ProcessingUnits)[1]是为了加速图形图像处理应用而设计的特殊电路。但现在它的应用不仅仅局限于图形图像处理,已经延伸到了一般的科学计算领域[2-6]。在实践中,我们可以利用NVIDIA公司所提供的并行处理架构——CUDA(ComputeUnified Device Ar

【相似文献】

中国博士学位论文全文数据库 前1条

1 王烁;字符串模式匹配的硬件加速研究[D];中国科学技术大学;2008年

，

本文编号：785933