[论文简介] 在多核 CPU / GPU 上的高效并行的图搜索

摘要

图是一种基本的数据表示方式，在各个领域中得到了广泛的应用。在基于图的应用中，对图进行系统化的探索，如广度优先搜索（BFS）往往是处理其海量数据集的关键部分。

在本文中，作者提出了一种在多核 CPU 上实现并行 BFS 算法的新方法，该方法利用了现实世界中随机形状的图实例的一个基本属性。通过更有效地利用内存带宽，作者的方法显示出了比目前最先进的实现方法更高的性能，并随着图的大小增加而增加了其优势。

然后，作者提出了一种混合方法，对于 BFS 算法的每一级，我们从以下几种方法中动态地选择最佳实现：顺序执行、两种不同的多核执行方法和GPU 执行。这样的混合方法可以为每个图的大小提供最佳的性能，同时避免了在高直径图上的最差性能。最后，作者通过比较多个 CPU 和 GPU 系统，研究了底层架构对 BFS 性能的影响；一个高端 GPU 系统的表现与四插槽的高端 CPU 系统一样好。

介绍

新千年的第一个十年已经结束，在计算领域出现了许多新的有趣的前景。最突出的是，多核 CPU 已经变得很普遍，因为它们不仅被广泛应用于高性能计算，而且还被广泛应用于无处不在的消费类电子产品，如手持设备

将图形处理器用于通用计算的想法也开始流行起来，因为这种方法在应用于合适的问题时，能产生巨大的性能[1]。这种并行性（一个 CPU 或 GPU上的多个线程）和异构性（同时使用一个CPU和GPU）的扩散，已经成功地提高了许多传统的计算密集型工作负载的性能，但前提是它们的并行或异构实现必须得到很好的理解。

然而，仍有一些问题需要快速计算，但还没有找到有效的并行或异构实现。图形探索是这类问题的一个重要例子。图是一种基本的数据表示方式，被广泛应用于许多领域，如智能分析[2]、机器人[3]、社会网络分析[4]和计算生物学[5]。这些应用由于其海量的数据集规模，传统上需要长时间的处理时间。并行性通常无法缓解这些问题，因为这些应用的并行加速受到了内存访问模式的随机性的严重限制，而内存访问模式是图处理算法的一个基本属性[6]。

广度优先搜索（Broadth-first search，BFS）是一种系统地探索图中节点的基本图形算法。BFS 通常被认为是最重要的图算法之一，因为它可以作为许多其他算法的构件，包括去中心化计算[4]、连通分量识别[7]、群落结构检测[8]和最大流量计算[9]。 以图应用为目标的基准套件通常将 BFS 作为主要元素[10]，[11]。

由于这样的重要性，人们已经进行了大量的研究，以有效地实现并行BFS在各种计算系统中的应用[12]-[19]。有两个结果特别引起了作者的注意。一个是 Agarwal 等人的工作[18]，他们提出了一个最先进的多核系统的 BFS 实现。他们的实现利用了精心设计的数据结构来减少 CPU 套接字之间的缓存一致性流量。当在高端多核系统上执行时，他们的实现优于以前的提案，甚至包括其他架构的提案，如Cell[14]、集群[12]和共享内存超级计算机[13]、[16]。

另一个提案是 Hong 等人[19]提出的针对GPU的BFS实现，与 Agarwal 等人的论文报道时间差不多。Hong 等人解决了处理不规则图形时的工作负载不平衡问题，这对以前的 GPU 实现有破坏性的影响。与多核 CPU 实现相比，他们表现出了良好的性能提升。然而，他们的比较既没有包括 Agarwal的工作，也没有包括 Nehalem CPU 系列[20] 或 Fermi GPU[21]等较新的架构。

在本研究中，作者在前两部工作的基础上，将其整合到一个通用的解决方案中，在异构系统中同时利用 CPU 和 GPU。具体来说，作者首先提出了一种新的多核 CPU 的 BFS 实现，它比最先进的实现[18]对大图实例的性能更好，同时实现起来也更简单（第III-A节）。

其次，作者提出了一种混合方法，对于每一次BFS迭代，在顺序、并行或GPU 实现中动态选择最佳的执行方法。这种方法对大图和小图都有好处，同时也防止了最坏情况下的性能差（第III-B节）。最后，利用这两种系统的最佳实现cpu应用，作者测量了多核 CPU 系统和 GPU 系统上的 BFS 性能，并研究了它们的架构效果。

本文的具体贡献是。

多核 CPU 上的一种新方法

算法 1 层次同步并行 BFS

