基于神威·太湖之光的超大规模图计算系统“神图” 2019-12-16 14:10:29 作者：Fma

林恒博士拥有清华大学计算机科学博士学位（2018 年获得）和中山大学数学专业学士学位（2011 年获得），费马科技公司联合创始人。其研究兴趣包括异构体系结构、图计算和大规模计算。他基于神威·太湖之光开发的 Graph500 基准架构在 Graph500 异构架构排名（2016 年 6 月）中名列第一，在整体排名中名列第二。

以下为林恒博士在SC2018期间举办的 HPC Connection Workshop上，关于超大规模图计算系统神图的演讲摘要。林恒博士介绍了一个超大规模图计算框架——神图：它能够利用数百万个超级计算机内核，在半分钟内处理有多达 70 万亿条边的图数据。这也是入围 Gordon Bell 2018 决赛名单的六大作品之一。

以下是现场实录：

这是我在清华大学读博期间的工作，是与来自卡塔尔计算研究所、数学工程与先进计算国家重点实验室、苏黎世联邦理工学院、国家并行计算机工程与技术研究中心、北京搜狗科技发展公司和国家超算无锡中心的研究人员共同完成的。

我们看到图数据无处不在，人们现在越来越多地使用图计算。具体来讲，科技进步使我们能够处理更大的图。第一个例子是道路图，其中的道路是边，将作为顶点的城市连接起来。道路图上的计算执行的是一些熟悉的任务，比如导航、交通管理和城市规划。我们大家都熟悉另一种图，那就是社交网络图，我们可以在这些图上执行社区发现和民意分析等任务。网络图是另一种重要的图，我们每天使用搜索引擎时都会依靠它。

我们面临的一个常见问题是，图规模数据变得越来越大，我们现在看到的新图规模是以前根本无法处理的。例如，上面提到的图数据有数亿到数百万亿条边。此类规模问题超出了典型服务器和集群的计算能力，人们自然地想到了超级计算机！

以pagerank为例，介绍我们选择的图计算模型的背景。许多图计算任务都是迭代式的，会一直运行到状态收敛或达到一定的迭代次数之后。我们给出了执行一次pagerank迭代的伪代码。首先，每个活动的顶点基于其传出边而生成消息。然后，每个顶点沿它的边发送和接收消息，最终更新其状态，在这个例子中，也就是pagerank 值。

当有多于一个节点执行并行图处理时，通常会为每个节点分配图数据的一部分。因此，消息的生成需要与分类相结合，以将消息一起传送到相同节点。在并行处理中，我们会生成许多节点内消息，使大规模并行图处理在通信上遇到瓶颈。

让我们来看一个超大图数据的例子。这是搜狗搜索引擎提供的一个网络图，其中显示了中文网页和它们之间的链接。它有2730 亿个网页和 12 万亿个链接，占用了 137TB 硬盘空间。

处理这个具有空前规模的图数据会面临一些特定的新挑战。首先，它涉及海量的随机数据存取。其次，与传统HPC 相比，它具有更低的计算与内存存取比率。这个问题在大规模执行时更严重，导致了大量的随机点对点消息传递。最后，现实中的图数据是不规则的。它们常常具有幂律度分布，少部分顶点具有非常高的度数。这种情况随图规模变大而更加严重。这些是应用方面的大规模带来的挑战。

现在让我们看看系统方面的大规模带来的挑战。坦率地讲，超级计算机设计的初衷不是为了解决图计算问题。例如，我们的平台“神威·太湖之光”就一台典型的HPC机器，它连续两年在 TOP500 强中名列榜首，而这周滑落到第三名。它拥有 4 万多个节点，其异构架构采用了加速内核。它确实在处理超大图计算问题上具有优势，在计算、内存存取、网络通信方面都拥有卓越的聚合吞吐量。而另一方面，神威太湖之光也带来了巨大挑战，包括处理4 万个节点间的大量消息，将复杂的工作负载映射到其异构处理单元，以及在规则加速内核网格中调度不规则的数据流。在本次演讲中，我们将提出我们为解决这些具体挑战而开发的重要解决方案

我们能否扩展现有的图计算系统来处理超大规模图计算问题？简单的答案是不能。我们这里展示的系统根据使用单节点还是多节点，执行内存还是外存处理，映射到一个二维空间。

