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

Krylov子空间方法的GPU加速算法研究

作　者: 秦晋
导　师: 胡庆丰
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: GPU CUDA Krylov子空间方法稀疏对角矩阵向量乘内积操作
分类号: TP391.41
类　型: 硕士论文
年　份: 2010年
下　载: 145次
引　用: 2次
阅　读: 论文下载

内容摘要

近几年来,通用图形处理单元(GPGPU)在体系结构、编程模型等方面迅速发展,可编程性不断提高,同时GPU的单精度浮点峰值性能已经从几个Gflops增长到几个Tflops。GPU开始越来越多的运用于通用计算,并且越来越多地应用到科学计算程序的加速研究当中。在科学计算领域中,迭代法求解大型稀疏线性系统在计算流体力学、数值天气预报、石油地震数据处理、材料模拟与设计等实际应用中具有重要的意义,Krylov子空间方法是求解大规模稀疏线性系统的有效算法,具有存储容量需求小和快速收敛等优点。然而在CPU上利用该算法求解稀疏线性系统时往往会耗费大量的时间,如何加速其求解具有重要的理论意义和实际应用价值。利用GPU加速Krylov子空间方法求解大型稀疏线性系统可以降低计算周期,提高计算效率,有利于加速多种实际问题的解决。本文通过对GPU体系结构和CUDA编程模型的分析,研究了Krylov子空间方法在NVIDIA GPU上移植的技术难点,包括稀疏矩阵中零元素对存储空间的浪费、稀疏矩阵向量乘在GPU上的实现、内积操作在GPU上的实现、GPU上实现算法中公式时产生的计算核心开销对性能的降低、NVIDIA GPU不存在归约操作、在NVIDIA GPU上需要采用针对性的优化方法等问题。通过CPU和GPU协作的方式使用CUDA编程模型在NVIDIA GPU上对算法进行了加速,取得了如下的成果:1,面向CUDA编程模型的算法优化。详细分析NVIDIA GPU的体系结构特点,首先NVIDIA GPU的一个重要特点就是具有复杂的存储层次结构,包括registers、shared memory、local memory、global memory以及两种只读存储器texture memory和constant memory,各种存储器在容量、速度方面有较大的差别,优化算法需要充分利用GPU内的高速存储器,例如shared memory、texture memory甚至是registers。CUDA中的一个与硬件联系比较紧密的概念是warp,在NVIDIA GPU实际运行程序时,warp才是真正的执行单位,在我们的程序优化中,从优化访存入手,线程束能符合warp或者half-warp的对其访问要求。2,提出稀疏对角矩阵的CDIA压缩存储格式。在DIA存储格式的基础上设计了一种新型的压缩存储格式CDIA,在该格式下能够获得较高的数据传输效率以及满足CUDA对数据的对齐访问。为满足CUDA对存储器的合并访问要求,CDIA压缩存储格式中包含了对压缩矩阵做了相应的转置处理的操作,这大大提高了GPU的访存性能,从而在Krylov子空间方法的几个核心操作中起到了重要的作用。在稀疏对角矩阵向量乘中,使用CDIA格式比使用普通DIA格式性能提高了50.3%。3,稀疏对角矩阵向量乘在GPU上的加速实现。使用CDIA压缩存储格式对矩阵进行压缩存储,将计算任务进行细粒度的任务分配,在NVIDIA C1060平台上使用CUDA编程模型,数据试验结果表明矩阵向量乘的性能有明显的提高,通过对访存、数据传输等的优化,在测试数据中,最高获得了单精度39.6Gflop/s和双精度19.6Gflop/s的浮点计算性能,性能在Nathan Bell和Michael Garland的基础上分别提高了7.6%和17.4%。4,内积运算在GPU上的实现及优化。内积运算的实现以归约操作的实现为基础,内积运算采用先乘法再归约的方式,借助shared memory在GPU上有良好的性能表现,单精度情况下,与CPU相比,达到了高达36.2倍的加速比。5,提出了Krylov子空间方法在GPU上的优化策略。对算法的优化主要从程序结构、主机与设备的通信以及CUDA编程模型下的存储层次结构等几方面入手,使用NVIDIA GPU上的高速存储部件,主要是shared memory来提高访存效率,同时使用pinned memory来提高通信带宽。这些措施大大提高了算法的整体性能。在NVIDIA C1060平台使用CUDA 3.0的测试结果中,双精度和单精度条件算法性能分别达到11.3Gflop/s和16.7Gflop/s,相比Intel四核处理器Q6600使用三级优化编译,加速比分别达到9.2倍和13.57倍。测试结果表明,在不同矩阵规模下算法的性能有较大的差异,这是由GPU的体系结构特点决定的,从测试数据可以看出,GPU在加速Krylov子空间方法求解线性系统中具有较大的优势。

