基于FPGA的细粒度并行CYK算法加速器设计与实现

• 作者: 夏飞 宋健 窦勇 雷国庆
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 生物信息学 RNA 二级结构预测 SCFG模型 并行CYK算法 FPGA 硬件加速器
• 年，卷（期）: 2010,（5）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 797-812
• 分类号: TP302
• 字数: 13380字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2010.00797

摘要

基于随机上下文无关文法(SCFG)理论模型进行RNA二级结构预测是目前采用计算方法研究RNA二级结构的一种重要途径.由于基于SCFG模型的标准结构预测算法(Coche-Younger-Kasami,CYK)巨大的时空复杂度,对CYK算法进行加速成为计算生物学领域一个极具挑战性的热点问题.CYK的并行性能受限于算法多维度、非一致性的数据依赖关系和较低的计算/通信比,现有的基于通用微处理器结构的大规模并行处理方案不能获得令人满意的加速效果,并且大规模并行计算机系统硬件设备的购置、使用、日常维护的成本高昂,其适用性受到诸多限制.文中在深入分析CYK算法计算特征的基础上,基于FPGA平台提出并实现了一种细粒度的并行CYK算法.设计采用了对三维动态规划矩阵"按区域分割"和"逐层按列并行处理"的计算策略实现了多个处理单元间的负载均衡;采用数据预取、滑动窗口和数据传递流水线实现处理单元间的数据重用,有效解决了计算和通信间的平衡问题;设计了一种类似脉动阵列(systolic-like array)结构的主从多PE并行计算阵列,并在目前最大规模的FPGA芯片(Xilinx XC5VLX330)上成功集成了16个处理单元(processing elements),实验结果表明作者提出的CYK算法加速器结构具备良好的可扩展性.当RNA序列长度为959bps,CM模型状态数为3145时,与运行在Intel双核E5200 2.5GHzCPU、2.0GB主存通用计算上的Infernal-1.0软件相比,可获得超过14倍的加速效果.配置一个FP-GA算法加速器的通用计算平台的综合处理性能与包含20个Intel-Xeon CPU的PC集群相当,而硬件成本仅为后者的20%,系统功耗不到后者的10%.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	窦勇	国防科学技术大学计算机学院	45	220	8.0	12.0
2	夏飞	国防科学技术大学计算机学院	5	31	4.0	5.0
3	雷国庆	国防科学技术大学计算机学院	3	8	1.0	2.0