面向FPGA的RNA二级结构预测并行算法研究

FPGA-Oriented Fine-Grained Algorithm for RNA Secondary Structure Prediction

动态规划是RNA二级结构预测最主要的算法,文中提出一种对动态规划矩阵采用分块技术的细粒度并行算法,通过对数据依赖关系的分析,引入了流水的策略,提高了算法的效率.在时钟模拟器上验证了算法的正确性,获得了一系列关于并行加速比、空泡率、存储访问带宽等问题的模拟结果,确定了FPGA PE阵列设计中的基本参数,为FPGA成功实现奠定了基础.

Dynamic programming is the most important algorithm in RNA secondary structure prediction. This paper proposes a fine-grained parallel algorithm by blocking the dynamic pro gramming matrix. By the analysis to the data-dependence, the authors introduce pipeline to im prove the efficiency of algorithm. They validate the correctness through clock-level simulator and obtain a series of result about speedup, bubble ratio and storage access bandwidth. They deter mine some basic parameters for FPGA and settle the foundation of FPGA realization.