稀疏线性系统中基于GPU的预条件共轭梯度法并行优化方法的研究

作     者：丁萍 

作者单位：华南理工大学 

学位级别：硕士

导师姓名：黄敏;王婷

授予年度：2015年

学科分类：08[工学] 080203[工学-机械设计及理论] 0802[工学-机械工程] 

主      题：预条件共轭梯度法 稀疏矩阵向量乘 CSR格式 GPU Xeon Phi 

摘      要：由于图形处理器(Graphics Processing Unit,GPU)的性能得到较大提高,不但促进了计算机仿真和图像处理等应用领域的高速发展,而且为人们提供了更好的运行平台来利用GPU进行除了图形处理以外的通用计算。在科学计算的领域中,用迭代法来求解大型稀疏线性系统在城市大气污染的湍流模拟、视频处理、流体和力学、材料模拟与生物医药等实际应用中具有重要的意义。非计算密集型类算法在数值类算法中的内存墙问题比较严重,而在利用GPU做并行优化时,这个问题尤为突出。稀疏矩阵向量乘算法是此类问题的典型代表,解决方法是使用压缩存储格式表示稀疏矩阵,设计一种基于GPU的稀疏矩阵向量乘并行算法,进而通过CPU和GPU协作的方式对预条件共轭梯度算法进行加速,本文的目标是取得如下的成果:1.分析解决稀疏线性系统中的预条件共轭梯度算法中最为耗时的是稀疏矩阵向量乘的计算,根据对称矩阵的特点和GPU多线程并行计算的要求,从存储格式、存储器层次、任务划分和线程映射等方面对稀疏矩阵向量乘的计算进行加速。2.本文提出预条件共轭梯度法在GPU上的优化方法。本文有效利用GPU的多层次的存储器体系,采用线程与矩阵映射、数据合并访问、数据复用等优化手段,有效利用GPU的多层次的存储器体系,并通过高效的线程调度来隐藏全局存储器的高延迟访问。3.本文提出预条件共轭梯度法在Xeon Phi上的优化方法。有效利用Xeon Phi的高并行度计算对数据通信/传递、减少数据依赖、向量化、异步计算等进行优化,并通过高效的线程调度来隐藏全局存储器的高延迟访问。本文提出了一种基于求解含有特征问题的大规模稀疏矩阵的并行共轭梯度算法。分别在GPU处理器上的计算和Xeon Phi处理器上进行并行优化,通过实验验证了算法的可行性和正确性,并对比几种方式下的运行效率,得出在GPU下比在Xeon Phi下运行效率高。最后在公共测试集上分别测试了本文提出的两种优化方法,相比较其他近年来的优化效果,取得了更好的优化效果,具有普遍意义。