基于滑动窗的Needleman-Wunsch算法硬件加速方案设计与实现

摘要

序列比对算法在疾病诊断等领域有着广泛应用,其中基于动态规划的Needleman-Wunsch算法具有全局最优解的特性,但却有较高的时间复杂度。为解决传统波前进位的并行方式计算和访存不规则,并行效率低的问题,提出一种基于滑动窗的改进方案,采用延时串连的脉动阵列结构实现大量局部数据的复用,降低访存次数和带宽需求,提高硬件资源利用率,并基于粗粒度可重构阵列进行实现。实验显示该方案相比改进前获得2.3倍的加速比,相比Intel Core i7-4770获得4.5倍的加速比。