单机器、共享内存解决方案显然不能解决问题，原因是我们无法将一个大图放入单个节点的主内存中。内核外解决方案无论单节点还是多节点也不行，因为它们受限于I/O 吞吐量而处理速度太慢。因此，唯一可用的选择是基于内存的分布式处理方案。但是，目前的这类系统多不适合超大规模图数据或超级计算机环境，原因包括内存消耗、通信低效等。我们在一个对数标尺中描述这些系统的相对容量和性能，以x 轴表示图规模（边数），y 轴表示单次pagerank 迭代的处理时间。我们选择能处理具有至少 1万亿条边的图数据的系统，并描绘出它们的样本输入图大小和性能

我们的神图系统能在少几个数量级的时间内处理大几个数量级的图数据。具体来讲，它在半分钟内即可对一个 70 万亿条边的图数据完成一轮 pagerank迭代。据我们所知，神图完成了有史以来最大的图计算任务，也是第一个针对超大异构架构而设计的通用图计算框架。

现在我们讨论一下超大图计算处理带来的几个问题，以及我们如何解决它们。第一个是现实中的大图中存在严重的负载失衡。我们知道，这些图具有幂律度分布，而现有的合成图生成器低估了数据不均衡程度。例如，这张图中的 y 轴提供了与 x轴上的不同度数对应的顶点数。这是由Graph500 使用的官方合成图生成器 kronecker得到的分布。而这是我们通过搜狗看到的现实中的网络图的分布。不同于合成图，现实中的图在入度和出度上具有完全不同的分布，出度相对均衡，而入度严重扭曲。现实中的图的入度分布中具有更长的边缘数据：尽管平均入度为 45，但最大值达到了30 亿！这些扭曲导致了较小规模系统中不存在的问题。例如，单个计算节点远远无法满足最大的“超级顶点”需要的内存，它们需要在所有其他节点上迭代许多次。

根据这些观察，我们采用了度数感知的消息传播。更具体来讲，我们将所有顶点分为3 类：高入、高出和常规，对它们采取不同的处理方式。由于之前提到的非对称性，我们在入度和出度中采用不同的阈值。我们将高入或高出顶点复制到所有计算节点上。这些高度数顶点的本地镜像分别负责它们的边的一部分并以代理形式与对等节点通信。此解决方案具有多种优势。

首先，我们将高度数顶点和它们的工作负载分布到所有节点。这里的蓝色分布线显示了每个计算节点在执行高度数节点镜像前处理的边数，红色分布线为执行镜像后处理的边数。可以看到，我们不仅能将所有顶点放入内存中，边分布也变得更加均衡，最大的边分区大小缩小了44 倍；其次，借助组合了更新的高度数顶点本地镜像，我们显著减少了消息数量；最后，这种全局复制利用了在超级计算机上进行了高度优化的集合通信机制。对于常规顶点我们将它们随机分配给所有计算节点，这样可以得到不错的负载均衡。同时，他们也没有执行消息组合，因为这些常规顶点仅与很少的相邻顶点通信，所以没有必要占用额外的内存空间或计算来实现消息组合。

由于神图采用了 1D数据分区，每个节点将把消息发送到所有其他节点，以沿各边更新顶点。这种机制不太适合我们的目标规模。首先，40,000 个节点执行成对更新的效率低下。其次，在此规模上，计算节点的数量远远大于平均度数，意味着几乎没有机会组合消息。导致产生大量小消息。这是应用方面的挑战。从系统方面讲，最先进的超级计算机拥有分层网络互连结构。例如，在太湖之光中，在超节点外，每个节点的带宽会减少为1/4。这意味着超节点内的通信带宽高得多。

大量消息是超大图计算中最关键的问题之一。每个节点将与其他每个节点通信。随着规模变大，消息将变小。在40960个节点中，会产生40960 * 40960条小消息，这对网络来说是非常低效的。在实际中，我们也遇到了其他一些挑战，包括超节点网络上4:1 的聚合带宽裁剪，一些节点在运行前发生故障，导致网络拓扑结构存在缺陷。这是一个直接消息通信的例子，可以看到每条消息都非常小，整个网络中存在大量消息。在神图中，我们设计了一种超节点路由技术来解决此挑战。对于每条消息，在第一步，消息将发送到一个与目标节点具有相同超节点的转发节点。在第二步，消息将从转发节点发送到目标节点。每个节点同时是发送节点/转发节点/接收节点。通过采用这种技术，第一步中的消息可以组合，第二步中的消息也可以组合。因此，节点的消息可以从40960 条减少到（256 + 160 条）。第二步也在超节点内完成，充分利用了聚合带宽裁剪。尽管执行了两步，但没有给*网络带来开销。