在实现层次同步并行BFS算法时，有一种基于算法 1 的直接实现，它使用有锁保护的共享队列来实现当前层次集(C)和下一层次集(N)。遗憾的是，这样一个简单的实现肯定会有很大的锁开销。

Agarwal 等人[18]提出了一个最先进的多核 CPU 的 BFS 实现，他们应用了以下一系列优化技术。

使用位图来紧凑地表示被访问的集合在原子化更新位图时，应用 "test and test-and-set" 操作使用局部下一层次队列；批量处理结点，插入到全局队列中维护每一个套接字的下一层次队列，这些队列实现是用票锁和快进式的

在这些优化方案中，前三者相对来说易于应用。图 1 显示了这样一个实现的伪代码。在该代码中，位图V（第3行）编码了访问过的节点集。由于该集是算法中访问频率最高的数据，因此使用位图数据结构可以最大限度地减小其大小，使缓存能够容纳最大的部分。通过使用内在的原子操作（如fetch_and_or）以及 teset 和 test-and-set 方法（第11-12行），位图的并行访问开销最小化。下一层次节点首先存储在每个线程的本地队列（LQ）中，直到它们被批量插入到全局队列中（第16、20行）。这些批量插入也可以使用单个原子操作有效地实现，方法是先增加队列索引(fetch_and_add)，然后对前一个索引进行正常的内存复制。这样做是可行的，因为在这一阶段，队列只被推入元素，但绝不会被任何线程弹出元素。作者将图 1 的该算法称为基于队列的 BFS 实现方法。

Argarwal 等人的最终优化是使用了一个精致的队列实现，尽可能地减少队列操作过程中不必要的相干流量。尽管这种优化提供了一些令人印象深刻的性能优势，但我们观察到，当输入数据集的大小变得非常大时，减少相干性遗漏的重要性就会大大降低，而性能主要受容量遗漏的影响。

因此，作者采取了不同的方法，将重点放在内存带宽的有效利用上。作者的方法是受以前的 GPU 的 BFS 实现的启发[15]，[19]，其中由于 GPU 的架构特性，作者有意避免了共享队列的使用。与共享队列不同，GPU 实现管理一个单一的 O(N) 数组，该数组会告诉一个节点是属于当前层次集、下一层次集还是已访问集。该数组在每个层次迭代时重复访问，利用 GPU 的巨大内存带宽。

从根本上说，作者的方法融合了以前的CPU[18]和GPU[19]方法的主要思想，并在此基础上进行了改进。新方法的伪代码如图2所示。与基于队列的方法一样，作者将访问的集保留为位图（第27行），并通过相同的原子更新（第38、39行）访问它。与基于队列的方法不同的是，下一层次集和当前层次集和GPU的实现方式一样，都是作为一个O(N)数组来实现的。

作为对方法的进一步论证，作者测量了各种机器上的顺序读和随机读带宽（这些机器的详细规格见 第四节表三）。表二显示了结果。最值得注意的是，数据显示多核 CPU 上的顺序读和随机读的带宽相差约9倍，进一步凸显了我们基于 Read 的方法更多的顺序读内存模式的重要性。

然而，作者提醒读者，即使是基于读取的方法也不能完全消除随机读取访问。该算法仍然需要从邻接列表到目的节点（图2中的第38行）的额外隐含，这是一种固有的随机操作。另外，注意到基于队列的方法和 Agarwal 等人的建议都是对位图进行同样的随机访问。然而，所有这些方法，包括作者的方法，都依赖于最后一级缓存来快速处理这种随机访问。

基于读取的方法的主要缺点是，它在每个层次迭代时都会读出整个级别数组，即使只有少数节点属于该级别。但是，这很少会影响到整体性能，因为现实世界的图实例有以下特点。

(1)图的直径很小，所以最大的重读量是有限制的；

(2)有几个关键层，其中的节点数为O(N)(见表I)，因此对这些层来说，按顺序读出整个O(N)数组并不浪费。

此外，总的算法执行时间已经被这些临界层的处理时间所支配。作者提醒读者，这种小世界属性并不仅仅是在某些图的实例中观察到的，而是随机形状的真实世界图的基本特征[22]。因此，虽然理论上，基于 Read 的方法可能在算法上是低效率的，但小世界属性保证了现实世界图中的现实执行很少接近最坏的情况。、

然而，当使用基于 Read 的方法进行最坏情况下的数据输入时，这个缺点会造成不理想的性能悬崖。两个具体的例子是(1)小(子)图和(2)长直径的图，如网格等。作者提出了一种 CPU 和 GPU 的混合方案来缓解这个问题。

（编辑：拼字网 - 核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!