生物序列分析是现代生命科学领域重要的基础性研究工作,由于该领域应用的广泛性、程序特征的复杂性以及海量数据特征对计算机性能提出越来越高的要求,迫切需要高性能计算的支持。现有的基于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算法加速器的异构计算平台对生物序列分析应用具有显著的加速效果,并能实现提高计算性能和降低系统功耗的双重目标。