我们使用超节点路由解决这些问题，这种方法将大量消息的传递过程协调为2 个阶段。让我们看看这个简单示例，其中3 个超节点上有 9 个计算节点。这里每个点表示一条消息，使用彩色编码来显示它需要更新的目标节点。

在第一阶段，每个源节点按目标超节点对它的传出消息进行分组，将组合后的消息发送到每个目标超节点中的一个转发节点。在第二阶段，每个节点处理传入它的消息，将这些消息转发给同一个超节点内的合适节点。请注意，所有节点都将充当源、目标和转发节点。通过此方法，我们显著减少了消息数量，尤其是跨超节点的消息，仅将更详细的消息传递给每个超节点内的更快网络。

具体来讲，在我们的目标系统中，有160 个超节点，每个超节点包含 256 个计算节点。如果我们使用直接更新方法，每个源节点将生成 256x160 条小消息，而我们的 2阶段超节点路由方法仅生成 256+160 条大消息。实现了更高的网络通信效率。

我们的2 阶段超节点路由方案的设计能够感知拓扑结构。但是，我们遇到的一个实际问题是，不是所有计算节点都会获得工作分配。甚至在机器全速运行时，分配中也可能存在少量遗漏，比如由于节点故障。理想情况下，执行超节点路由时，我们很容易使用每个超节点中的相应节点作为转发节点。假设我是第一个超节点中的第二个计算节点，那么每个超节点中的第二个节点将是我要通信的转发节点。只要遗漏少量计算节点，我们就无法真正做到这一点。为了实现平衡的转发负载，以及保留消息组合的优势，我们使用一个随机分配算法来调节转发负载划分的边界。在这个例子中，源超节点中有6 个计算节点，而目标中仅有 5 个。

我们将5 个转发节点的容量划分为 6 个虚拟节点，以与源超节点中的 6 个节点匹配。例如，第二个源节点将概率性地在目标节点 1 和 2之间分配其消息。这样，不但实现了负载均衡，还最大限度减少了每个源节点通信的转发节点数量。

最后一个问题是太湖之光的国产处理器的异构架构。让我们放大一个计算节点，其中有4 个内核组，每个内核组有一个 MPE 和 64 个CPE。MPE是通用单元，具有完整的控制流和 IO 容量，但内存带宽和计算能力较低。CPE是协处理器单元。尽管一个 CPE 的性能弱于 MPE，但 64核 CPE 集群提供了很高的硬件并行化水平和很高的聚合内存带宽。与此同时，CPE的功能有限，无法有效地处理通信。所以，我们需要谨慎执行任务映射和协调。我们的设计基于融合架构，这意味着MPE 和 CPE 拥有共享内存。

为此目的，神图将管道的每个模块根据其工作负载特征来映射到特定的 MPE或 CPE 集群。回想一下超节点路由方案，神图有一个额外的‘转发’模块，以及相应的接收和发送模块。在它们之中，模块‘生成并分类’、“转发”、“粗略分类”和“分类并更新”涉及大量内存存取且是内存带宽密集型的，所以我们将它们映射到CPE 集群。与此同时，发送和接收模块需要 MPI 通信，所以应该映射到 MPE。此外，我们将这些模块设计为均衡地占用所有 MPE 和CPE。在一个计算节点内，第一个内核组执行源节点功能，生成传出的消息并对其进行分类。第二个内核组执行转发功能，而第三和四组执行目标节点功能，接收并分类传入的消息，然后相应地更新顶点。

神图将分类作为其所有 CPE模块的主要计算任务来执行，根据消息目标对消息反复分桶。我们知道，CPE 具有很高的聚合内存带宽。例如，如果将分类任务分配给MPE，它的处理能力会受到内存带宽的限制，只能达到 1.09GB/s。我们设计了一种特定的片上分类机制，以在每个CPE 集群内实现高效的分类。但是，CPE缺乏高效的同步功能。所以如果我们通过原子指令实现简洁的并行分类来实现同步，只能获得 0.42Gb/s 的分类带宽，比单个 MPE 的性能低得多。相反，神图在CPE集群内执行了另一级别的异构映射，以利用它仅按行和按列的快速片上寄存器通信。它构建了一个分类网络，让第一组中的 16个内核从内存读取未排序的数据。第二组执行第二轮整理并传递给第三组的 16 个内核，后者将经过分类的数据传回内存。这个 2 轮整理过程不需要同步，可实现9.8Gb/s 的分类带宽。

