学位论文 > 优秀研究生学位论文题录展示

生物序列分析算法硬件加速器关键技术研究

作　者: 夏飞
导　师: 窦勇
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 生物序列分析可重构计算现场可编程门阵列细粒度并行硬件算法加速器全局动态重构
分类号: TN791
类　型: 博士论文
年　份: 2011年
下　载: 47次
引　用: 0次
阅　读: 论文下载

内容摘要

生物序列分析是现代生命科学领域重要的基础性研究工作,由于该领域应用的广泛性、程序特征的复杂性以及海量数据特征对计算机性能提出越来越高的要求,迫切需要高性能计算的支持。现有的基于CPU和GPU的通用计算平台虽然能够提供很强的峰值计算能力,但是不能在运算粒度、存储调度、计算适应度方面主动拟合应用的特点,难以应对生物序列分析领域细粒度的位级操作和不规则的计算、存储需求,实际应用效率低。近年来,FPGA器件以其可编程特性、细粒度并行能力、丰富的计算资源、灵活的算法适应性、低硬件代价和高性能功耗比成为理想的定制计算平台。本文针对生物序列分析应用在通用计算平台上并行性能不高的问题,基于通用微处理器结合FPGA可重构算法加速器的异构体系结构,研究了该领域典型计算方法的细粒度并行化问题。以存储优化为核心,集中解决了可重构算法加速器设计中面临的若干技术难点,构建了面向序列分析应用的动态可重构原型系统,实现了对典型生物信息序列分析过程的定制计算,达到了提高特定应用性能和降低系统功耗的双重目标。本文取得的重要研究成果如下:1.针对不同领域动态规划算法的数据相关性和存储访问特征,基于FPGA平台提出了资源受限条件下的数据相关性转换、负载平衡的任务划分和存储调度策略,设计了并行计算结构,对典型算法实现细粒度并行。具体包括:针对回溯条件下序列比对过程存储需求膨胀的问题,提出了节省存储需求的细粒度并行算法,采用区域划分和计算策略解决了长序列比对面临的FPGA片内逻辑和存储资源受限问题;利用二维串行动态规划问题具有的固定数据依赖和矩阵反对角线元素不存在数据相关的特点,提出基于同构线性阵列对矩阵反对角线元素实现并行计算的方法和加速器结构模板;采用等值罚分和仿射罚分模型分别实现了无回溯、片内回溯和片外回溯三种序列比对设计方案,比较全面地解决了序列比对应用的硬件加速问题。针对RNA二级结构预测领域三维非串行动态规划算法中变化的数据相关距离、不规则计算和非连续存储问题,提出了一系列提高存储效率的优化措施:通过重组单元计算顺序提高数据局部性,通过数据重用减少片外存储访问开销,通过数据预取和缓存、同步点写回等措施隐藏片外访问延迟,实现计算和通信的平衡;利用反对角线元素计算量相等且不存在数据依赖的特点,提出了细粒度并行算法和基于主从多处理单元的加速器设计模板;利用列元素计算量之差只与列坐标相关的特点,采用“区域分割”和“按列轮转划分”的层次化任务分配策略实现处理单元间的负载均衡;基于加速器设计模版,在国际上首次实现了对Zuker、RNAalifold和CYK三种典型算法的硬件加速,取得了10倍以上的加速效果。针对带假结RNA结构预测领域的四维动态规划算法中复杂数据相关性和存储带宽受限的问题,提出了“时空域重叠”的数据相关性分析方法;通过对访存请求的动态调度减少片外存储访问的随机性,降低了50%的存储带宽需求;采用基于多处理单元的异构线性阵列结构,实现了对四维动态规划矩阵的细粒度并行计算,相对于通用计算平台取得了3~5倍的加速效果。2.针对启发式序列数据库搜索算法中存在的种子检测效率不高的问题,提出一种不基于常规查询策略的并行多种子检测算法和基于线性结构的并行多种子搜索阵列;采用阵列分组和并行种子收集、组内种子合并和多种子并行扩展策略实现了无阻塞的数据库搜索,成功对BLAST数据库搜索算法实现硬件加速。3.针对基于HMM模型的随机搜索过程中紧耦合的数据相关导致矩阵元素无法并行计算的问题,提出粗细粒度混合的HMM模型并行计算方法,即对单个元素内部状态的计算实现细粒度并行,对“模型—序列”间的匹配过程实现粗粒度并行。与目前最好的硬件加速方案相比,单PE的计算性能提升了30%;与运行在通用计算平台上的搜索程序相比,可获得接近200倍的全局加速效果。4.以蛋白质结构预测为应用背景,提出了贝叶斯网络模型的细粒度并行方法和计算结构。针对模型的串行结构和不同处理阶段负载不匹配的问题,提出了多阶段混合流水处理策略和细粒度并行计算结构,采用关键流水段复制实现了流水线负载平衡;针对模型参数的共享访问竞争和地址间隔访问的特点,采用参数表分割、复制和传递策略提高参数访问效率,首次对基于贝叶斯统计和网络模型的蛋白质结构预测应用成功实现硬件加速。5.以大容量FPGA芯片和SDRAM存储器为基础设计了硬件算法加速器,与通用微处理器结合构建了基于异构体系结构的序列分析原型系统,并开发了序列分析应用程序集和FPGA配置文件库,采用FPGA动态全局重构技术实现了不同应用间的快速切换,提高了原型系统对应用程序的适应性,达到了对生物序列分析典型应用的整体加速效果。研究结果表明,本文提出的通用微处理器结合可重构FPGA算法加速器的异构计算平台对生物序列分析应用具有显著的加速效果,并能实现提高计算性能和降低系统功耗的双重目标。

