图算法一直是学术界和工业界的研究热点。随着社交网络和大数据爆炸式增长,基于大图数据的应用逐渐增多。Google提出了Pregel图计算系统,解决关于大图数据的分布式计算问题。Pregel编程模型为用户抽象分布式计算的实现细节,提供了简明的API实现图算法。随着GPU软硬件技术的发展,与CPU相比,GPU逐渐演变成为高度并行的多线程及多核处理器,同时具有强大的计算能力和超高的内存带宽。越来越多的图算法使用GPU来提升计算性能,并利用GPU的硬件特性优化图算法。但是目前大部分基于GPU的图计算研究都是针对特定的图算法,缺乏基于GPU的类Pregel系统,为图算法提供基于GPU的通用图计算系统。而且当前的系统尚未根据图算法特点和GPU硬件特性,对系统性能进行优化。因此,本文主要对基于GPU的图计算进行研究,以实现对基于GPU的Pregel编程模型进行改进,分析图计算出现的性能瓶颈问题,提出相关的系统级优化算法。基于以上研究成果,本文实现了基于GPU的图计算系统Pregel GPU。论文的主要工作如下:首先,讨论GPU体系结构的基础知识,归纳图计算的研究进展。着重阐述图计算系统的编程模型和执行流程,并分析相关系统的不足。其次,GPU线程具有细粒度并行的特点,改进传统的顶点编程模型,提出基于GPU的通用图编程模型—Edge-Vertex编程模型,为图算法提供类似Pregel的API。同时根据Edge-Vertex编程模型,设计图系统的执行流程,把整个系统执行阶段划分成预处理阶段、Edge Compute和Vertex Compute,并阐述各个阶段的执行任务和逻辑操作。最后,分析Edge-Vertex编程模型的性能瓶颈,提出相应的解决方案。由于基于GPU的图计算存在线程负载不均衡问题,提出基于GPU的近似排序算法,缓解线程任务分配不均衡的压力。根据GPU合并访问全局内存的特性,提出应用于消息缓存的数据重映射算法,减少非合并访存次数,提高全局内存的实际带宽利用率。实验显示在不同的数据集和图算法下,和其他基于GPU的图计算系统相比,本文实现的图计算系统可以达到1.6x—4.5x倍的加速比。