ACM通信

研究突出了

加速GPU之间的中心性

作者:亚当·麦克劳克林，大卫·a·巴德
ACM通信，2018年8月，第61卷第8期，85-92页
10.1145 / 3230485
评论

模拟社交网络、数值模拟和互联网结构的图表非常庞大，无法人工检查。用来分析这些网络的一个流行的度量是介间中心性(BC)，它在社区检测、电网事故分析和人脑研究中都有应用。然而，这些分析带来了很高的计算成本，阻碍了对感兴趣的大型图的检查。

最近，图形处理单元(gpu)的使用在非结构化数据集的高效处理方面有很大的前景。BC之前的GPU实现受到大型本地数据结构和低效图遍历的影响，这限制了可伸缩性和性能。在这里，我们提出了一个混合GPU实现，它在任意结构的图上提供了良好的性能，而不是像以前那样只在无标度图上提供性能。与现有最好的GPU算法相比，我们的方法在大直径图形上实现了高达13倍的加速，总体平均加速2.71倍。当在192 gpu上运行BC时，我们还观察到接近线性的加速。

回到顶部

1.简介

网络分析是各种领域的基本工具，比如编译器，¹⁷社交网络,¹⁴和计算生物学。⁵这些分析在现实世界中的应用涉及到无法人工检查的巨大网络。在最近的文献中，图分析的一个例子是BC。中介中心性被用来寻找城市中商店的最佳位置，^20.研究艾滋病在性网络中的传播，¹³电网事故分析，¹¹和社区检测。²³这种分析方法所应用的各种领域和应用表明，图分析需要算法技术，使其性能可移植到尽可能多的网络结构。不幸的是，已知最快的计算BC分数的算法O（锰的非加权图的复杂性n顶点,米边，使分析大型图形具有挑战性。因此，需要健壮、高性能的图分析，可以应用于各种各样的网络结构和规模。

图形处理单元(gpu)为规则的、密集的、需要计算的子程序(如矩阵乘法)提供了出色的性能。然而，最近在gpu上加速不规则、内存限制的图形算法也取得了成功。^6，17，19之前在GPU上的中介中心性的实现优于CPU，特别是在无标度网络上;然而，它们对更大的图实例的可伸缩性受到限制，使用渐近低效的算法来降低在大直径图上的性能，而且不够通用，无法应用到可以利用它们的结果的各种领域。

本文通过以下贡献来缓解这些问题:

• 我们在GPU上提供了一种高效的介数中心性算法，尤其适用于具有大直径的网络。
• 为了通用性，我们提出了一种算法，它可以在利用GPU的内存带宽和基于被处理图的结构的工作的渐近效率之间进行选择。我们提出了一种在线方法，使用算法中的少量初始工作来建议哪种并行方法最适合处理剩余的工作。
• 我们在单个GPU系统上实现了我们的方法，在各种各样的真实图形和合成图形上，显示了比之前最好的GPU实现的平均速度提高了2.71×。此外，我们的实现在192个gpu的集群上实现了近乎线性的加速。

回到顶部

2.背景

2.1.定义

让一个图G= (V E)由一组组成V的n= |V|个顶点和一个集合E的米= |E|边缘。从顶点出发的路径u一个顶点v是否有边序列起源于u和终止v。这样的路径是最短路径如果它的序列包含最小数量的边。广度优先搜索(BFS)通过开始一个“源”(或“根”)顶点并搜索它的邻居来探索图的顶点。然后查找这些顶点的邻居，这个过程重复进行，直到没有剩余的顶点要查找为止。每一组被检查的邻居被称为顶点前沿从顶点边界出发的边集合被称为edge-frontier。的直径是任意一对顶点之间的最长最短路径的长度。一个无标度图有一个服从幂律的度分布，即少量顶点有大量的出边，大量顶点有少量的出边。²最后,一个小世界图的直径与图中顶点数的对数成正比。²⁵在这些网络中，每一个顶点都可以通过通过少量的边从其他顶点到达。