全文目录

摘要  13-15
Abstract  15-17
第一章绪论  17-41
  1.1 课题背景  17-35
    1.1.1 生物序列分析研究现状  17-23
    1.1.2 序列分析领域典型计算方法  23-25
    1.1.3 序列分析领域高性能计算的现状和挑战  25-35
  1.2 研究内容  35-37
    1.2.1 典型序列分析方法计算特征提取  35-36
    1.2.2 动态规划算法并行化研究  36
    1.2.3 启发式数据库搜索算法并行化研究  36-37
    1.2.4 随机过程数据库搜索算法并行化研究  37
    1.2.5 基于贝叶斯模型的蛋白质结构预测算法并行化研究  37
    1.2.6 动态可重构序列分析原型系统构建  37
  1.3 主要工作和贡献  37-39
  1.4 全文组织结构  39-41
第二章基于二维动态规划的序列比对算法并行化研究  41-67
  2.1 序列比对  41-49
    2.1.1 序列比对简介  41-44
    2.1.2 问题描述  44-45
    2.1.3 典型序列比对方法  45-49
  2.2 二维动态规划算法细粒度并行方法  49-53
    2.2.1 算法并行化的主要难点  49
    2.2.2 算法计算特征分析  49-50
    2.2.3 细粒度并行算法  50-53
  2.3 算法加速器设计与实现  53-63
    2.3.1 研究现状  53
    2.3.2 双序列比对算法并行计算结构  53-62
    2.3.3 多序列比对算法并行计算结构  62-63
  2.4 实验结果与性能分析  63-66
    2.4.1 双序列比对  63-64
    2.4.2 多序列比对  64-66
  2.5 本章小结  66-67
第三章基于高维动态规划的RNA 结构预测算法并行化研究  67-111
  3.1 RNA 简介  67-71
    3.1.1 RNA 结构  67-69
    3.1.2 RNA 二级结构预测  69-70
    3.1.3 典型RNA 二级结构预测方法  70-71
  3.2 三维动态规划问题细粒度并行方法  71-90
    3.2.1 问题描述  71-75
    3.2.2 研究现状  75-76
    3.2.3 计算特征分析  76-81
    3.2.4 按列轮转的任务划分策略  81-82
    3.2.5 细粒度并行算法  82-84
    3.2.6 存储优化策略  84-90
  3.3 四维动态规划问题细粒度并行方法  90-101
    3.3.1 问题描述  91
    3.3.2 研究现状  91-92
    3.3.3 计算特征  92-94
    3.3.4 数据相关性分析  94-99
    3.3.5 细粒度并行算法  99-101
  3.4 系统设计与实现  101-105
    3.4.1 三维动态规划算法并行计算结构  101-104
    3.4.2 四维动态规划算法并行计算结构  104-105
  3.5 实验结果与性能分析  105-110
    3.5.1 资源利用率  105-106
    3.5.2 加速性能  106-109
    3.5.3 性能分析  109-110
  3.6 本章小结  110-111
