图是一种强大的数据结构，它可以表达现实世界中事物之间错综复杂的关系，如城市之间道路的连接关系，网页之间的引用关系，人与人之间的社交关系。近年来GPU体系结构的蓬勃发展让人们看到了用GPU来进行通用计算的可能性。由于GPU能够提供大量并行线程，于是很自然地想到用它来处理图这种蕴含海量数据并行性的数据。但在GPU上实现一个高效的图应用程序仍旧面临着许多方面的挑战，其中包括串行化与工作量之间的矛盾，规则与不规则之间的矛盾，以及GPU并行编程本身的复杂度。为了解决这些问题，本文提出了一个轻量级GPU图处理框架。本文的研究工作和成果包括以下两点:　　(1)设计并实现了轻量级GPU图编程并行框架——Olive。Olive向用户提供了vertexSubset（顶点子集）数据类型和两组计算函数:用来进行边计算的edgeFilter和edgeMap，以及用来进行顶点计算的vertexFilter和vertexMap。使用Olive编程框架进行图编程就是对一系列的vertexSubset调用这两组函数的过程。所有的底层细节都被隐藏在了系统背后，用户只需要关注发生在边和顶点上的计算即可，而不需要关心和GPU有关的任何编程细节。vertexSubset在底层使用了两种不同的物理实现:基于队列的紧凑型表示和基于布尔数组的松散型表示。使用紧凑型表示作为edgeFilter的输入可以最小化工作量，使用松散型表示作为edgeFilter的输出则可以提高系统的并行性。为了证明Olive的实用性和有效性，本文基于Olive实现了三种常用的图算法（BFS、PageRank和Bellman-Ford单源最短路径），并通过实验评测了Olive系统的性能。实验表明，Olive的实现对串行版本的加速比最高可以达到20倍。　　(2)研究了图不规则性和GPU执行模型之间的关系。由于GPU中的线程以SIMD的方式执行，在边计算（edgeFilter和edgeMap）过程中，输入数据的不规则性会对性能产生很大的影响。为了理解输入数据对硬件利用率的影响，本文分析了15个来自不同应用领域的图的不规则度，并对图拓扑结构和SIMD利用率的关系进行了建模（以BFS算法为例）。由于现实世界中的图的结构往往有着有很大的差异，Olive框架采用了分组映射方案（用一组线程处理一个顶点），并允许用户调整线程组的大小，从而找到最高效(GPU硬件利用率最高)的实现版本。实验表明，使用可变大小的线程组映射方案能够显著提高系统性能。