基于FPGA的并行RNA二级结构预测加速算法研究

摘要

随着生物信息学的不断发展,人们对生物信息数据的处理和分析能力提出了更高的要求。虽然生物信息学的算法相对简单,运算类型单一,但是算法数据量较大,重复性很强,而且潜在的并行度较高。预测RNA分子的二级结构就是一个典型的这类问题。随着RNA序列数量与日俱增,受限于三维动态规划方法的计算复杂度,现有的软件预测方法已不能满足研究需求,因此迫切需要高性能计算的支持。基于FPGA(Field Programmable Gate Arrays)平台的算法加速器是高性能计算研究的重要方向之一,因此,对RNA二级结构预测算法进行异构计算平台上的并行化开发,从而实现算法加速,是一个热点的研究方向。
　　本文首先对RNA二级结构预测领域的主要研究情况进行了较为全面的论述与总结,并选择了目前主流的基于最小自由能的预测算法中具有代表性的Nussinov算法进行研究。通过详细的分析了Nussinov算法中的数据相关性,分别提出了针对格点内并行性和针对格点间并行性的并行加速方案。同时,为了解决存储器容量需求过大以及存储器写入带宽对加速器结构性能的影响,本文提出了取模映射和基于存储平衡优化策略的两种存储结构。经验证,在序列长度较长的应用情景下,该存储策略能够获得较好的存储利用率,因此是一个较为可行的方案。我们在Xilinx ML605 FPGA平台上对两种并行实现方案进行了具体实现,验证了本文提出的并行加速算法的功能的正确性,在p路并行的情况下能够将Nussinov算法的执行效率提高到接近p倍,因此,能够很好的实现对Nussinov算法进行加速的目的。

目录

封面

声明

中文摘要

英文摘要

目录

图 录

表 录

第一章 绪论

1.1 课题背景

1.2 高性能 RNA 二级结构预测的研究现状

1.3 课题研究的目的和主要内容

1.4 本文组织结构

第二章 RNA 二级结构预测算法概述

2.1 RNA 结构基础理论

2.2 RNA 二级结构预测算法

2.3 Nussinov RNA 二级结构预测算法分析

2.4 本章小结

第三章 针对格点间并行性的 Nussinov 加速结构

3.1 简单的加速结构

3.2 改进的加速算法硬件结构

3.3 性能与存储需求分析

3.4 本章小结

第四章 针对格点内并行性的 Nussinov 加速结构

4.1 并行加速算法概述

4.2 加速算法硬件结构

4.3 性能与存储需求分析

4.4 本章小结

第五章 实现与结果分析

5.1 并行算法的实现与功能验证

5.2 并行算法加速性能验证

5.3 本章小结

第六章 总结与展望

6.1 主要工作内容和创新点

6.2 后续研究工作

参考文献

致谢

攻读硕士学位期间已发表或录用的论文