肖俊杰

（上海交通大学电子信息与电气工程学院，上海200240）

0 引言

生物序列比对是生物信息学和计算生物学的基本问题之一，它旨在找出一个未知序列与已知序列在结构和功能上是否相关，这对于疾病的早期防治和药物工程至关重要[1]。Needleman-Wunsch 算法[2]是一种广泛使用的序列比对算法，用于全局比对两个序列之间的相似性。这一算法基于动态规划实现，可以求得比对的最优解，但其时间复杂度与序列长度的乘积成正比，考虑到生物序列数据库的巨大规模和其指数增长率，需要更快的计算技术来应对这一问题。

高算力的并行结构为解决这一问题提供了机会，但是Needleman-Wunsch 算法内部数据之间存在依赖性，需要各计算节点之间相互通信。现有计算方法大多基于波前进位（wave-front）[3]这一并行方式进行优化删减[4-6]，但其访存特征不规则，难以实现高效的访存调度，有限的存储资源和过多的片外存储器访问导致并行效率下降成为了硬件优化的主要阻碍。因此本文提出了一种基于滑动窗的解决方案，采用了通用化的并行策略，简化了对Needleman-Wunsch 算法进行并行的难度；并提出一种延时串连的脉动阵列（systolic array）[7]结构，减少了对存储的访问。为与不同加速方案下的计算和存储特征相匹配，本文基于粗粒度可重构阵列（CGRA）[8]对改进前后的方案进行了比较，并与通用计算架构下的解决方案对比，量化本文方案在执行时间和执行效率方面的优势。

1 Needleman-Wunsch算法

Needleman- Wunsch 算法的目标是在序列X=x1x2…xi…xM（序列长度为M）和序列Y=y1y2…yj…yN（序列长度为N）之间寻找最佳的全局匹配结果。……