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

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

作　　者：徐琳[1] 李晓民[1] 谭光明[1] 刘新春[1] 卜东波[1] 冯圣中[1] 孙凝晖[1] 

机构地区：[1]中国科学院计算技术研究所国家智能中心

出　　处：《计算机学报》2006年第2期233-238,共6页Chinese Journal of Computers

基　　金：中国科学院知识创新工程重大项目基金(KSCX2-SW-223);国家自然科学基金(60403025)资助~~

摘　　要：动态规划是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.

关 键 词：RNA 二级结构预测 FPGA 并行 流水 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]