具有同时多种子检测与并行扩展能力的BLAST算法加速器研究

本文针对目前流行的BLAST算法存在的种子检测效率不高的问题,提出了一种不同于常规查询策略的并行多种子检测算法,并基于脉动阵列结构设计和实现了一种具备同时多种子检测与并行扩展能力的算法加速器,实现了对NCBI BLAST程序前两个阶段的加速。加速器阵列采用流水工作模式,能够动态计算所有单词的匹配点位置,避免了索引结构的存储开销;采用了阵列分组和并行种子收集策略减少了有效种子数量;采用组内种子合并策略避免了冗余扩展操作;采用多种子并行扩展策略实现了无阻塞的数据库搜索,显著提高了数据库搜索效率。实验结果表明,本设计在阵列规模和时钟频率上都优于相关研究工作,相对于目前主流的通用微处理器可获得20倍以上的加速效果。