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

摘要

论文主要讨论了Smith&Waterman算法以及在脉动式阵列上的加速.通过对Smith&Waterman比对算法的并行化方法的考察,引出细粒度并行化方法和定制硬件,特别是脉动式阵列;通过对脉动式阵列的结构和特点的分析,结合龙芯I号处理器的结构,设计了龙芯I号新的协处理器CP2为一个脉动式阵列,并设计了相关的一组指令集;通过对龙芯I号的模拟器的修改,实现了该协处理器和指令集;在算法和系统结构互相制约的基础上,描述了算法在脉动式阵列上的实现,明确了算法实现过程中的一些实现细节;最后通过在新的模拟器和原模拟器上的性能比较,针对实验数据中体现的协处理器的优势和不足,总结了脉动式阵列结构在各个方面对算法性能提高的影响,最后总结了已完成的实验内容以及未来工作的一些方向.