GPU流式计算模型应用研究

论文摘要

当前市场主流处理器的发展趋势是多核化／众核化,即通过提高处理器核心数目保持计算性能的持续增长。最新的图形处理器已经能够提高兆级的FLOPS理论峰值,远远超出了市场主流多核CPU。本文以国家自然科学基金项目（60803054）、浙江省自然科学基金项目（Y1100069）和AMD-浙江大学合作项目为研究背景,针对流式计算模型及其应用展开研究,主要工作包括：1、在NVIDIA CUDA平台上实现了基因序列比对的分值计算部分。本文设计实现的Diamond Tiled Wavefront算法的效率能够达到传统的Tiled Wavefront算法的1.7倍,更充分的利用GPU的并行性,更快的返回两个序列串的局部最大匹配值。2、在NVIDIA CUDA平台上实现了基因序列比对的精确比对部分。本文设计实现的流式序列比对算法首次在GPU上实现精确返回各元素的位置匹配结果。3、在ATI Stream平台上实现了三维模型凸包生成算法。在GPU上解决了CPU代码中大量应用vector、queue、map数据结构的问题。同时本文也介绍了一些用于辅助或优化上述算法实现的通用流式算法。4、在NVIDIA GeForce GTX285和ATI Radeon 5870图形处理器上使用CUDA和OpenCL实现了以上算法,并使用一系列模型进行了测试。本文算法对于基于GPU的算法加速研究具有一定的通用意义,并能延伸到其他生物计算、几何处理等领域的相关问题。

论文目录

• 摘要
• Abstract
• 图目录
• 表目录
• 第1章 绪论
• 1.1 课题背景
• 1.2 GPU技术
• 1.2.1 GPU发展历程
• 1.2.2 GPU编程环境
• 1.3 流式计算
• 1.4 本文目标与结构
• 1.5 本章小结
• 第2章 GPU加速的基因序列比对Ⅰ——分值计算
• 2.1 引言
• 2.2 相关工作
• 2.2.1 Smith-Waterman算法
• 2.2.2 Wavefront算法
• 2.2.3 Tiled Wavefront算法
• 2.2.4 相关加速算法
• 2.3 Diamond Tiled Wavefront算法
• 2.3.1 相关名词
• 2.3.2 算法概述
• 2.3.3 计算步骤
• 2.4 TWF和DTWF算法的比较
• 2.4.1 时间开销
• 2.4.2 空间开销
• 2.5 相关流式算法
• 2.5.1 分批处理
• 2.5.2 取最大值
• 2.5.3 前缀和与数据流缩减算法
• 2.6 实验结果与分析
• 2.6.1 实验平台
• 2.6.2 实验结果
• 2.6.3 结果分析
• 2.7 本章小结
• 第3章 GPU加速的基因序列比对Ⅱ——精确比对
• 3.1 引言
• 3.2 相关工作
• 3.2.1 Hirschberg算法
• 3.2.2 Checkpoint算法
• 3.3 流式序列比对算法
• 3.3.1 查找起止位置
• 3.3.2 流式比对算法
• 3.4 实验结果与分析
• 3.4.1 实验平台
• 3.4.2 实验结果
• 3.4.3 结果分析
• 3.5 本章小结
• 第4章 GPU加速的三维模型凸包生成
• 4.1 引言
• 4.2 相关工作
• 4.3 三维凸包CPU生成算法
• 4.4 流式算法
• 4.4.1 三维凸包流式生成算法
• 4.4.2 算法流程
• 4.4.3 Vector和Queue数据结构的实现
• 4.4.4 Map数据结构的实现
• 4.4.5 其他实现优化
• 4.5 实验结果与分析
• 4.5.1 实验平台
• 4.5.2 实验结果
• 4.5.3 性能分析
• 4.6 本章小结
• 第5章 总结与展望
• 5.1 本文工作总结
• 5.2 未来工作展望
• 参考文献
• 攻读硕士学位期间主要的研究成果
• 致谢
• 作者简介