Smith-Waterman算法在脉动阵列上的实现及分析  

The Implementation and Analysis of Smith-Waterman Algorithm on Systolic Array

作　　者：汪冬[1] 唐志敏[1] 

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

出　　处：《计算机学报》2004年第1期12-20,共9页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究计划 (G19990 3 2 80 0 );国家"八六三"高技术研究发展计划重点课题 (2 0 0 1AA11110 0 );中国科学院知识创新工程重点项目(KGCX1 SW 0 9)资助

摘　　要：Smith Waterman算法是一种经典的序列比对算法 ,在双序列比对的情况下具有比较好的性能 ,但是在大规模的序列比对时 ,其性能并不能令人满意 .脉动式阵列和Smith Waterman算法有比较好的吻合性 .该文通过在龙芯 1号处理器上附加一个脉动式阵列的协处理器 ,构建了硬件模型 .通过模拟器的验证 ,附加了协处理器的龙芯 1号的性能与没有附加协处理器时的性能之比接近于线性 .该文最后根据硬件模型和模拟器的性能数据 。Smith Waterman algorithm is a classical sequence alignment algorithm and behaves very well in a bi sequence alignment. But its performance is not satisfying when aligning a lot of sequences. The systolic array architecture shows good fitness for the algorithm. By appending the array as a co processor to the Godson 1 architecture, authors build the hardware model of the accelerator. By comparing the performance on the Godson 1 simulator with the co processor and the one without, the systolic array shows almost linear speed up on the algorithm. Authors at last analyze the model and performance data to reveal the aspects that affect the performance especially the cells’ number, the sequences’ length, branches and cache size.

关 键 词：SMITH-WATERMAN算法 脉动阵列 序列比对算法 计算机 生物信息学 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] Q811.4[自动化与计算机技术—计算机科学与技术]