图形处理器（GPU：Graphics Processing Unit）传统上是作为一种外设用来加速3D图形渲染，但随着其功能和性能的逐步加强，如今它已经成为一种流行的通用计算设备。随着CPU单核心性能的进化陷入瓶颈，同时多核CPU正在蓬勃发展，需要把注意力从单线程程序转移到多线程程序上，才能从多核CPU中获益。这就要求开发者必须设计相应的并行算法来代替串行算法。现代GPU将多核处理器的设计思路推向了极致，在一块芯片上集成了成百上千个核心。与CPU相比，GPU具有高性能、高能耗比、低成本等优势，因此利用GPU来提升算法性能得到了广泛的关注。　　然而，GPU有自己独特的编程方式和算法设计思想，让习惯编写CPU程序的人很容易犯错，写出低效的GPU程序。因此需要深入研究GPU全新的编程模型，包括硬件结构、编程环境、程序执行方式以及性能优化方法等，对它们的深入研究和理解是设计高性能GPU算法的基础。在此基础上，高效实现了需要在后续算法中使用到的reduce、scan等原语操作，这些操作对于所提出算法的性能表现有至关重要的影响。　　图算法的大数据量、高并发度和高性能要求的特点使其很适合利用GPU进行处理，因此近几年来基于GPU的图算法研究成为了一个热点。广度优先搜索（BFS：Breadth-First Search）是最底层最基础的图算法之一，它一般作为其他复杂算法的构成单元，其性能对整个算法会产生重大影响，因此值得进行深入研究。现有的GPU BFS算法均存在较大的负载不均问题，导致算法的性能受图结构的影响较大，表现不够稳定。针对此问题提出了一个新的BFS算法，第一次实现了完全的负载均衡。该算法将每一轮BFS循环分解为两个阶段：工作重分配与邻接顶点获取。工作重分配阶段使用一个并行化的expand操作来从全局范围内重新组织输入的工作负载，然后邻接顶点获取阶段以负载均衡的方式实现对邻接顶点的并行访问。实验结果表明，对比CPU上的串行BFS实现与现有最高效的GPU BFS实现，所提出的算法分别能够取得最高39倍和1.42倍的性能提升。　　强连通分量（SCC：Strongly Connected Component）分解是另一个基础图算法。现有的GPU SCC分解算法基本上是CPU算法的直接移植，没有充分考虑GPU的架构特性，性能表现受到很大局限。针对这一问题，提出了一个新的SCC分解算法。它完全基于GPU架构，以前向和反向可达集合查询为基础，通过一种迭代形式的分治策略来识别每一个SCC。算法中引入了很多专门针对GPU架构所设计的优化方法，如基于BFS的高效多起点可达集合查询、可有效降低递归深度的Partition操作、高效的随机顶点选取方法、最优化的子图编号策略和顶点标记策略等。实验结果表明，对于CPU上最高效的Tarjan串行算法和现有的GPU算法，所提出的方法分别能够取得最高41倍和3.8倍的速度提升。