稀疏图在内存中的表示。在内存中存储图形最直观的方法是作为邻接矩阵。对于未加权图，元素一个_ij如果有一条边存在，则等于1我来j否则等于0。然而，我们在本文中研究的真实世界的图表却是如此稀疏的，这意味着在这些数据集的邻接矩阵表示中，绝大多数元素都是零。而不是使用O（n²)空间来存储整个邻接矩阵，我们使用压缩稀疏的行(CSR)格式，如图1．这种表示由两个数组组成:行补偿(R)和列索引(C)列索引数组是每个顶点的邻接表连接到的数组米元素。数组中的行偏移量n+ 1元素数组，指向每个顶点的邻接表所在的位置，并在列下标数组中结束。例如，顶点的邻接表u起价C (R (u))结束C (R (u + 1)−1)(在内地)。

图1。一个小图的中间性、中心性分数和CSR表示示例。

2.2.Brandes的算法

中介中心性最初是在社会科学中发展起来的，用来对那些在网络中处于中心地位的人进行分类，这些人可能通过隐瞒或改变信息来影响他人。⁸度量试图通过测量通过特定顶点的最短路径与所有顶点对之间最短路径总数的比值来区分网络中最具影响力的顶点。直观地说，这个比率决定了一个顶点连接网络中其他顶点对的良好程度。形式上，顶点的介心性v被定义为:

在σ_圣顶点之间最短路径的个数是多少年代而且t和σ_圣（v)是经过的最短路径的个数v。

考虑图1．顶点3是唯一位于从左(顶点4到8)到右(顶点0到2)的路径上的顶点。因此，顶点3位于这些顶点对之间的所有最短路径上，具有很高的BC分。相反，顶点8不属于图中任何剩余顶点对之间的路径，因此BC值为0。注意，分数反映在图1处理从顶点开始的路径u到顶点v相当于从顶点开始的路径v到顶点u因为这些路径是无方向的。换句话说，为了避免重复计算(无向)最短路径的数量，我们将分数除以2。

BC值的大小也随网络的大小而变化。为了公平地比较两个不同图的顶点之间的BC值，一种常用的技术是用BC值的最大可能值规范化BC值⁴:(n−1)(n−2).这种比较对于比较随时间变化的网络的离散切片是有用的。¹⁵

的实现解决了全对最短路径问题O（n^3.)的Floyd-Warshall算法，并用路径计数对结果进行增强。Brandes在此基础上改进了一种算法O（锰)的时间。^3.Brandes方法的关键概念是依赖的一个顶点v对于一个给定的源顶点年代：

顶点的依赖关系和后继顶点的依赖关系之间的递归关系允许对中心性度量进行更渐近高效的计算。Brandes的算法将中间度中心性计算分为两个主要步骤:

1. 求每对顶点之间最短路径的个数。
2. 对每个顶点的依赖关系求和。

我们可以根据依赖关系重新定义BC分数的计算如下:

2.3.GPU架构和编程模型

与传统cpu相比，GPU具有较高的内存带宽，因此产生了许多高性能的GPU图形算法。^15，17，19与cpu相比，gpu倾向于依赖延迟隐藏，而不是缓存和利用单指令,多头螺纹(SIMT)编程模型。SIMT模型允许将晶体管分配给附加的处理器核心，而不是用于控制流管理的结构。

图形处理器是由一系列流多处理器(SMs)，每个线程管理数百个线程。每个SM中的线程以32个线程(在当前的NVIDIA架构上)为一组执行，称为扭曲。尽管每个经线内线程的执行路径可能不同，但当一个经线内的所有线程执行相同的指令时，性能会达到峰值。一个特定的SM的扭曲之间的同步是不昂贵的，但正确地同步GPU的所有SMs需要启动一个单独的内核，或在设备上执行的函数。GPU线程可以访问很多寄存器(通常是255个左右)，程序员管理的寄存器很少(通常是48KB)共享内存每个SM都是独一无二的，还有一个更大的全局内存所有短信都可以访问。

回到顶部

3.之前GPU实现

