Abstract: HMMer is a bioinformatics software package that uses profile HMMs（Hidden Markov Models） to model the primary structure consensus of a family of protein or nucleic acid sequences. However, it is more and more time-consuming to run HMMer on traditional computer architecture due to the sequence. In this paper, the computation kernel of HMMer, P7Viterbi, is selected to accelerate on FPGA platform. There is an infrequent feedback loop in P7Viterbi to update the value of beginning state（B state）, which limits further parallelization. Previous work either ignored the feedback loop or serialized the process, leading to loss of either precision or efficiency. The proposed syslolic array based architecture with a parallel data providing unit can exploit maximum parallelism of the full version of P7Viterbi. The proposed architecture speculatively runs with fully parallelism assuming that the feedback loop does not take place. If the rare feedback case actually occurs, a rollback mechanism is used to ensure correctness. The experimental results show that the FPGA-based pipelined parallel system can be very efficient in running HMMer. The proposed architecture with 20 PEs by running on Xilinx Virtex-5 110T FPGA platform can achieve approximately 56.8 times speedup compared with the one running on Intel Core2 Duo 2.33 GHz CPU.

Key words: systolic array, Field Programmable Gate Array（FPGA）, Plan7 Hidden Markov Model（HMM）

摘要： HMMer是用PHMM来对蛋白质或氨基酸序列查询进行分类和匹配的生物信息学软件工具包，但是由于HMMer的并行特性，HMMer在传统的串行化CPU平台上运行十分耗时。采用FPGA对HMMer的核心算法P7Viterbi进行加速，在P7Viterbi算法中存在一个限制并行性的多层循环的迭代间数据依赖关系，以前的工作都是忽略该循环反馈或者串行化这部分程序，从而导致精度和效率的降低。提出了一种基于FPGA的可以适应P7Viterbi的数据依赖特性的基于脉动阵列的并行运算结构，采用自动重算机制来解决阻碍计算并行的回边问题。在FPGA中通过并行流水技术实现的加速系统能够有效地提高HMMer的运算效率。实验结果表明，提出的带有20个运算单元的结构和Intel Core2 Duo 2.33 GHz CPU平台相比，加速比能够达到56.8倍。

关键词: 脉动阵列, 现场可编程门阵列（FPGA）, Plan7隐马尔可夫模型（HMM）