计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2013年
8期
76-80
,共5页
陆志坚%吴艳霞%郭振华%孙延腾
陸誌堅%吳豔霞%郭振華%孫延騰
륙지견%오염하%곽진화%손연등
脉动阵列%现场可编程门阵列(FPGA)%Plan7隐马尔可夫模型(HMM)
脈動陣列%現場可編程門陣列(FPGA)%Plan7隱馬爾可伕模型(HMM)
맥동진렬%현장가편정문진렬(FPGA)%Plan7은마이가부모형(HMM)
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倍.
HMMer是用PHMM來對蛋白質或氨基痠序列查詢進行分類和匹配的生物信息學軟件工具包,但是由于HMMer的併行特性,HMMer在傳統的串行化CPU平檯上運行十分耗時.採用FPGA對HMMer的覈心算法P7Viterbi進行加速,在P7Viterbi算法中存在一箇限製併行性的多層循環的迭代間數據依賴關繫,以前的工作都是忽略該循環反饋或者串行化這部分程序,從而導緻精度和效率的降低.提齣瞭一種基于FPGA的可以適應P7Viterbi的數據依賴特性的基于脈動陣列的併行運算結構,採用自動重算機製來解決阻礙計算併行的迴邊問題.在FPGA中通過併行流水技術實現的加速繫統能夠有效地提高HMMer的運算效率.實驗結果錶明,提齣的帶有20箇運算單元的結構和Intel Core2 Duo 2.33 GHz CPU平檯相比,加速比能夠達到56.8倍.
HMMer시용PHMM래대단백질혹안기산서렬사순진행분류화필배적생물신식학연건공구포,단시유우HMMer적병행특성,HMMer재전통적천행화CPU평태상운행십분모시.채용FPGA대HMMer적핵심산법P7Viterbi진행가속,재P7Viterbi산법중존재일개한제병행성적다층순배적질대간수거의뢰관계,이전적공작도시홀략해순배반궤혹자천행화저부분정서,종이도치정도화효솔적강저.제출료일충기우FPGA적가이괄응P7Viterbi적수거의뢰특성적기우맥동진렬적병행운산결구,채용자동중산궤제래해결조애계산병행적회변문제.재FPGA중통과병행류수기술실현적가속계통능구유효지제고HMMer적운산효솔.실험결과표명,제출적대유20개운산단원적결구화Intel Core2 Duo 2.33 GHz CPU평태상비,가속비능구체도56.8배.
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 maxi-mum 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.