Brandes算法的两个著名的GPU实现在过去几年中已经发布。贾庆林et al。¹⁰比较两种类型的细粒度并行，显示一种比另一种更好，因为它在GPU上展示了更好的内存带宽。施、张出席GPU-FAN²²通过使用不同的线程分配到工作单元，报告了比Jia等人稍微加快的速度。这两种方法都将优化重点放在无标度网络上。

3.1.顶点和边的平行度

Jia等人讨论了线程到图形实体的两种分布:vertex-parallel而且edge-parallel。¹⁰顶点并行方法将一个线程分配到图的每个顶点，该线程遍历从该顶点出发的所有出线边。相反，边并行方法为图的每条边分配一个线程，并且该线程只遍历该条边。在实践中，图中的顶点和边的数量往往大于可用线程的数量，因此每个线程依次处理多个顶点或边。

对于最短路径计算和依赖累积阶段，顶点并行方法在每个线程中遍历的边数取决于分配给每个线程的顶点的出度。顶点之间的出度差异会导致线程之间的负载不平衡。对于无标度网络，这种负载不平衡可能是一个巨大的问题，因为超出度的分布遵循幂律，少量顶点将有大量的边要遍历。²边并行方法通过直接将边分配给线程来解决这个问题。Jia等人的顶点平行和边缘平行方法都使用了一种低效的O（n²+米)图遍历，检查正在处理的每个顶点是否属于当前搜索深度。

图2说明了用于顶点并行和边缘并行方法的线程分布。如图所示图1，考虑从顶点4开始的广度优先搜索。在搜索的第二次迭代中，顶点1、3、5和6位于顶点边界中，因此需要检查它们的边缘。顶点平行法，如图所示图2，将一个线程分配到图的每个顶点，即使连接图中大多数顶点的边不需要遍历，也会导致浪费工作。还要注意，每个线程负责遍历不同数量的边(由每个顶点下面的小方格表示)，这会导致工作负载失衡。边缘平行法，如图中所示图2，不会有负载不平衡的问题，因为每个线程都有一条边要遍历。然而，这种线程的分配也会导致浪费的工作，因为在这个特定的迭代中不需要检查不是来自边界顶点的边(但在迭代过程中会不必要地检查)每一个迭代)。最后，下面的部分图2显示了一个高效的遍历迭代，其中边界中的每个顶点都分配了一个线程。在这种情况下，尽管线程之间可能存在负载不平衡，但只执行有用的工作。

图2。线程分配到工作单元的说明。上图:Vertex-parallel。中间:Edge-parallel。底部:工作效率。

3.2.GPU-FAN

的GPU-FAN该包被设计用于分析代表蛋白质通信或基因相互作用的生物网络。²²与Jia等人的实现类似，GPU-FAN使用边缘并行方法跨线程进行负载平衡。然而，GPU-FAN包只关注细粒度的并行性，每次使用来自所有线程块的所有线程并行遍历BC计算的一个源顶点的边缘。相比之下，Jia等人的实现使用块中的线程并行遍历边缘，而独立的线程块每个都关注BC计算的独立根。

回到顶部

4.方法

4.1.工作效率的方法

注意到上一节中提到的问题，我们现在介绍在GPU上高效实现中介中心性的基础。除了我们自己的新技术外，我们的方法还利用了文献中的优化。我们的方法与之前的工作之间最重要的区别是，我们使用显式队列进行图遍历。由于图的级别是并行处理的，我们使用两个队列来区分当前搜索级别中的顶点(问_咕咕叫)从将在下一级搜索中处理的顶点(问_下一个)．对于依赖项积累阶段，我们进行初始化年代和它的长度。在本例中，我们需要跟踪搜索的所有级别的顶点，因此我们只使用一个数据结构来存储这些顶点。区分…的各部分年代对应于我们使用的每一层搜索结束数组,结束_len= 1 +马克斯_v∈｛d［v]}在遍历的末尾。顶点对应于深度我的遍历都是从索引定位的结束［我)指数结束［我+ 1] - 1(含)的年代。的用法结束而且年代数组类似于用于以CSR格式存储图的数组。

