CUDA计算技术在生物序列数据处理中的应用研究

摘要

目前新的高通量DNA测序技术能够在很短的时间内以较低的成本生成大量的序列数据，生物序列的数据量正以爆炸式的速度快速增长。与此同时，计算机处理器的频率已接近理论极限，这意味着现存的串行算法很难像以前一样依靠频率的提高获得性能提升。并行处理技术成为解决这一效率差异的必然选择之一。由于GPU比CPU拥有更强的计算能力和更高的内存带宽，而生物序列数据又具有数据量大、数据结构简单的特点，本文采用基于数据并行处理指令体系的GPU众核计算技术来实现生物序列数据的廉价高效处理。本文根据复杂程度的不同，精心筛选出若干个经典序列分析问题作为并行处理的研究对象，分别给出高效的数据并行算法设计，并通过CUDA并行计算平台加以实现、分析和优化。本文的主要贡献总结如下:
　　第一，对CUDA计算涉及的软硬件并行体系结构特点进行了比较全面的研究。基于GPU属于SIMD并行指令体系的特点，总结并归纳了常用的基本数据并行操作，为并行算法的设计和实现提供了基本的参考和指南。
　　第二，针对生物序列分析研究中最基本的开放阅读框架问题，通过运用直接和间接并行化两种方法，完成了六读码框翻译算法和序列频率统计算法的高效数据并行设计与实现，展示了数据并行算法设计的特点以及GPU通用计算技术的优势和局限，并给出了GPU计算的并行加速模型，用以衡量并行化效率。本文基于直接转换的方法设计了具有高度并行性的适合于GPU执行的六读码框翻译算法，其执行速度要比串行算法快5倍左右。然而序列频率统计过程的并行化就无法这么自然的表达，因为这个过程中包含严重的并行访问冲突和延迟，只能采用以排序和计算前置和操作进行替代的间接并行化方法。该间接并行频率统计算法基本能够达到相应串行算法的效率。并行开放阅读框架算法总的执行效率为串行算法的2倍左右。
　　第三，针对序列测定和分析中的重复序列检测问题，提出了一种通过构造字典次序来快速完成超短精确重复查找的数据并行算法，该算法的效率要比目前的串行算法提高一个数量级。DNA序列中的重复区域对许多关键生物功能发挥着至关重要的作用，重复序列检测也是生物信息学中一个必须解决的基本问题。本文详细说明了一个基于CUDA平台的快速数据并行超短精确重复查找算法的设计和实现过程，并以这些超短重复为种子，进一步提出了启发式的海明距离和编辑距离重复测定的数据并行化方法，并给出了可行的并行线程调度方案。并行重复查找算法设计过程中采用的按串行代码功能区逐步完成并行化的方法，不但可以快速确定并行化过程中面临的瓶颈问题，进而判定整个算法的并行化难度，而且便于并行程序的设计、调试、分析和优化，可以作为现存大多数串行算法实现并行化处理的参考。
　　第四，针对后缀数组构造问题，提出了一种新的以排序方法替代传统分组策略的并行后缀数组倍增构造算法，其数据并行执行效率明显高于同类串行算法。后缀数组广泛应用于序列分析、字符串匹配和文本压缩等领域，近年来，有关后缀数组构造和应用算法的不断探索构成了计算机科学中一个非常活跃的研究领域。在对现有串行算法进行了全面的分析和对比之后，通过抽象和等效替换的方法提出了一种适合于GPU计算的且更为简洁的并行后缀数组倍增构造算法，不但能独立完成后缀数组的并行构造，还可与现存的串行倍增算法结合使用，以达到更高的执行效率（速度可以达到同类串行算法3倍以上）。实验结果表明该算法在解决实际应用问题时，具有易于实现、执行速度快和可扩展性强等优点，是目前最快的单机运行算法之一。尤其是在处理小字符集的生物序列数据时，快于目前所有的串行算法。

目录

声明

摘要

第1章 绪论

1．1 研究背景与动机

1．2 国内外相关研究现状与分析

1．2．1 序列分析技术综述

1．2．2 高性能计算在序列分析领域的应用现状与分析

1．3 本文工作

1．3．1 本文的研究内容和主要贡献

1．3．2 本文的组织结构

第2章 CUDA数据并行计算技术

2．1 GPU众核计算简介

2．1．1 多核与众核计算

2．1．2 GPU众核计算的主要特点

2．2 CUDA多线程执行部件和机制

2．3 CUDA的存储体系

2．4 CUDA的线程同步机制

2．5 CUDA的编程模型和工具

2．5．1 CUDA的基本程序结构

2．5．2 CUDA程序的线程管理和映射方法

2．5．3 CUDA程序设计涉及的基本操作

2．5．4 软硬件实验平台及测试数据

2．6 本章小结

第3章 利用CUDA实现ORF算法

3．1 串行六读码框翻译算法

3．2 六读码框翻译算法的并行实现和优化

3．2．1 六读码框翻译算法的简单并行实现和性能分析

3．2．2 六读码框翻译算法的内存访问优化

3．3 序列频率统计算法的并行化研究

3．3．1 序列频率统计算法的无冲突并行化方法与性能分析

3．3．2 基于原子操作的并行计数排序算法的实现与性能分析

3．4 本章小结

第4章 并行重复序列匹配算法研究

4．1 现有串行重复序列匹配算法剖析

4．2 利用字典次序查找超短精确重复序列的算法(RSRF)

4．3 超短精确重复序列匹配算法的并行实现与性能分析

4．3．1 字典次序构造过程的并行实现

4．3．2 超短精确重复序列匹配算法的并行实现与性能分析

4．4 其它类型重复序列匹配算法的并行化研究

4．4．1 精确重复与非精确重复的联系

4．4．2 噬菌体控制元件测定的并行任务调度方案

4．5 本章小结

第5章 后缀数组构造算法的并行化研究

5．1 现有串行后缀数组构造算法剖析

5．1．1 后缀数组的相关定义

5．1．2 串行后缀数组构造算法的分类和可并行化研究

5．1．3 LS串行算法介绍

5．2 数据并行倍增算法的设计与实现

5．2．1 基于名次排序的数据并行后缀数组构造算法(DPPD)

5．2．2 数据并行倍增算法DPPD在GPU上的实现

5．3 并行倍增算法DPPD的性能分析与优化

5．4 本章小结

第6章 结束语

6．1 本文的主要贡献与结论

6．2 未来工作部分

参考文献

致谢

攻博期间发表的论文

作者简介