基于节点前沿的gpu广度优先搜索改进算法

《基于节点前沿的gpu广度优先搜索改进算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于节点前沿的GPU广度优先搜索改进算法YANGBo(杨博)1,2,LUKai(卢凯)1,2,GAOYing-hui(高颖慧)3,XUKai(徐凯)1,2,WANGXiao-ping(王小平)1,2,CHENGZhi-quan(程志权)4（1）中国国防科技大学并行分布式处理重点实验室，长沙410073（2）中国国防科技大学计算机学院长沙410073（3）中国国防科技大学电子与工程学院长沙410073（4）中国阿凡达科技公司广州510001摘要：广度优先搜索（BFS）是用于图遍历的一个重要的内核，并已被应用于许多图形处

2、理应用。人们一直在进行大量的研究致力于促进BFS的性能。已实现的最有效、最先进的GPU加速是NVIDIATeslaC2050GPU的GPU算法，它可以每秒遍历3.3×109条边。而现在有一种新的基于GPUBFS的节点前沿算法技术被提出了，其主要特点有三方面。首先，为了获得更好的处理负载平衡不规则的图，节点前沿扩大时引入虚拟队列任务分解和映射策略。其次，提出了一个全局重复数据删除检测方案，从节点前沿有效去除重复的节点。最后，使用擅于用来处理大前沿的自下而上的GPUBFS方法。实验结果表明，在不同的图形处理方面，该算法相

3、较于目前最先进的处理算法能够提高10%的效率。特别是，它表现出的在低直径无标度图上的遍历率是NVIDIA最先进的TeslaGPUK20C设备的2-3倍加速，峰值遍历率达到11.2×109边/秒。关键词：广度优先搜索；GPU；图的遍历；节点前沿1.引言图算法是许多特定的应用，如基因组序列装配和对于超大规模集成电路自动设计[1-2]的基础。随着社交网络的迅速成长，图算法被发现在网络中分析用户的关联分析和产品推荐[3-4]方面有着更重要的应用。广度优先搜索（BFS）是许多复杂的图算法的一个重要组成部分。它也是许多基准套装，

4、如Parboil[5]和Graph500[6]的超级计算机的基准的重要的内核。在图论中，给定图G=（V，E）和一个源点S，BFS的目标是计算从S到任意可达节点Vi的最短距离，或者说从S到Vi的边数。BFS是一种用于搜索图的策略，尤其是搜索基本上限于两个动作：（1）访问和检查的图的节点；（2）访问当前访问节点的相邻节点。BFS开始于一个根节点并检查所有的相邻节点。对于每个相邻节点，它会轮流检查哪个是未访问过的并重复该过程，直到所有节点都被访问过。它均匀地扩张已发现的节点（与S距离K）和未被发现的节点（距离K+1）之间的

5、节点边境的广度。已经有大量的前期工作[7-10]致力于加快BFS的速度，通过提高算法或采用不同类型的硬件，如CPU，GPU，MIC和FPGA.Fortunately的数据结构，BFS在本质上是高度并行的。由于GPU已经发展了并行计算的直接加速，最近，许多研究人员用它来进行科学计算[11-12]。GPU的加速是快速BFS的必然选择，而利用GPU的稀疏图的BFS计算是不平凡的。首次实现的GPUBFS[13]用原始的任务分解并没有最大化GPU的利用率。BFS是一种任务分配和存储器存取通常依赖于输入图形的结构的算法，由于图形

6、的不规则性，BFS并行与原始任务分解会造成严重的工作量不平衡和局部的内存访问较少，这将损害整体的并行。此外，它的所有线程都使用直接原子操作来管理节点边境的全局共享成本过于高昂。已经有一些前期工作在一定程度上解决了这些问题。一种经基任务分配方法[9]提出了解决因不当的任务分配给并行BFS带来的负载不平衡。第一个基于GPUBFS的节点边境算法[14]采用了分层的队列管理方案，来维护节点边境。到目前为止，最快的GPUBFS算法[15]依靠一种咦节点边境为序列的BFS算法，在一块NVIDIATeslaC2050GPU上实现每

7、秒遍历图上3.3×109条边。经过深入的研究，有两个关于现有基于GPUBFS的节点边境算法的问题，限制了GPU的性能。首先，任务分配和存储器的并行图表访问计算是高度不规则和数据相关的。其次，节点和其相邻节点的同时扩张导致重复的节点出现在节点边境。在此次工作中，我们提出了一个基于GPUBFS的节点边境算法，它包括四个主要操作：相邻节点采集，状态检查，全局重复数据删除和自下而上遍历。该算法采用了虚拟队列任务分解和映射策略，可有效做到对于不规则图形的工作量平衡。全局重复数据删除检测方案用于删除在节点边境的重复节点。此外，一

8、个基于GPU的自下而上的BFS方法被用来针对一些低直径图BFS方法中的大型边境，如无标度和小世界图[16]。这种基于GPU的BFS算法将与最先进的应用于NVIDIATeslaK20cGPU的算法进行比较。2.新型GPU广度优先搜索算法我们提出了一种新的基于GPU的节点边境BFS算法，该算法工作效率，并且实现了时间复杂度为O(

9、E

10、+

11、V

12、)的渐