图形处理器(Graphics Processing Unit,GPU)在功能和性能上逐步增强,在浮点计算性能和存储带宽已远超CPU。如今GPU不只局限于传统的图形渲染功能,已成为一种流行的通用计算设备。自NVIDIA公司推出计算统一设备架构(Compute Unified Device Architecture,CUDA),基于CUDA的高性能并行计算已成为各领域的研究热点。本文从传统问题着手,选择典型算法,优化其在GPU上的执行效率。论文主要选择了稀疏矩阵向量乘法(Sparse Matrix-Vector Multiplication,SpMV)和平面点集凸包算法。SpMV常用于挖掘网络数据信息的算法中,对分析网络抗毁性、鲁棒性以及控制谣言传播有重要作用。稀疏矩阵的存储格式对SpMV的性能影响巨大,为了提升其运算性能,对稀疏矩阵存储格式的优化至关重要。凸包算法是计算几何的重要构成,在非图像领域它也广泛应用于信息安全系统。快速凸包算法(QuickHull)是一种典型的分治法,将分治法映射到GPU架构上还没有一般性的高效方法。针对上述问题,本文基于CUDA高性能计算平台,对GPU上的SpMV和凸包算法进行了改进和优化。论文基于分块行列存储(Blocked Row-Column,BRC),提出一种改进的数据结构,用于存储稀疏矩阵以便在GPU上准确高效计算。该存储格式通过一种二维分块策略和一个基于快速分段求和的GPU内核函数,极大减少了BRC格式在并行环境中的计算误差。采用多种真实世界矩阵数据,在GPU上评估该方法,对于SpMV和使用该操作的PageRank中,实验结果表明,本文提出的方法得到的SpMV结果比BRC格式更具有准确性和再现性,同时保持了良好的运算性能。论文基于一种针对现代GPU的并行分治法实现策略,提出一种改进的并行凸包算法,以实现对大规模点集的快速凸包构造。算法通过引入分段的概念,对最初分配的输入数据进行直接操作,并将其划分至不同的分段来执行分而治之的过程。通过设计分段划分和分段压缩这两种数据并行操作,提出基于GPU的并行QuickHull算法。基于几个广泛使用的基准数据集进行了丰富的实验,实验结果表明,与目前最先进的Qhull库相比,本文提出的方法在耗时上明显更少,充分利用了GPU的性能。