论文题目: 面向生物信息学的可重构计算技术研究
论文类型: 硕士论文
论文专业: 计算机系统结构
作者: 张佩珩
导师: 许鲁
关键词: 序列联配,动态规划,编辑距离,算法,可重构计算,硬件加速卡
文献来源: 中国科学院研究生院（计算技术研究所）
发表年度: 2005
论文摘要: 人类基因组测序工作完成后,对基因数据的处理和分析能力提出了更高的要求。计算是生物信息学的基本研究方法之一,其算法的特点是数据量较大、算法比较简单、运算类型单一、重复性较强、潜在的并行度较高。用现有的大规模并行机或超级服务器等通用系统解决这些问题,既浪费系统的资源,使用维护也比较复杂,有些问题甚至无法在限定的时间内完成。可重构计算就是一种行之有效的解决方案,这种解决方案不仅能够有效地对一些最常用的算法进行加速,而且能够快速适应算法的变化。本文的工作紧密结合面向生物信息处理的专用计算机系统这一项目的需求,分别基于PCI-X总线和DDR SDRAM总线设计实现了两种比较通用的算法可重构加速卡,并讨论了DDR SDRAM接口设计、PCI-X接口设计、ZBT SRAM接口设计等内容。在算法的硬件实现方面,本文系统地讨论了两条序列相似性的比较问题,详细阐述了编辑距离的原始算法和化简的方法以及从算法到逻辑的映射方法,根据这一方法提出了一种简单而高效的处理器单元(PE:Processing Element)的设计方法,并在此基础上进一步实现了脉动阵列的设计和完整的编辑距离算法核心处理逻辑电路设计。基于Altera公司的FPGA-Stratix 1S30,本文在加速卡上设计实现了3072个PE,其工作频率限定为133.3MHz,峰值计算能力为409.6GCUPS(Giga Cell Update Per Second)。加速比测试结果表明,与通用CPU相比,在序列比较长时(数十K对数百K长度),该卡最高可以得到3000倍以上的加速比,即使是在序列长度为几K时,也仍能取得两个数量级左右的加速比。在实际的应用中,本文利用硬件加速卡对多序列联配程序ClustalW的第一个计算步骤——序列两两最优联配过程进行了加速。测试过程中使用了随机生成的长度为3Kbp的序列,当序列的数量在100～1000条范围变化时,多序列联配的整体加速比与序列的数量基本上成正比关系,在这个范围内最高可以得到近35倍的整体加速比,显示出了硬件加速卡在实际系统中的良好的应用前景。在此基础上,本文又提出了一种面向蛋白质序列的局部联配算法的PE设计方法,该设计可以重用编辑距离算法的实现中的总线接口和片上控制逻辑,通过简单升级加速卡上的FPGA芯片就可以实现500倍以上的加速比。最后,作者对全文进行了总结,介绍了下一步的工作,并指出了将其他类型算法映射到该加速卡上的可行性。
论文目录:
第一章 引言
第二章 生物序列相似性的比较问题及算法
2.1 分子生物学中的几个基本概念
2.1.1 DNA
2.1.2 染色体和基因
2.1.3 RNA
2.1.4 变异
2.2 序列相似性比较的生物学的动机和问题的定义
2.2.1 序列联配的有关概念
2.2.2 序列联配问题的定义与分类
2.3 全局联配
2.3.1 全局最优联配原始算法
2.3.2 动态规划的思想在全局联配中的应用
2.4 局部联配(Local Alignment)
2.4.1 动态规划在局部联配中的应用
2.4.2 包括空位处罚的局部最优联配动态规划算法
2.5 小结
第三章 序列联配算法的加速方法
3.1 并行算法实现的类型
3.1.1 启发式算法
3.1.2 并行计算方法
3.1.3 硬件加速计算方法
3.2 硬件加速的典型工作
3.2.1 Splash 和Splash-2
3.2.2 BISP 和SAMBA
3.2.3 BioScan
3.2.4 Kestrel 系统
3.2.5 TimeLogic 公司DeCypher 系列产品
3.2.6 近期的其他相关工作
3.3 小结
第四章 全局联配算法的硬件实现
4.1 Altera Stratix FPGA 的原理与结构
4.1.1 Stratix 体系结构
4.1.2 查找表（Look-Up-Table)的原理与结构
4.1.3 逻辑单元LE 的结构
4.2 编辑距离的计算方法
4.3 编辑距离算法到逻辑的映射
4.4 编辑距离算法处理单元PE
4.5 编辑距离算法脉动阵列
4.6 编辑距离算法核心逻辑电路
4.7 小结
第五章 算法可重构加速卡的设计
5.1 两种加速卡的特点比较
5.2 Matrix-DIMM 型加速卡
5.2.1 DDR SDRAM 接口设计
5.2.2 ZBT SRAM 接口设计
5.2.3 Matrix-DIMM 加速卡FPGA 设计与实现
5.3 Matrix-PCI 型加速卡
5.3.1 PCI-X 总线接口的设计与实现
5.3.2 FPGA 内部总线的设计与实现
5.3.3 Matrix-PCI 加速卡FPGA 设计与实现
5.4 小结
第六章 可重构加速卡的计算过程及其性能测试
6.1 编辑距离算法在可重构硬件加速卡上的计算过程
6.2 编辑距离算法在可重构硬件加速卡上的性能测试
6.3 编辑距离算法在可重构硬件加速卡上的测试结果分析
6.4 ClustalW 多序列联配算法在加速卡上的的性能测试
6.5 小结
第七章 局部最优序列联配算法设计
7.1 蛋白质序列的局部联配
7.2 仿射空位处罚模型的局部最优序列联配算法
7.3 序列局部联配算法PE 设计
7.4 序列局部联配算法PE 在FPGA 中的实现
7.5 小结
第八章 结论和展望
参考文献
致谢
作者简历
发布时间: 2006-12-26
参考文献
- [1].基于编辑距离的序列聚类算法及其在临床异常检测中的应用[D]. 孙启航.江苏大学2017
- [2].基于图编辑距离的图匹配算法研究[D]. 齐彩霞.西安建筑科技大学2013
- [3].基于图编辑距离的自然景物识别[D]. 宋建昌.北京工业大学2013
- [4].基于图编辑距离的画像识别[D]. 和彦莉.西安电子科技大学2010
- [5].基于编辑距离算法的中文模糊匹配技术在大数据量环境中的应用[D]. 解天书.湖北大学2013
- [6].不确定图数据库中的图相似搜索方法研究[D]. 陈福洪.辽宁大学2017
- [7].基于贝叶斯方法和编辑距离的英文语法检查系统设计与实现[D]. 王冬.电子科技大学2014
- [8].Tai树编辑距离算法的存储优化与树的纵向归并算法[D]. 韦龙宝.中国工程物理研究院2015
- [9].编辑距离快速算法研究[D]. 王培培.东北大学2011
- [10].基于树编辑距离的网页信息抽取[D]. 刘晓波.中国石油大学(华东)2015
相关论文
- [1].生物信息学中的序列相似性比对算法[D]. 陈伟.中国海洋大学2006
- [2].生物信息学中序列拼接程序的并行化研究[D]. 杨琪.中国科学院研究生院（计算技术研究所）2002
- [3].支持向量机在生物信息学中的应用[D]. 翁建洪.东南大学2006
- [4].动态可重构FPGA的布局布线算法研究[D]. 施小祥.西安电子科技大学2007
- [5].生物信息学中的并行处理[D]. 刘维.扬州大学2007
- [6].基于FPGA的可重构计算技术的应用研究[D]. 史先龙.北京化工大学2006
- [7].计算智能方法在生物信息学中的应用[D]. 闫化军.电子科技大学2005
- [8].生物信息学中的模式发现算法研究[D]. 冯永志.黑龙江大学2005
- [9].聚类和分类技术在生物信息学中的应用[D]. 黄金.黑龙江大学2005
- [10].生物信息学中的若干组合问题[D]. 刘丙强.山东大学2006