面向体系结构的串匹配算法优化研究

《面向体系结构的串匹配算法优化研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、串匹配算法广泛应用于生物信息学、信息检索等领域。随着基因数据和网络数据的爆炸式增长，对串匹配算法的性能也提出更高的要求。本文从计算机体系结构的角度出发，立足于开发串匹配算法的数据并行性和提高算法的cache性能。本文的主要工作包括：(1)基于SIMD指令集的动态规划算法数据并行性开发与实现研究。动态规划是模糊串匹配和序列联配中的基本算法•一类动态规划算法以Smith・Watennan算法为代表，计算复杂度为。(朮)：一类是以Zuker算法为代表，计算复杂性为CXn5)。本文分析了两类动态规划算法的数据依赖关系及其数据并行性。基于前驱计算思

2、想，优化设计了Smith-Watennan算法，充分挖掘了算法的数据并行性，并基于SIMD指令集实现，数倍提高了该算法性能。通过设计辅助矩阵，有效组织数据，优化设计了Zuker算法，对于较大的数据规模，获得了接近理论值的加速比.(2)基于组合字符集的高性能shifbor算法研究Shift-or算法广泛应用于内容过滤领域。基本的shifter算法以char类型的字符集合作为字符集,因而状态转换单位为8bits。本文通过组合NFA的状态，建立E—上的NFA,状态转换单位提高为short型整数，显著降低了自动机状态转换次数，提高了计算效率.(3

3、)面向位并行的低内存开销高性能关键词表达式匹配算法研究关键词表达式匹配算法是一类重要的串匹配算法。本文面向位并行，利用ft>ur・njssian和分治等优化方法设计了新的关键词表达式匹配算法，可提高计算效率、降低内存开销。关键词：串匹配算法；SIMD；算法优化；位并行ABSTRACTOptimizationofstringmatchingalgorithmbasedoncomputerarchitectureDaiZhenghua(ComputerArchitecture)DirectedByF«igShengzhongStringmat

4、chingalgorithmisafundamentalprobleminBioinfbrmaticsandInformationretrieval.Despiteofabigamountofeffortsspentbyresearchersondesigningefficientstringmatchingalgorithm,improvingthestringmatchingefficiencyremainsofprimaryimportance^whichisduetothedrasticgrowthofgenedataandweb

5、contoitandconsequentlythemoremorecriticaldemandonthepafbrmanceofstringmatdiing.Thisdiesisaimsataddressingtheproblemofhowtooptimizestringmatchingalgorithmwithresped*totfiediaracteristicsofcmnputerarchitecture^whoseprimaryaimistoexploreILPandimprovetheperfbnnanceofdataacces

6、singthrou^icadieThemainwotkislistedasbelow:(1)ResirchonexploitingandimplementingdataparallelizationofdynamicprogrammingandbasedonSEMDinstructionsetDynamicprogrammingisthebasisof却proximatestringmatchingandsequencealignmentTwomostpopularkindsofsuchalgorithmsarepresentedintt

7、iisthesis:theoneisrepresentedbySmith-WatermanalgorithmwhosecomputingcomplexityisO(n2);theotherisrepresscitedbyZukeralgorithmwhosecomputingcomplexityisO(n3).WeanalyzethedatadepoulencyanddataParallelismofthesetwokindsofdynamicprogramming.ThenweexploitdataparallelizationofSm

8、ith-WatermanalgorithmbasedonthethinkingofPrefixComputation,andimplementitwithSIMDinstructionsetW