基于SSE2的Smith-Waterman算法  

Smith-Waterman Algorithm Based on SSE2

作　　者：戴正华[1,2] 张庆丹[1,2] 徐琳[1,2] 谭光明[1,2] 冯圣中[1] 

机构地区：[1]中国科学院计算技术研究所 [2]中国科学院研究生院,北京100039

出　　处：《计算机工程与应用》2006年第11期85-87,共3页Computer Engineering and Applications

基　　金：国家自然科学基金资助项目(编号:60372040)

摘　　要：Smith-Waterman动态规划算法是生物信息学使用最广泛的序列匹配算法,由于存在严重的数据依赖关系,该算法的细粒度数据并行性开发受到了很大限制。文章从简化数据依赖关系出发,采用前驱计算思想,提出了基于X86处理器多媒体指令集SSE2的Smith-Waterman细粒度并行算法SWSSE2,在相似性显著的情况下比普通的SW算法性能提高5倍,且与测试集无关。一般相似性不显著的情形下,同目前最好的动态规划细粒度并行算法SWMMX相比可以获得1.5倍的加速比。The dynamic programming Smith-Waterman algorithm is the most common align algorithm in the field of bioinformation.Because of serious data dependence,the fine granularity data parallelism of that algorithm is poor.We simplify the data dependence,and using the think of prefix computation we present the fine granularity Smith-Waterman algorithm called SWSSE2 based on multimedia instruction set SSE2 of X86 processor.In the case of high similarity,the performance of SWSSE2 is 5 times as high as that of ordinary SW algorithm,and the performance has nothing to do with the set of test.In the case of inconspicuous similarity,the performance of SWSSE2 is 1.5 times as high as SWMMX which is the best algorithm in the case of conspicuous similarity.

关 键 词：Smith-Waterman 算法 细粒度并行算法 SIMD SSE2 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]