论文部分内容阅读
图数据是许多计算、科学和工程领域中经常采用的数据结构,图操作则是构建这些领域中许多应用的基石。一直以来,设计高效的图算法就是数学与计算机科学的重要研究内容。随着算法理论的成熟,研究人员意识到传统的串行图算法几乎已达到理论上的时间复杂度极限,它们在生物基因工程、Web网络分析、地理信息系统等新兴应用产生的海量数据前遭遇到性能瓶颈。开发并行的图算法势在必行。然而,大多数研究集中在以CPU为处理部件的传统并行架构上,受到处理器核心数限制和通信代价方面的挑战。现代图形处理器(Graphic Processing Units,GPUs)具有运算核心数量多、运算能力强、高带宽的架构优势。近年来,利用GPU进行通用计算(General Purpose Computation on GPU,GPGPU)成为高性能计算领域新的趋势。目前,GPGPU领域的图算法研究还处于起步阶段,图算法具有的不规则访存性增加了设计的难度。除此之外,也不是所有的图算法都能够被有效地并行,比如深度优先搜索本质上就是串行的。本文研究和归纳了在CPU和GPU上设计实现并行图算法的研究现状,分析了GPU上图的数据表示,开发了基于统一计算设备架构(Compute Unified Device Architecture,CUDA)的并行算法以用于求解强连通分量(SCC)、最小生成树(MST)以及每对顶点间的最短路径(APSP)等三种图问题。首先,本文实现了基于CUDA的计算SCC的FB算法,在算法中引入了枝剪过程,并考虑到了线程分歧的影响;接下来,设计了一种Kruskal算法和Boruvka算法相结合的混合MST算法,它使用基于CUDA的基数排序与前缀和Scan原语来划分子图、构造子图结构以及过滤边,并用Boruvka算法的CUDA实现来求解子图的最小生成树森林;然后,受到基于CUDA的单源最短路径(SSSP)算法的启发,开发了一种利用SSSP求解APSP的并行方案,该方案一次求解多个源顶点的SSSP问题,能有效地利用GPU片上的共享内存。最后,本文以实验作为手段,测试了算法在不同规模的三种合成图Random、RMAT、SSCA#2上的性能,数据表明,这些基于CUDA的算法确实取得了一定的加速比。