计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2006年
11期
85-87
,共3页
戴正华%张庆丹%徐琳%谭光明%冯圣中
戴正華%張慶丹%徐琳%譚光明%馮聖中
대정화%장경단%서림%담광명%풍골중
Smith-Waterman%算法%细粒度并行算法%SIMD%SSE2
Smith-Waterman%算法%細粒度併行算法%SIMD%SSE2
Smith-Waterman%산법%세립도병행산법%SIMD%SSE2
Smith-Waterman动态规划算法是生物信息学使用最广泛的序列匹配算法,由于存在严重的数据依赖关系,该算法的细粒度数据并行性开发受到了很大限制.文章从简化数据依赖关系出发,采用前驱计算思想,提出了基于X86处理器多媒体指令集SSE2的Smith-Waterman细粒度并行算法SWSSE2,在相似性显著的情况下比普通的SW算法性能提高5倍,且与测试集无关.一般相似性不显著的情形下,同目前最好的动态规划细粒度并行算法SWMMX相比可以获得1.5倍的加速比.
Smith-Waterman動態規劃算法是生物信息學使用最廣汎的序列匹配算法,由于存在嚴重的數據依賴關繫,該算法的細粒度數據併行性開髮受到瞭很大限製.文章從簡化數據依賴關繫齣髮,採用前驅計算思想,提齣瞭基于X86處理器多媒體指令集SSE2的Smith-Waterman細粒度併行算法SWSSE2,在相似性顯著的情況下比普通的SW算法性能提高5倍,且與測試集無關.一般相似性不顯著的情形下,同目前最好的動態規劃細粒度併行算法SWMMX相比可以穫得1.5倍的加速比.
Smith-Waterman동태규화산법시생물신식학사용최엄범적서렬필배산법,유우존재엄중적수거의뢰관계,해산법적세립도수거병행성개발수도료흔대한제.문장종간화수거의뢰관계출발,채용전구계산사상,제출료기우X86처리기다매체지령집SSE2적Smith-Waterman세립도병행산법SWSSE2,재상사성현저적정황하비보통적SW산법성능제고5배,차여측시집무관.일반상사성불현저적정형하,동목전최호적동태규화세립도병행산법SWMMX상비가이획득1.5배적가속비.