算法1:高效工间、中心性最短路径计算。

高效的最短路径计算阶段如算法1所示。队列问_咕咕叫初始化为只包含源顶点。while循环的迭代对应于图的深度遍历。第3行中的并行for循环将一个线程分配给队列中的每个元素，这样就不会不必要地遍历图中其他部分的边。第5行上的原子比较和交换(CAS)操作用于防止同一顶点的多次插入问_下一个．这种限制允许我们安全地进行分配O（n)内存问_下一个而不是O（米)在允许重复的队列条目的情况下。因为每个元素只需要一个线程问_咕咕叫这种原子操作不会对图中的每个顶点或边使用一个线程，而是会遇到有限的争用，因此不会显著降低性能。

第11行上的条件检查包含下一个深度搜索顶点的队列是否为空;如果是，那么搜索就完成了，因此我们从最外层的while循环中断。否则，我们从问_下一个,问_咕咕叫，将这些顶点添加到的末尾年代，并进行适当的簿记以设置这些数组的长度。

算法2展示了一种高效工作的依赖性积累。我们可以通过检查来消除原子的使用继任者而不是每个顶点的前身。与其让当前正在并行处理的多个顶点原子地更新它们共同祖先的依赖关系，祖先可以基于其后辈更新自己，而不需要原子操作。¹⁴

算法2:工作效率、中介性、中心性依赖积累。

注意，算法2的第3行并行for循环只将线程分配给需要累积依赖值的顶点;这是做簿记的地方，以跟踪图遍历的不同级别结束阵列实现了。而不是naïvely分配一个线程到每个顶点或边，并检查是否顶点或边属于当前深度，我们可以立即提取该深度的顶点，因为它们是一个连续的块内的条目年代。此策略再次防止了以前的实现所造成的不必要的分支开销和对全局内存的访问。有关进一步的实现细节，请读者参阅相关的会议文件。¹⁶

4.2.混合方法的基本原理

上一节中概述的这种方法的主要缺点是线程之间可能存在严重的负载不平衡。尽管我们的方法有效地将线程分配给有用的工作单元，但线程的边分布完全依赖于图的结构。在直径较大的图上，我们的方法明显比其他方法快，因为这样的图往往有更均匀的出度分布。然而，在无标度图或小世界图上，上一节中概述的算法并不能提高性能。基于这一结果，我们提出了一种基于图的结构在边缘并行和高效工作方法之间进行选择的混合方法。我们不是对图进行预处理，试图确定它是否可以被分类为无标度图或小世界图，而是将杂交作为在线方法实现。

图3说明了我们决定使用混合算法背后的基本原理。每个子图显示了图中三个随机选择的源顶点的顶点边界是如何演化的。请注意，子图的轴在不同的尺度上，以适当地显示前沿的趋势。尽管源顶点的位置在顶点边界如何随着搜索迭代变化的精确过程中起着重要作用，但我们可以看到，在搜索的迭代过程中，顶点边界的一般大小和大小的变化更多地依赖于图的整体结构。对于大直径图，例如rgg_n_2_20而且delaunay_n20（图3一而且3 b)，顶点边界逐渐增长，始终是图中顶点总数的一小部分。对于直径较小的图，如kron_g500-logn20（图3 c)，顶点边界在经过几次迭代后就会变大，并且在顶点处包含了图中顶点总数的一半以上。

图3。图的不同分类的顶点前沿的演化(占总顶点的百分比)。

直观地说，对于大型顶点前沿，边并行方法是有利的，因为它的内存吞吐量，而对于小型顶点前沿，高效工作的方法是有利的，因为将被遍历的边的数量明显小于图中总边的数量。

4.3.抽样

中间性中心性的精确计算为图中的每个顶点计算一个BFS。因为所有这些搜索都是独立的，所以它们可以并行执行。对于大多数顶点都属于一个大型连接组件的图，处理每个源顶点的时间量大致相等，因为每个源顶点需要遍历相同数量的边。因此处理所需的时间k源顶点大概是k乘以处理一个源顶点所需的时间。²¹

算法3:并行化策略选择的抽样方法。

