现今,使用通用图形处理单元(General Purpose Graphics Processing Unit,GPGPU)用于高性能并行计算已经变得越来越流行。GPU的高计算吞吐量和高带宽使之成为加速大规模数据并行应用的理想平台。多媒体、数据挖掘、生物信息学等领域的许多应用在GPU上取得了比传统CPU更高的性能和能效比,但这些应用大多具有对GPU“友好”的规则的数据结构和并行访问模式。图处理算法是许多应用领域的基础。高性能计算和商业应用中的许多问题都是用图表示的,比如不完全LU分解,电子设计自动化,数据挖掘,Web分析,社交网络分析等。由于图的特性,在GPU上加速图算法存在着诸多挑战:图算法访存是输入相关的并且难以预测,在GPU上呈现出显著的线程发散和访存发散,线程之间的负载不平衡也是一个常见的挑战。本文即针对这些问题,研究图算法在GPGPU上的实现与优化,主要取得了如下成果:1)在GPGPU上实现了一种可扩展的高效图着色算法:该算法基于着色质量接近最优解的贪心算法,在保存顶点不能着的颜色时,设计了位向量数据结构,相比布尔类型,减少了存储开销,提高了数据重用性,减少了对高延迟的局部存储器的访问。算法针对图是只读的这一特性,将其缓存在只读数据缓存(Read-only Data Cache),进一步提升了访存性能。算法在NVIDIA Tesla K20c GPU上取得了很好的性能,实验结果表明:该实现性能为NVIDIA CUSPARSE库函数实现的2.3倍,并且所需要的颜色比CUSPARSE库少很多,是串行First-Fit算法的2.6倍。同时,该实现对于稀疏图扩展性很好。2)在GPGPU上实现了一种高效的强连通分量分解算法:该算法结合真实世界中图的拓扑结构特点,先使用FB算法计算图中的最大强连通分量,并进行了负载平衡;然后使用Coloring算法进行一次颜色传播,将剩余顶点分割成更多更小的子图;最后对每个子图并行地进行FB分解。通过该混合算法,提高了并行度,充分利用了GPU的计算资源,减少了迭代次数,加速了求解过程。该算法在NVIDIA Tesla K20c GPU上取得了很好的性能,实验结果表明:该实现性能为串行Tarjan算法的5.4倍,是Hong等的OpenMP实现的1.4倍,是Stuhl的CUDA实现的40多倍。