此外，我们提出了其他许多技术来优化端到端的图处理性能，包括方向优化、快速图加载和随机顶点分区。请参阅我们的论文了解详细信息。所有这些技术为神图的实现提供了 22,000 行 C 代码。与此同时，作为一个通用的图计算框架，神图通过简单、标准的图计算框架 API 向用户隐藏了它的复杂性。例如，使用这些 API 实现 BFS 只需 30行代码。相比而言，太湖之光上以前的一个特定于Graph500 的BFS 实现拥有 40 多个文件和 9,000 多行代码。

接下来是实验部分。我们首先需要一个合适的指标。Graph500建议使用 TEPS（每秒遍历的边数）。但是，取决于具体实现，遍历的边数可能与实际访问的边数相差甚远。例如，一个使用规模为 38 的 Kronecker图优化的 BFS 可以遍历 44亿条边，但仅访问了约 2 亿条边，不到遍历边数的 5%。相反，我们提出了PEPS（每秒处理的边数），用于测量处理边的速度，与解决问题所需的工作量直接对应。

我们实现了这5 个图算法，并对合成图和现实图进行了测试。对于 Kcore，我们实现了算法，但发现它由于频繁的障碍而导致太慢，因此我们对Kcore跳过了最大规模的测试。

首先，我们展示弱扩展结果，随着我们增加图规模，我们会使用更多计算节点，在整个系统上达到40的规模。由于节点可用性，我们最大规模的运行使用了38,656 个节点，但神图可以扩展到整个系统的 40,960 个节点。我们从规模35 的 1248 个节点上开始扩展，所以 x 轴显示了系统规模，y轴显示了聚合 GPEPS。如图所示，BFS、WCC和PageRank 三个程序都实现了非常好的弱扩展性。

对于强扩展，我们采用相同的x 和 y 轴定义，图规模固定为 36。我们可以看到，由于网络同步和传输开销增加，规模缓慢降低到5000 个节点以下。

此表总结了我们使用的现实图和合成图的特征，以及运行我们实现的5 个图算法的聚合 GPEPS 性能。我们突出显示了两次最大规模的测试：具有12 万亿条边的搜狗网络图和具有 70 万亿条边的 Kronecker 图。这两个图的 GPEPS之间的最大区别在于，现实网络图包含长尾，导致其迭代次数显著增加，图的很大部分在大量处理过程中都处于不活动状态。总体来讲，神图的性能非常好。例如，我们测量的性能为 8328 GTEPS，约为所报告的特定于 Graph500 的 BFS 实现的结果的 1/3。但是请注意，神图是一种通用的图计算框架，没有特定于算法的优化，而且用户仅使用 30 行代码就达到了该性能的 1/3。

最后，让我们看看现实图的问题。我们在这里计算TrustRank（PageRank 的一种变形），搜狗搜索引擎实际使用它来检测欺诈网页，使用一个额外的可信网页白名单作为种子输入。此图显示了结果。页面根据PageRank 或 TrustRank 值按降序排序，并分组到 20 个页面桶中。蓝条表示 PageRank 结果，橙条表示 TrustRank 结果。x轴表示桶 id，桶 id 越大的桶具有越低的 PageRank 或 TrustRank 值。y 轴表示每组中的劣质页面比例，由搜狗工程师手动标记。从该图中可以看到，在中部的桶中，PageRank拥有的劣质页面比 TrustRank 多得多，因此垃圾页面也更多。PageRank本身单独根据图结构来计算结果，而不会合并任何外部知识。这使垃圾页面很容易欺骗 PageRank 来操纵 PageRank 值。TrustRank采用专家挑选的一组信誉良好的种子页面，排除了中部桶中的垃圾页面，提高了更高 id 的桶中的垃圾页面集中度。


总结一下，我们开发了通用图计算框架神图。通过端到端的优化解决了超大图数据与机器相结合所带来的独特挑战，它设法利用了太湖之光超级计算机上接近 40,000个异构内核，在现实图和合成图上实现了令人印象深刻的性能和扩展能力。最后，它将所有复杂的优化隐藏到标准图计算 API背后，只需几十行代码即可实现常见的图算法。