使用上述分析，可以通过处理图顶点的一小部分来估计图中连接组件的平均大小(因此是首选的并行性方法)。算法3展示了该方法是如何实现的。我们最初使用高效工作的方法来处理源顶点的一小部分，记录它们每个BFS遍历的最大深度。然后我们使用这个集合的中值作为我们对图直径的估计。如果该中值小于阈值(由参数确定γ)，那么我们的图很可能是一个小世界或无标度图，我们应该切换到使用边并行方法。

回到顶部

5.结果

5.1.实验装置

单节点GPU实验使用CUDA (computing Unified Device Architecture) 6.0 Toolkit进行。CPU是英特尔酷睿i7-2600K处理器，运行频率3.4 GHz, 8MB缓存和16GB DRAM。GPU是一个GeForce GTX Titan，有14条短信和837 MHz的基本时钟。Titan有6GB的GDDR5内存，是CUDA计算能力3.5(“开普勒”)GPU。

在Keeneland初始投放系统(KIDS)上进行了多节点实验。²⁴KIDS每个节点有2个运行2.8 GHz的Intel Xeon X5660 cpu和3个特斯拉M2090 gpu。各节点之间采用ib QDR (Infiniband four ple Data Rate)网络连接。特斯拉M2090有16个短信，时钟频率1.3 GHz, 6GB的GDDR5内存，是CUDA计算能力2.0(“费米”)GPU。

我们将我们的技术与GPU-FAN进行比较²²贾等人。¹⁰如果可能，使用他们已经在线提供的实现。用于这些比较的图表显示在表1．这些图表来自第十届DIMACS挑战赛，¹佛罗里达大学稀疏矩阵集合，⁷以及斯坦福网络分析平台(SNAP)。¹²这些基准测试包含现实世界和随机生成的图实例，这些图实例对应于各种各样的实际应用程序和网络结构。我们将注意力集中在BC的精确计算上，注意到我们的技术可以简单地调整为近似。

表1。本研究使用的图形数据集。

5.2.扩展

首先，我们比较了我们的算法在三种不同类型的图上随图大小变化的效果。由于Jia等人的实现无法读取包含孤立顶点的图，因此我们无法使用该参考实现获得随机几何(rgg)和简单克罗内克(克隆亚麻)图。此外，由于较高的尺度会导致GPU-FAN耗尽内存，我们只需从较低的尺度(用虚线表示)的结果中推断出预期的结果。注意，从一个比例到下一个比例，顶点的数量和边的数量都是双倍的。

注意到坐标轴上的对数-对数刻度，我们可以看到图4一抽样方法在所有尺度上的性能都优于GPU-FAN算法12倍以上rgg。有趣的是，当抽样方法处理四倍于GPU-FAN的图时，抽样方法只比GPU-FAN多花一点时间。为德劳内网格图如图所示图4 b我们可以看到边缘并行方法和采样方法在所有尺度上都优于GPU-FAN。对于包含少于10,000个顶点的图，边并行方法甚至优于采样方法;然而，应该注意的是，这些时间上的差异是微不足道的，因为它们在毫秒量级上。随着图的规模增加，采样方法明显成为主导，它所达到的速度随着图的规模增长而增长。最后，我们将采样方法与GPU-FAN进行了比较克隆亚麻在图4 c．尽管GPU-FAN在最小尺度图上的速度略快于抽样方法，但我们可以看到抽样方法在下一个尺度上是最好的，趋势显示了抽样方法的最佳数量随着尺度的增长而增长。此外，之前的两种实现都不能在更大的范围内支持这种类型的图，而抽样方法可以支持更大的范围。

图4。根据问题大小对三种不同类型的图进行缩放。

5.3.基准

图5提供了本文中讨论的各种并行化方法与Jia等人的边缘并行方法的比较。¹⁰至于道路网及网(af_shell、del20 luxem)，所有方法的性能都比边缘并行法高出约10倍。边缘并行方法对这些图执行了大量不必要的工作。对于剩下的图(无标度图和小世界图)，单独使用工作效率方法比边并行方法执行得慢，而抽样方法相同或略好。在这些情况下，我们看到了选择在线并行化方法的优势。

