具有同时多种子检测与并行扩展能力的BLAST算法加速器研究 The Research on BLAST Accelerator with Parallel Multi-Seeds Detection and Extension

本文针对目前流行的BLAST算法存在的种子检测效率不高的问题，提出了一种不同于常规查询策略的并行多种子检测算法，并基于脉动阵列结构设计和实现了一种具备同时多种子检测与并行扩展能力的算法加速器，实现了对NCBI BLAST程序前两个阶段的加速。加速器阵列采用流水工作模式，能够动态计算所有单词的匹配点位置，避免了索引结构的存储开销；采用了阵列分组和并行种子收集策略减少了有效种子数量；采用组内种子合并策略避免了冗余扩展操作；采用多种子并行扩展策略实现了无阻塞的数据库搜索，显著提高了数据库搜索效率。实验结果表明，本设计在阵列规模和时钟频率上都优于相关研究工作，相对于目前主流的通用微处理器可获得20倍以上的加速效果。 BLAST adopts index-based approach to detect the matches between two substrings by looking up a large table and processing one match per query. In this paper, we propose a systolic array approach to detect string matches without using looking up tables. The pipelining systolic array is implemented as a multi-seeds detection and parallel extension engine to accelerate the first two stages of NCBI BLAST algorithm. Different from the index-based approach, our implementation con- sumes little memory resources and eliminates redundant string extensions. Our FPGA implemen-tation achieves superior performance results in both of processing element number and clock frequency over related works in the area of FPGA BLAST accelerators. The experimental results show a speedup factor of more than 20× over the NCBI BLAST software running on a current main- stream PC platform.