摘要
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.
出处
《计算机工程与应用》
CSCD
北大核心
2006年第11期85-87,共3页
Computer Engineering and Applications
基金
国家自然科学基金资助项目(编号:60372040)