全文目录

摘要  8-10
ABSTRACT  10-12
第一章绪论  12-19
  1.1 课题背景  12-14
    1.1.1 GPU 发展概述  12-14
    1.1.2 GPU 上加速稀疏线性系统  14
  1.2 相关工作  14-16
  1.3 面临的挑战  16-17
  1.4 本文研究内容和创新  17-18
  1.5 本文结构  18-19
第二章 GPU 和 Krylov 子空间方法  19-29
  2.1 NVIDIA GPU  19-21
    2.1.1 GT200 体系结构  19-20
    2.1.2 Fermi（GT300）体系结构  20-21
  2.2 CUDA 编程模型  21-26
    2.2.1 主机与设备  22-23
    2.2.2 存储层次结构  23-25
    2.2.3 线程层次结构  25-26
  2.3 Krylov 子空间方法  26-29
    2.3.1 Krylov 子空间方法介绍  26-27
    2.3.2 Krylov 子空间方法加速研究  27-29
第三章稀疏对角矩阵向量乘在GPU 上的实现  29-38
  3.1 数据处理方法  29-32
    3.1.1 稀疏矩阵处理方法  29-31
    3.1.2 CDIA 压缩存储格式  31-32
  3.2 稀疏对角矩阵向量乘的GPU 加速实现  32-34
  3.3 稀疏对角矩阵向量乘的优化  34-37
    3.3.1 多线程并行与减少线程切换开销  35
    3.3.2 优化存储合并访问  35-36
    3.3.3 使用shared Memory  36-37
  3.4 本章小结  37-38
第四章 Krylov 子空间方法在GPU 上的实现  38-49
  4.1 计算任务的划分  38-41
    4.1.1 任务划分的原则  38-39
    4.1.2 任务划分的方法  39-41
  4.2 计算核心的划分  41-42
    4.2.1 计算核心  41
    4.2.2 计算核心的划分方法  41-42
  4.3 Krylov 子空间方法的实现  42-46
    4.3.1 稀疏对角矩阵向量乘的GPU 加速实现  42
    4.3.2 内积操作在GPU 上的加速实现  42-44
    4.3.3 Grid 和Block 的维度设计  44-46
  4.4 Krylov 子空间方法的相关优化  46-48
    4.4.1 程序结构优化  46
    4.4.2 主机与设备的通信优化  46-47
    4.4.3 存储器优化  47-48
  4.5 本章小结  48-49
第五章性能评测  49-54
  5.1 实验环境  49
  5.2 矩阵向量乘的测试结果  49-51
    5.2.1 CDIA 格式在GPU 上的性能测试  49-50
    5.2.2 稀疏对角矩阵向量乘的性能测试  50-51
  5.3 内积操作的测试结果  51-52
  5.4 Krylov 子空间方法的测试结果  52-54
第六章结束语  54-56
  6.1 工作总结  54-55
  6.2 展望  55-56
致谢  56-58
参考文献  58-61
作者在读期间取得的学术成果  61

Krylov子空间方法的GPU加速算法研究

内容摘要

全文目录

相似论文