图5。工作效率和抽样方法的比较。

在最极端的情况下，边缘并行方法需要两天半以上的时间来处理af_shell9而抽样方法将此时间缩短到5小时以下。类似地，边缘并行方法需要超过48分钟来处理luxem-bourg.osm而采样方法仅需要6分钟。总体而言，采样方法的平均执行速度比边缘平行方法快2.71倍。

5.4.Multi-GPU实验

尽管我们的方法同时利用了粗粒度和细粒度的并行性，但可用的并行性仍然比单个GPU所能处理的要多。我们的方法很容易扩展到多个gpu和多个节点。我们通过将根的子集分布到每个GPU来扩展算法。因为每个根都可以独立并行处理，如果每个GPU都有足够(且均匀分布)的工作量，我们应该期待接近完美的伸缩。

由于每个根的本地数据结构是独立的(因此只需要驻留在一个GPU上)，我们在所有GPU上复制代表图形本身的数据，以消除通信瓶颈。一旦每个GPU都有自己的BC分数本地副本，这些本地副本就会为每个节点上的所有GPU积累起来。最后，通过一个简单的调用将节点级别的分数简化为全局BC分数MPI_Reduce()。图6展示了我们的算法扩展到多个gpu的效果德劳内,rgg,克隆亚麻图表。它表明，如果问题规模足够大(例如，如果每个GPU都有足够的工作)，线性加速是很容易实现的。对于更密集的网络结构，线性加速可以在更小的图尺度上实现。例如，对于规模为16的单个节点，使用64个节点提供了大约35倍的加速德劳内图，而使用相同数量的节点在相同的尺度rgg而且克隆亚麻图分别提供了超过40×和50×的加速。所见的缩放行为图6不是这些图所独有的，因为算法提供了大量的粗粒度并行性。对于足够大的图，这种可伸缩性可以独立于网络结构而获得。

图6。针对不同的图形结构，通过节点数量实现多gpu伸缩。每个节点包含3个图形处理器。

回到顶部

6.结论

在这篇文章中，我们讨论了在GPU上计算中介中心性的各种方法。利用关于图结构的信息，我们提出了几种在两种并行方法之间进行选择的方法:边并行和工作效率。对于大直径图，使用渐近最优算法对于获得良好的性能是至关重要的，而对于小直径图，最好是最大化内存吞吐量，即使完成了不必要的工作。此外，我们的方法比现有的实现更具可扩展性和通用性。最后，我们在一个包含192个gpu的集群上运行我们的算法，结果显示，无论网络结构如何，加速几乎与gpu的数量成线性关系。总的来说，我们的单GPU方法比之前最好的GPU方法平均快2.71倍。

对于未来的工作，我们希望有效地将额外的图分析映射到并行架构。对于实现更复杂的并行算法来说，健壮、高性能原语的重要性再怎么强调也不为过。理想情况下，GPU内核应该是模块化和可重用的;幸运的是，像推力这样的包⁹和幼崽(CUDA Unbound)¹⁸正开始弥合这一差距。在一个软件环境中，用户可以访问GPU上的高性能图形分析套件，这将允许快速的网络分析，并作为更复杂程序的构建块。

回到顶部

致谢

本文描述的工作部分由美国国防高级研究计划局(DARPA)根据#HR0011-13-2-0001协议赞助。本文件所提供的内容、观点和结论并不一定反映DARPA或美国政府的立场或政策，不应推断其官方认可。发行声明A:“批准公开发行;分布是无限的。”这项工作也得到了NSF拨款ACI-1339745 (XScala)的部分赞助。这项研究使用了乔治亚理工学院Keeneland计算设施的资源，该设施由美国国家科学基金会根据合同OCI-0910735支持。特别感谢Jeff Young对在KIDS上进行实验的帮助。最后，我们还要感谢NVIDIA公司捐赠的GeForce GTX Titan GPU。

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2018 ACM, Inc.

---

没有发现记录