图（Graph）作为一种基础的数据结构,采用顶点和边的连接来表示对象之间的复杂关系。由于其结构的灵活性,图结构已经被广泛用来表达社交网络、化学和物理、以及生物信息学等多种应用领域中对象之间的复杂关系。随着不同应用领域之间的交叉融合发展,图处理作为众多应用领域的关键数据处理方法之一,在数据处理领域的重要性已经不言而喻。应用领域的数据增长和不同应用领域的深度融合,给图数据处理带来了一些新的挑战,如何应用一些新的数据处理硬件和技术来加速图数据处理算法成为当前图计算领域的一个研究热点。近年来,GPU（Graphics Processing Unit）加速器由于具备超高并行能力,被逐渐应用于高性能计算、大规模图数据处理以及智能数据处理等多种应用场景。针对图着色算法中存在的数据依赖问题,提出了一种以颜色为中心的两阶段图着色算法。主要的优化技术包括:（1）提出了一种GPU上的两阶段着色算法Feluca,算法结合了迭代式着色方法和遍历式着色方法。在第一阶段采用迭代式着色方法快速对大部分顶点进行着色,在第二阶段采用遍历式着色方法在避免颜色冲突的基础上对剩余顶点进行着色。（2）针对颜色传递过程中的局部死循环问题,设计了一种环消除策略。算法通过修改有向边的指向,消除图数据中的环结构,进而避免着色过程中的局部死循环。在此基础上,在迭代式着色阶段提出了一种自顶向下的颜色选择机制,通过给当前冲突顶点分配其父母顶点颜色值的下一个颜色值,来避免颜色选择过程中产生的冲突。（3）针对遍历式着色过程中由于颜色选择依赖导致的并行度低的问题,设计了一种以颜色为中心的线程组织策略。算法给每一个颜色值分配一个线程组,并且采用流水线（pipeline）的方式来管理所有的线程组,消除了计算过程中的数据依赖,提高了GPU着色算法的并行度。针对介数中心度算法中存在的内存膨胀和访存过程中指针跳跃的问题,设计并实现了一种基于路径合并的介数中心度计算方法以及一种临时空间合并的内存管理方法,在降低临时内存开销的同时加速GPU上的介数中心度计算。主要的优化方法包括:（1）设计了一种路径合并策略,通过合并迭代过程中局部最短路径实现全局最短路径的计算,对计算过程进行剪枝。（2）提出了一种面向局部内存的活跃队列维护和更新策略来提高GPU内存数据的局部性,算法采用一种部分和的方法来对多个遍历过程中的活跃队列进行合并,实现多个遍历过程共享一个活跃队列,从而降低计算过程中的临时内存开销。针对社区检测算法中存在的分支分歧问题,设计并实现了一种基于B树的并行重叠社区检测算法。主要的优化方法包括:（1）提出了一种基于B树的数据组织方法,将遍历过程中的目标数据组织成一种并行查找树,提高遍历操作的并行度。（2）实现了一种缓存（cache）感知的B树管理方法,将B树节点映射到GPU的缓存行（cache line）,提高GPU缓存利用率的同时降低访存开销。（3）实现了一种以线程组（Warp）为中心的线程组织策略,将B树节点和GPU线程组进行一一映射,消除了重叠社区检测算法中的分支分歧操作,从而提高GPU线程的利用率。综上所述,针对GPU上图处理算法优化过程中面临的数据依赖、内存膨胀和分支分歧等重要问题,研究了基于GPU的图着色、介数中心度和社区检测等典型算法,解决了GPU上图处理算法设计中面临的一些挑战,提高了GPU上图着色、介数中心度和社区检测算法的性能,对GPU等其他新型加速器上图处理算法的优化设计提供了技术参考。