第四章基于启发式和随机过程的序列搜索算法并行化研究  111-135
  4.1 生物数据库搜索研究现状  111-113
    4.1.1 生物数据库简介  111-112
    4.1.2 数据库搜索面临的挑战  112-113
  4.2 典型序列数据库搜索方法  113-114
    4.2.1 基于序列两两比对的精确搜索方法  113
    4.2.2 基于“种子—扩展”的启发式搜索方法  113-114
    4.2.3 基于隐马模型的随机过程搜索方法  114
  4.3 基于“种子—扩展”的并行搜索方法  114-124
    4.3.1 算法简介和计算特征  114-116
    4.3.2 研究现状  116-117
    4.3.3 并行多种子检测算法和线性搜索阵列  117-119
    4.3.4 提高阵列搜索效率的优化策略  119-123
    4.3.5 BLAST 算法并行计算结构  123-124
  4.4 基于HMM 模型的并行搜索方法  124-130
    4.4.1 Viterbi 算法简介  124-125
    4.4.2 算法计算特征  125-126
    4.4.3 研究现状  126-127
    4.4.4 粗细粒度混合的并行方法  127-128
    4.4.5 Viterbi 算法并行计算结构  128-130
  4.5 实验结果与性能分析  130-134
    4.5.1 BLAST 算法加速性能  130-132
    4.5.2 Viterbi 算法加速性能  132-134
  4.6 本章小结  134-135
第五章基于贝叶斯方法的蛋白质结构预测算法并行化研究  135-155
  5.1 蛋白质简介  135-136
    5.1.1 蛋白质组成  135-136
    5.1.2 蛋白质结构  136
  5.2 蛋白质结构预测  136-144
    5.2.1 蛋白质结构类型预测  137-138
    5.2.2 蛋白质二级结构预测  138-140
    5.2.3 蛋白质三级结构预测  140-142
    5.2.4 贝叶斯方法基本原理  142-144
  5.3 蛋白质结构预测细粒度并行方法  144-152
    5.3.1 问题描述  144-148
    5.3.2 研究现状  148-149
    5.3.3 贝叶斯网络模型计算特征  149
    5.3.4 细粒度并行方法  149-152
  5.4 系统设计与实现  152-153
    5.4.1 蛋白质二级结构预测并行计算结构  152
    5.4.2 蛋白质三级结构预测并行计算结构  152-153
  5.5 实验结果与性能分析  153-154
    5.5.1 FPGA 实现  153
    5.5.2 加速性能  153-154
  5.6 本章小结  154-155
第六章动态可重构序列分析原型系统构建  155-181
  6.1 系统总体结构  155-157
    6.1.1 系统组成  155-156
    6.1.2 FPGA 算法加速器  156-157
  6.2 通用计算组件设计  157-166
    6.2.1 多功能IO 接口控制器  158
    6.2.2 PCI-E 接口  158-159
    6.2.3 DMA 控制器  159-162
    6.2.4 可配置SDRAM 存储控制器  162-166
  6.3 系统动态重构  166-172
    6.3.1 FPGA 重构  167-168
    6.3.2 Virtex-5 FPGA 配置端口  168-169
    6.3.3 全局动态重构  169-170
    6.3.4 动态任务切换  170-172
  6.4 性能评价  172-180
    6.4.1 性能评价指标  172-174
    6.4.2 算法级性能评价  174-177
    6.4.3 系统级性能评价  177-180
  6.5 本章小结  180-181
第七章结论与展望  181-185
  7.1 工作总结  181-182
  7.2 工作展望  182-185
致谢  185-187
参考文献  187-203
作者在学期间取得的学术成果  203-205
作者在学期间参与的科研工作和所获专利  205

生物序列分析算法硬件加速器关键技术研究

内容摘要

全文目录

相似论文