面向生物序列分析的算法加速器关键技术研究

论文摘要

生物序列分析是进行生物信息学研究的基础之一,具有重大的理论和应用价值。随着生物序列数据库规模的快速增加,生物序列分析对数据的处理能力提出了更高的要求,迫切需要高性能计算的支持。采用FPGA构建动态可重构加速系统是进行高性能计算研究的重要手段之一,能够为生物序列分析的研究提供有力的支持。序列比较分析和序列拼接是生物序列分析的两个重要方面,本文中对其算法加速器技术进行了研究。针对序列比较分析,分别以Smith-Waterman算法、ClustalW程序、Phrap程序为例对双序列比对、序列搜索、多序列比对进行了研究,提出了双序列同步送入阵列、中间结果送入外部存储器、多种子并行检测、多路并行扩展等解决方案。与软件相比,加速器分别可以达到1555倍、27倍、24倍以上的加速比。本文以Phrap程序为例对序列拼接算法加速器技术进行了研究。对Phrap程序进行了程序特征分析,选取其核心函数进行了硬件加速。采用了简化的索引方式减少进行比对的片段数量,采用脉动式阵列结构快速定位片段中的匹配词,采用双路并行方式对匹配区域进行比对。与软件相比,加速器可以达3.5倍的加速比。本文对序列分析加速器中的数据结构硬件设计以及存储优化技术进行了研究,分别对栈、队列、链表、树、图等典型数据结构进行了分析,提出了适合其应用特点的硬件设计方法,并进行了存储优化设计。本文还对加速器原型系统构建技术进行了研究,提出了动态可重构原型系统的组成结构,对高速I/O通道PCI Express的控制技术和高速大容量外部存储器DDR2 SDRAM的控制技术进行了研究,并在原型系统中进行了实现。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题背景
• 1.2 课题研究现状
• 1.2.1 序列比较分析硬件加速研究现状
• 1.2.2 序列拼接硬件加速研究现状
• 1.3 本课题研究内容
• 1.4 论文结构
• 第二章 序列比较分析算法加速器技术研究
• 2.1 双序列比对算法加速器技术研究
• 2.1.1 双序列比对算法特征分析
• 2.1.2 优化方案
• 2.1.3 硬件结构设计
• 2.1.4 实验结果
• 2.2 序列搜索算法加速器技术研究
• 2.2.1 算法特征分析
• 2.2.2 硬件结构设计
• 2.2.3 实验结果
• 2.3 多序列比对算法加速器技术研究
• 2.3.1 算法特征分析
• 2.3.2 硬件结构设计
• 2.3.3 实验结果
• 2.4 本章小结
• 第三章 序列拼接算法加速器技术研究
• 3.1 序列拼接算法特征分析
• 3.1.1 序列拼接算法原理
• 3.1.2 序列拼接程序加速设计分析
• 3.2 硬件结构设计
• 3.2.1 设计分析
• 3.2.2 解决方案
• 3.2.3 硬件结构设计
• 3.3 实验结果
• 3.4 本章小结
• 第四章 序列分析应用中典型数据结构的存储优化技术研究
• 4.1 栈结构的硬件设计
• 4.1.1 设计分析
• 4.1.2 结构设计
• 4.2 队列结构的硬件设计
• 4.2.1 设计分析
• 4.2.2 结构设计
• 4.3 链表结构的硬件设计
• 4.3.1 设计分析
• 4.3.2 结构设计
• 4.4 树结构的硬件设计
• 4.4.1 设计分析
• 4.4.2 结构设计
• 4.5 图结构的硬件设计
• 4.5.1 设计分析
• 4.5.2 结构设计
• 4.6 本章小结
• 第五章 构建算法加速器原型系统的实现技术研究
• 5.1 原型系统设计
• 5.2 高速I/O 通道控制器关键技术
• 5.2.1 高速I/O 通道PCI-E 概述
• 5.2.2 PCI-E 总线基础
• 5.2.3 DMA 控制器设计
• 5.2.4 DMA 控制器驱动程序设计
• 5.3 高速大容量外部存储控制器关键技术
• 5.3.1 动态存储器技术
• 5.3.2 存储控制器结构设计
• 5.3.3 高速数据信号采样技术
• 5.4 本章小结
• 第六章 结束语
• 6.1 工作总结
• 6.2 进一步的工作
• 致谢
• 参考文献
• 作者在学期间取得的学术成果