面向后E级图计算的方法、系统、存储介质及电子设备

摘要

本发明涉及面向后E级图计算方法、系统、存储介质及电子设备，方法包括：在构建核心子图的情况下，至少一个计算节点选取核心子图中包含活跃图顶点的图划分块且基于拓扑结构感知的图处理机制对图划分块进行异步图计算处理，基于树型的方式设置计算节点，基于社区结构感知的划分方式将图数据分区并分配至各个计算节点；在各个计算节点及其管辖的下层计算节点的图数据均收敛后，计算节点与其自身所属的上层计算节点、同层次计算节点进行通信以实现同级之间的图顶点状态的同步；逐层次通信直至整个集群负责的图顶点状态收敛。本发明解决了大规模分布式环境下计算性能低、拓展性差、通信开销高等问题，提升超级计算机在支持大规模图计算时的性能。

权利要求

1.一种面向后E级图计算的方法，其特征在于，所述方法至少包括：分布式异步图处理和建立层次化超大规模分布式通信；

所述分布式异步图处理的步骤至少包括：

在构建核心子图的情况下，至少一个计算节点选取所述核心子图中包含活跃图顶点的图划分块且基于拓扑结构感知的图处理机制对所述图划分块进行异步图计算处理，所述建立层次化超大规模分布式通信的步骤至少包括：基于树型的方式设置多个计算节点，基于社区结构感知的划分方式将图数据分区并分配至各个计算节点；

在各个计算节点及其管辖的下层计算节点的图数据均收敛后，所述计算节点与其自身所属的上层计算节点、同层次计算节点进行通信以实现同级之间的图顶点状态的同步；

逐层次通信直至整个集群负责的图顶点状态收敛。

2.根据权利要求1所述的面向后E级图计算的方法，其特征在于，所述方法还包括：在进行分布式异步图处理之前，各个计算节点将本地图分区划分为细粒度的块，并且根据块中图顶点度数来区分高度数块和低度数块，选取所述高度数块来构建核心子图；

其中，

在构建核心子图的过程中，识别核心图顶点，并且将核心图顶点的状态数据合并存储。

3.根据权利要求1或2所述的面向后E级图计算的方法，其特征在于，所述至少一个计算节点选取所述核心子图中包含活跃图顶点的图划分块且基于拓扑结构感知的图处理机制对所述图划分块进行异步图计算处理的步骤至少包括：至少一个计算节点选取所述核心子图中包含活跃图顶点的高度数块，基于拓扑结构感知的图处理机制，将所述高度数块中的图数据按照图拓扑顺序调度到各核上并行处理。

4.根据权利要求3所述的面向后E级图计算的方法，其特征在于，所述至少一个计算节点选取所述核心子图中包含活跃图顶点的图划分块且基于拓扑结构感知的图处理机制对所述图划分块进行异步图计算处理的步骤还包括：在高度数块的处理过程中，将图顶点状态的更新数据按照图顶点ID顺序进行排序，再将排序后的所述图顶点状态更新数据按照排好的顺序应用到相应图顶点来更新其图顶点状态值，以将图顶点状态更新数据的随机访问转化为规则地有序访问。

5.根据权利要求4所述的面向后E级图计算的方法，其特征在于，所述至少一个计算节点选取所述核心子图中包含活跃图顶点的图划分块且基于拓扑结构感知的图处理机制对所述图划分块进行异步图计算处理的步骤还包括：在所述计算节点的图数据被计算至局部收敛后且没有达到需要通信的条件的情况下，所述计算节点生成需要通信状态值的图顶点与不直接相邻的至少一个图顶点之间的状态值依赖关系，所述计算节点基于所述状态值依赖关系在通信后更新图顶点状态值，使得图顶点的更新进行传递。

6.根据权利要求1所述的面向后E级图计算的方法，其特征在于，所述基于树型的方式设置计算节点，基于社区结构感知的划分方式将图数据分区并分配至各个计算节点的步骤至少包括：将若干计算节点按照树型的方式设置，

将图数据按照社区结构感知的划分方式划分并形成图分区，根据状态值依赖关系将图顶点之间的依赖紧密的核心子图分配至同一组计算节点中，使得所述核心子图内的频繁通信发生在同一计算节点分组内部。

7.根据权利要求6所述的面向后E级图计算的方法，其特征在于，所述基于树型的方式设置计算节点，基于社区结构感知的划分方式将图数据分区并分配至各个计算节点的步骤还包括：在若干计算节点进行通信时，发送至同一图顶点的通信信息基于规约合并的方式来减少通信量；和/或向同一计算节点的若干通信信息是以合并的方式统一发送至所述计算节点的。

8.一种面向后E级图计算的系统，至少包括处理器，其特征在于，所述处理器至少包括：第一模块，用于分布式异步图处理；

第二模块，用于建立层次化超大规模分布式通信：

第一模块被配置为：

在构建核心子图的情况下，至少一个计算节点选取所述核心子图中包含活跃图顶点的图划分块且基于拓扑结构感知的图处理机制对所述图划分块进行异步图计算处理，第二模块被配置为：基于树型的方式设置多个计算节点，基于社区结构感知的划分方式将图数据分区并分配至各个计算节点；

在各个计算节点及其管辖的下层计算节点的图数据均收敛后，所述计算节点与其自身所属的上层计算节点、同层次计算节点进行通信以实现同级之间的图顶点状态的同步；

逐层次通信直至整个集群负责的图顶点状态收敛。

9.一种存储设备，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现权利要求1至7中任一项所述的面向后E级图计算方法的步骤。

10.一种电子设备，其特征在于，包括：

存储器，其上存储有计算机程序；

处理器，用于执行所述存储器中的所述计算机程序，以实现权利要求1至7中任一项所述的面向后E级图计算方法的步骤。

说明书

面向后E级图计算的方法、系统、存储介质及电子设备

技术领域

[0001] 本发明涉及图计算技术领域，尤其涉及一种面向后E级图计算的方法、系统、存储介质及电子设备。

背景技术

[0002] 由于图能够很好地描述大数据时代事物之间的关联关系，在结构和语义上有很强的表达能力。为此，大量大数据分析应用均利用迭代图处理技术来挖掘各自需要的数据信息。例如，通过单源点最短路径算法来找出事物间的最短路径；通过连通分量算法找出数据中的社区关系。与此同时，随着数据的爆发式增长，图数据的规模越来越大，对计算能力的需求也越来越强烈。例如AI芯片电路图的图顶点规模已达万亿级别。在对大规模图数据的科学计算中，往往需要利用超级计算机来快速高效地获得分析结果。

[0003] 然而，图计算和传统的科学计算有着极大不同，它会更明显地表现出数据依赖复杂，负载不均衡，数据局部性差，不规则数据访问等问题，这使得传统超级计算机的大数据处理系统在支持大规模图计算时面临着极大的挑战。具体而言，首先，现有面向超级计算机的图计算系统在运行时缺乏对图顶点状态间复杂依赖的充分感知，在并行执行时以图顶点或者边为基本处理单位，各图顶点难以将其最新状态快速有效地传递给其邻居，导致大量无效图顶点状态更新、计算效率低下(不但收敛速度慢而且底层硬件资源消耗大，例如数据的冗余加载导致内存带宽等资源的消耗)，使得有限的硬件资源成为大规模图计算执行的性能瓶颈，最终导致系统性能低下。其次，在图计算过程中，数据间复杂且不规则的依赖导致大量不规则的数据访问以及极差的数据局部性(比如传统CPU架构每次访问64字节的数据，其中只有4或者8字节的数据是有效的)，造成存储资源和内存带宽的有效利用率低。同时，现有方案在计算时，所有图顶点之间状态传递需要沿着它们之间的依赖关系链串行进行，这使得底层平台上的大量并行计算资源利用率低，而上面运行的图计算任务不但收敛速度慢而且需要高额的数据访问开销以反复加载图数据以对它们进行处理。此外，图数据间的依赖也导致不同计算节点之间频繁且不规则的小消息通信，造成大量冗余的通信消息(例如，数据包的包头和图顶点ID信息)和极大的网络通信开销，限制了大规模图计算的在超级计算机上的性能和拓展性。

[0004] 专利文献CN110704693A公开了一种分布式图计算系统和方法，系统包括多个计算机和数据库，每台计算机上具有一个或多个计算结点，首先进行初始化，各个计算结点分别从数据库中读取不相交的原图的一部分边；主体计算流程，采用以子图为中心的迭代化计算方法，同时加入图缩减和重新划分过程以加速收敛，其中每轮迭代包含以下步骤：重新划分步骤，在每轮迭代的开始，首先对当前计算的图进行重新划分；本地计算步骤；缩减步骤，每个计算结点本地计算完成后，删除被判定无用的部分点/边，对原图进行重构；判断剩下的所有边是否能够存储在单个计算结点，为是的情况下，迭代结束，否则返回到重新划分步骤。本发明图计算方技术可以有效减少算法收敛所需的迭代轮数，提高计算效率。

[0005] 此外，一方面由于对本领域技术人员的理解存在差异；另一方面由于申请人做出本发明时研究了大量文献和专利，但篇幅所限并未详细罗列所有的细节与内容，然而这绝非本发明不具备这些现有技术的特征，相反本发明已经具备现有技术的所有特征，而且申请人保留在背景技术中增加相关现有技术之权利。

发明内容

[0006] 现有技术中，在进行图计算时，所有图顶点之间状态传递需要沿着它们之间的依赖关系链串行进行，这使得底层平台上的大量并行计算资源利用率低，上面运行的图计算任务不但收敛速度慢而且需要高额的数据访问开销以反复加载图数据以对它们进行处理。此外，图数据间的依赖也导致不同计算节点之间频繁且不规则的小消息通信，造成大量冗余的通信消息(例如，数据包的包头和图顶点ID信息)和极大的网络通信开销，限制了大规模图计算在超级计算机上的性能和拓展性。

[0007] 针对现有技术之不足，本发明提供了一种面向后E级图计算的方法，所述方法至少包括：分布式异步图处理和建立层次化超大规模分布式通信；所述分布式异步图处理的步骤至少包括：在构建核心子图的情况下，至少一个计算节点选取所述核心子图中包含活跃图顶点的图划分块且基于拓扑结构感知的图处理机制对所述图划分块进行异步图计算处理。

[0008] 本发明的异步图计算处理，通过优先选取核心子图中包含活跃图顶点的块进行处理，使得重要图顶点的状态快速传递，加快难以收敛的图顶点状态的收敛速度，避免图计算的长尾效应；还通过在处理每个块时，采用拓扑结构感知的图处理机制的方式将图划分块中的图数据按照图拓扑顺序调度到各核上并行处理，从而有效加快图顶点状态传递、避免无效图顶点处理和减少数据访问开销。

[0009] 所述建立层次化超大规模分布式通信的步骤至少包括：基于树型的方式设置计算节点，基于社区结构感知的划分方式将图数据分区并分配至各个计算节点；在各个计算节点及其管辖的下层计算节点的图数据均收敛后，所述计算节点与其自身所属的上层计算节点、同层次计算节点进行通信以实现同级之间的图顶点状态的同步；逐层次通信直至整个集群负责的图顶点状态收敛。

[0010] 本发明中，在图数据分区时，采用社区结构感知的划分方式，将图顶点之间依赖紧密的核心子图分配到同一分组中，从而使得子图内的频繁通信发生在同一分组内部，减少全局通信开销。

[0011] 优选地，所述方法还包括：在进行分布式异步图处理之前，各个计算节点将本地图分区划分为细粒度的块，并且根据块中图顶点度数来区分高度数块和低度数块，选取所述高度数块来构建核心子图。其中，在构建核心子图的过程中，识别核心图顶点，并且将核心图顶点的状态数据合并存储。本发明的状态数据的合并，能够提高数据时间/空间局部性，保证每次加载的数据大多都是有效的，减少数据访问开销。

[0012] 优选地，所述至少一个计算节点选取所述核心子图中包含活跃图顶点的图划分块且基于拓扑结构感知的图处理机制对所述图划分块进行异步图计算处理的步骤至少包括：至少一个计算节点选取所述核心子图中包含活跃图顶点的高度数块，基于拓扑结构感知的图处理机制，将所述高度数块中的图数据按照图拓扑顺序调度到各核上并行处理，能够有效加快图顶点状态传递、避免无效图顶点处理和减少数据访问开销。

[0013] 优选地，所述至少一个计算节点选取所述核心子图中包含活跃图顶点的图划分块且基于拓扑结构感知的图处理机制对所述图划分块进行异步图计算处理的步骤还包括：在高度数块的处理过程中，将图顶点状态的更新数据按照图顶点ID顺序进行排序，再将排序后的所述图顶点状态更新数据按照排好的顺序应用到相应图顶点来更新其图顶点状态值，以将图顶点状态更新数据的随机访问转化为规则地有序访问，减少无效数据访问。

[0014] 优选地，所述至少一个计算节点选取所述核心子图中包含活跃图顶点的图划分块且基于拓扑结构感知的图处理机制对所述图划分块进行异步图计算处理的步骤还包括：在所述计算节点的图数据被计算至局部收敛后且没有达到需要通信的条件的情况下，所述计算节点生成需要通信状态值的图顶点与不直接相邻的至少一个图顶点之间的状态值依赖关系，所述计算节点基于所述状态值依赖关系在通信后更新图顶点状态值，使得图顶点的更新进行传递，能够使得通信后更新的图顶点状态值能够快速传递给更多的图顶点，加快图顶点状态的传递速度，提高计算资源的有效并行度。

[0015] 优选地，所述基于树型的方式设置计算节点，基于社区结构感知的划分方式将图数据分区并分配至各个计算节点的步骤至少包括：将若干计算节点按照树型的方式设置，将图数据按照社区结构感知的划分方式划分并形成图分区，根据所述状态值依赖关系将图顶点之间的依赖紧密的核心子图分配至同一组计算节点中，使得所述核心子图内的频繁通信发生在同一计算节点分组内部，减少全局通信开销。

[0016] 优选地，所述基于树型的方式设置计算节点，基于社区结构感知的划分方式将图数据分区并分配至各个计算节点的步骤还包括：在若干计算节点进行通信时，发送至同一图顶点的通信信息基于规约合并的方式来减少通信量；和/或向同一计算节点的若干通信信息是以合并的方式统一发送至所述计算节点的，以充分利用网络带宽，减少频繁的小消息通信开销。此外，对通信消息进行压缩，通过去掉图顶点ID等不必要的信息来进一步降低通信量。

[0017] 本发明还提供一种面向后E级图计算的系统，至少包括处理器，所述处理器至少包括：第一模块，用于分布式异步图处理；第二模块，用于建立层次化超大规模分布式通信：

[0018] 第一模块被配置为：在构建核心子图的情况下，至少一个计算节点选取所述核心子图中包含活跃图顶点的图划分块且基于拓扑结构感知的图处理机制对所述图划分块进行异步图计算处理，

[0019] 第二模块被配置为：基于树型的方式设置计算节点，基于社区结构感知的划分方式将图数据分区并分配至各个计算节点；在各个计算节点及其管辖的下层计算节点的图数据均收敛后，所述计算节点与其自身所属的上层计算节点、同层次计算节点进行通信以实现同级之间的图顶点状态的同步；逐层次通信直至整个集群负责的图顶点状态收敛。

[0020] 本发明还提供一种存储设备，其上存储有计算机程序，该程序被处理器执行时实现权利要求1至7中任一项所述的面向后E级图计算方法的步骤。

[0021] 本发明还提供一种电子设备，包括：存储器，其上存储有计算机程序；处理器，用于执行所述存储器中的所述计算机程序，以实现权利要求1至7中任一项所述的面向后E级图计算方法的步骤。

[0022] 本发明的面向后E级图计算系统、存储设备和电子设备，其优势与本发明的面向后E级图计算方法的优势相同，不再赘述。

附图说明

[0023] 图1是本发明提供的其中一种基于分组的层次化树型通信方式的逻辑结构图；

[0024] 图2是本发明提供的图计算方法中核心图顶点状态合并的逻辑示意图；

[0025] 图3是本发明提供的图计算方法中SSSP任务的状态值依赖关系的逻辑示意图；

[0026] 图4是本发明提供的图计算方法中的社区检测算法的逻辑示意图；

[0027] 图5是本发明提供的图计算方法中多计算节点间通信的逻辑示意图；

[0028] 图6是本发明提供的图计算方法中的消息压缩的结构示意图；

[0029] 图7是本发明提供的图计算方法中图顶点状态规约算法的逻辑示意图；

[0030] 图8是本发明提供的图计算方法中消息合并的逻辑示意图；

[0031] 图9是本发明提供的分布式异步图处理流程示意图；

[0032] 图10是本发明提供的层次化超大规模分布式通信流程示意图。

[0033] 附图标记列表

[0034] 10：合并状态表；20：哈希表；30：初始社区结构；31：第一社区结构；32：第二社区结构；33：第三社区结构；34：第n社区结构；41：图顶点状态值；42：主代理图顶点；43：镜像代理图顶点；51：消息压缩步骤；52：消息发送步骤；53：消息解压及规约步骤；54：生成的信息；61：图顶点ID；62：第一状态值；63：位表；64：第二状态值；65：规约算法步骤。

具体实施方式

[0035] 下面结合附图进行详细说明。

[0036] 本发明提供一种面向后E级图计算的方法及系统、存储介质以及电子设备。

[0037] 本发明的核心思想包括：首先，各计算节点利用细粒度的块来进行异步图处理，使得每个加载到缓存的块被处理到局部收敛才换出，提高数据访问局部性，避免数据冗余的反复加载；并且，优先地选择重要图数据块进行处理来加快重要图顶点的状态传播速度。其次，对每个块的处理，采用一种图拓扑感知的异步图处理机制，使活跃图顶点的最新状态能够沿着图拓扑快速传递，加快图顶点状态速度。对图计算的图顶点状态更新进行规则化来有效降低随机访存，提高缓存和内存带宽利用率，降低图顶点状态更新开销；同时，合并核心图顶点状态数据的存储和访问，提高数据时间/空间局部性，保证每次加载到缓存的图顶点状态数据大多都是有效的。生成需要通信状态值的图顶点与其他不直接相邻图顶点之间的状态值依赖关系，以此来进一步加快图顶点状态的传递速度，提高计算资源的有效并行度。每个计算节点的每轮图计算需要将其图划分块计算到局部收敛为止才触发通信，加快了图顶点状态传递，充分挖掘各计算节点的计算能力，也减少了通信次数和数据量。在各个计算节点的每轮图计算后，通过基于分组的层次化的树型通信模式，使得大量无规则的全局小消息通信规则化，即大多数无规则的全局小消息通信能够被转换成了局部通信，从而有效限制了大量无规则小消息通信对整个网络以及整个集群的负面影响；并且通过消息层次化通信方式来有效合并小消息，从而充分利用网络带宽。在通信前，对发往相同计算节点的消息进行合并和压缩，将非规则小消息通信转换成顺序的规则通信，并且去掉通信消息中的图顶点ID等不必要的信息，从而减少频繁的小消息通信开销，降低通信量，提高带宽利用率。

[0038] 实施例1

[0039] 本发明的面向后E级图计算方法，至少包括：分布式异步图处理和建立层次化超大规模分布式通信。

[0040] 分布式异步图处理的步骤包括：

[0041] 在进行分布式异步图处理之前，在构建核心子图的情况下，至少一个计算节点选取所述核心子图中包含活跃图顶点的图划分块且基于拓扑结构感知的图处理机制对所述图划分块进行异步图计算处理。

[0042] 核心子图是指：由高度数图划分块构成的子图，核心子图的处理对图计算收敛速度影响最大。

[0043] 活跃图是指：在每轮迭代处理中，需要处理的图数据。

[0044] 具体地，在进行分布式异步图处理之前，各个计算节点将本地图分区划分为细粒度的块，并且根据块中图顶点度数来区分高度数块和低度数块，选取所述高度数块来构建核心子图。

[0045] 例如，各个计算节点将其本地图分区Gi划分为细粒度的图划分块P，图划分块的大小|P|由以下公式决定：

[0046] 其中，|G|为图数据的大小，|V|为图顶点的数量，|Uv|为每个图顶点状态值的大小，|LLC|为L3缓存的大小，|R|表示预留的空间。|P|的值为满足该公式的最大正整数值。

[0047] 统计各个图划分块中图顶点的平均度数 其中VP是图划分块P的图顶点集合。|VP|是图划分块P中包含的图顶点数量，Deg(vi)是图顶点vi的度数。

[0048] 根据阈值(Threshold)来区分高度数块和低度数块。阈值(Threshold)是由用户定义的高度数块的比例来决定的。例如：现有100个图划分块，用户定义的高度数块的比例为5％，则将图划分块按照ADegP降序排序后，阈值(Threshold)为第5个图划分块P5的ADeg大于阈值(Threshold)的图划分块被判定为高度数块，将选取的高度数块来构建核心子图。

[0049] 在构建核心子图的过程中，识别核心图顶点，并且将核心图顶点的状态数据合并存储。本发明的状态数据的合并，能够提高数据时间/空间局部性，保证每次加载的数据大多都是有效的，减少数据访问开销。

[0050] 核心图是指：由高度数图顶点以及这些图顶点的边构成的子图。

[0051] 顶点是指：图是由图顶点和边构成。图顶点用于表示某个事物或者对象，边用于表示事物或者对象之间的关联关系。

[0052] 首先根据用户自定义的核心图顶点比例来判定核心图顶点。例如，如果图中有10000个图顶点，用户自定义的核心图顶点比例为0.5％，则将图顶点按照其度数Deg(v)的降序进行排序后，前50个图顶点为核心图顶点。如图2所示，每个计算节点将其本地的高度数图顶点状态合并存储在其本地的合并状态表10中。为了快速访问到本地的核心图顶点状态值，各个计算节点构建相应哈希表20，其中每个key‑value对为为图顶点v的状态值Sv在合并状态表10中的地址。

[0053] 在进行异步图计算处理时，通过优先选取核心子图中包含活跃图顶点的图划分块进行处理，使得重要图顶点的状态快速传递，加快难以收敛的图顶点状态的收敛速度，避免图计算的长尾效应。

[0054] 在选取时，优先选择核心子图中的图划分块来获取图数据。至少一个计算节点选取所述核心子图中包含活跃图顶点的图划分块。

[0055] 若该计算节点的所有图划分块均收敛，即，该计算节点的图分区中没有活跃图顶点，则表示当前轮图计算完成。如果此时达到了通信条件，即，该计算节点上的图数据和其管辖的计算节点上的图数据均收敛，则触发分布式通信模块来同步不同计算节点上的图顶点状态。如果此时还没有达到通信条件，则该计算节点生成需要通信状态值的图顶点与其他不直接相邻图顶点之间的状态值依赖关系。

[0056] 获取图数据的处理方式为：在处理每一个选取的图划分块时，计算节点的每个CPU核选取该图划分块中的一个活跃图顶点并压入其私有队列Q中。此处，压入是指：将选取的活跃图顶点按顺序写入先进先出队列Q中。每个CPU核对应一个队列Q，以便以该图顶点作为源顶点来按照图拓扑获取图数据。

[0057] 优选地，以广度优先的顺序获取图数据，并且按照图拓扑顺序进行异步图计算。如果该图划分块中没有活跃图顶点，则表示当前选取的图划分块已经局部收敛，则判断是否达到通信条件并进行相应的处理。

[0058] 广度是指：一次性访问当前图顶点的所有未访问状态相邻图顶点，并依次对每个相邻图顶点执行同样处理。

[0059] 基于拓扑结构感知的图处理机制，将所述高度数块中的图数据按照图拓扑顺序调度到各CPU核上并行处理，能够有效加快图顶点状态传递、避免无效图顶点处理和减少数据访问开销。

[0060] 拓扑结构感知的图处理机制是指：从高度数块的活跃图顶点开始，按照广度优先的遍历顺序来访问图数据并对访问的图数据进行处理，使得图数据沿着相互之间的依赖顺序进行处理。

[0061] 每个图划分块需要被处理到局部收敛时才会调度下一个块进行处理，使得加载进到缓存的图数据被反复处理直到收敛后才被置换出缓存，从而通过提高数据时间局部性(即提高数据重用率)来避免数据冗余的反复加载，减少数据访问量，减少全局同步开销，使得图顶点状态传递更快，活跃图顶点数量更多，数据并行度更高，最终提高核的利用率。

[0062] 优选地，每个计算节点的每个CPU核从其对应的队列Q中按顺序取出一个图顶点vi，获取该图顶点vi的邻居图顶点(与vi一起构成边)以及相应图顶点的状态值。

[0063] 获取图数据进行处理的方式还包括：将每条边的源顶点状态值传递到该边的目的顶点来更新目的顶点的状态值。同时，读取图顶点状态值依赖关系表，通过生成的图顶点状态值依赖关系，将通信后的图顶点状态值快速传递给其他图顶点。每次图顶点状态传递会生成一个图顶点状态更新，即<目的图顶点ID，更新状态值>。队列Q中所有图顶点的相关图数据被处理后，所生成的图顶点状态更新会生成图顶点状态更新流。

[0064] 在图划分块的处理过程中，将图顶点状态的更新数据按照图顶点ID顺序进行排序，再将排序后的所述图顶点状态更新数据按照排好的顺序应用到相应图顶点来更新其图顶点状态值，以将图顶点状态更新数据的随机访问转化为规则地有序访问，减少无效数据访问。

[0065] 对图顶点状态更新流按照其目的图顶点ID进行排序，将排序后的图顶点状态更新，顺序地应用到相应图顶点，即将更新状态值和目的图顶点的当前状态值进行计算，得出目的图顶点的最新状态值。

[0066] 对核心图顶点的状态更新，需要更新其在合并状态表10的状态值，从而提高核心图顶点状态访问的空间/时间局部性。如果图顶点的状态值被更新，则该图顶点被设置为活跃图顶点，并且压入队列Q中。

[0067] 判断队列Q中是否还存在活跃图顶点。若是，则重新进行获取图顶点以及相应图顶点的状态值。否则，重新进行图划分块的处理。

[0068] 在所述计算节点的图数据被计算至局部收敛后且没有达到需要通信的条件的情况下，所述计算节点生成需要通信状态值的图顶点与不直接相邻的至少一个图顶点之间的状态值依赖关系，所述计算节点基于所述状态值依赖关系在通信后更新图顶点状态值，使得图顶点的更新进行传递，能够使得通信后更新的图顶点状态值能够快速传递给更多的图顶点，加快图顶点状态的传递速度，提高计算资源的有效并行度。

[0069] 具体地，生成需要通信状态值的图顶点与其他不直接相邻图顶点之间的状态值依赖关系。

[0070] 由于图顶点状态值之间的依赖关系通常是线性关系，因此，两个不直接相邻的图顶点状态值的依赖关系可以表示为：Sy＝a*Sx+b，vx和vy为两个不直接相邻的图顶点，Sx和Sy为图顶点vx和vy的状态值，a和b为常量。

[0071] 例如，在图3中，需要通信图顶点状态值的图顶点为v0，对于SSSP算法，v0与其他不直接相邻图顶点(例如，v2)之间的状态值依赖关系。如图3所示，其中常量a和b分别为1和9。该依赖关系的计算方式为，进行两次迭代处理，分别得到两组图顶点vx和vy的状态值，即和，随后将根据这两组状态值计算出相应的常量a和b。

[0072] 图顶点状态值依赖关系存储。

[0073] 当两个不直接相邻的图顶点状态值的依赖关系被计算出来后，相应的参数(即，vx，vy，a和b)被存储在一个图顶点状态值依赖关系表中，如表1：图顶点状态值依赖关系表所示。

[0074] 表1：图顶点状态值依赖关系表

[0075]vx vy a b
v0 v2 1 9
v0 1 11
v3
v0 v4 1 18

[0076] 当每次通信后，需要通信状态值的图顶点被更新图顶点状态值后，可以利用生成的图顶点状态值依赖关系，将更新后的图顶点状态值快速传递给更多的图顶点，加快图顶点状态的传递速度和传播范围。

[0077] 在生成图顶点状态值依赖关系的过程中，如果某个时刻达到了通信条件即，当前计算节点上的图数据和其管辖的计算节点上的图数据均收敛，则重新选取包含活跃图顶点的图划分块进行处理。

[0078] 在进行分布式异步图处理后，建立层次化超大规模分布式通信。

[0079] 如图1所示，基于树型的方式设置计算节点。以图1中的计算节点为例，设置有4层计算节点。第0层F0的初始计算节点为Node 0。第一层F1计算节点为Node 1～Node 4。第二层F2的计算节点为Node 5～Node 8、Node 9～Node 12，……。第三层F3的计算节点为Node y～Node y+3，……。第四层F4的计算节点至少包括Node x～Node x+3，……，Node n～Node n+3，……。

[0080] 具体地，计算节点进行分组，构建层次化的树型通信架构。如图1的示例中，每个分组包含4个计算节点。该4个计算节点中除去了树型结构根节点对应的计算节点。各分组之间构成如图1所示的树型通信架构。

[0081] 各个计算节点在通信时，只与自己所管辖的计算节点、自己所属的计算节点和该所属节点所管辖的其余同层次节点进行通信。

[0082] 各个计算节点自己管辖的计算节点为树型结构的子节点，如图1中，计算节点Node y所管辖的计算节点，即树型结构的子节点为Node x，Node x+1，Node x+2和Node x+3。计算节点Node y所属的计算节点即树型结构的父亲节点为Node 5。与计算节点Node y同层次节点即树型结构的兄弟节点为Node y+1，Node y+2和Node y+3。

[0083] 基于社区结构感知的划分方式将图数据分区并分配至各个计算节点。

[0084] 具体来说，社区是图顶点之间依赖紧密的子图。

[0085] 社区将被分配到同一分组中，甚至同一计算节点，以此来降低全局通信开销。如图4所示，通过社区检测算法(例如，基于标签传播的社区检测算法)来检测出图结构中的社区关系，随后将具有社区相关的图数据分配到同一分组中。

[0086] 例如，图4中，图顶点v0～v5属于初始社区结构30；图顶点v6、v7、v13和v14属于第一社区结构31；图顶点v8～v12属于第二社区结构32；图顶点v15、v16、v19、v20和v21属于第三社区结构33。v17和v18属于第n社区结构34。

[0087] 镜像代理图顶点是指：指图顶点在不同计算节点上的副本

[0088] 例如，将初始社区结构30分配给图1中的计算节点Node x，Node x+1，Node x+2和Node x+3。优选地，在进行分区时采用笛卡尔顶点切分方法，在该方法中，只有主代理图顶点同时拥有该图顶点的出边和入边，而代理图顶点只有该图顶点的出边或者入边的一类，如图5所示。按照以上方式，图数据将被切分为图分区，然后各个图分区将分配到超级计算机的各个计算节点。

[0089] 在各个计算节点及其管辖的下层计算节点的图数据均收敛后，所述计算节点与其自身所属的上层计算节点、同层次计算节点进行通信以实现同级之间的图顶点状态的同步；逐层次通信直至整个集群负责的图顶点状态收敛。

[0090] 具体地，每个计算节点在完成其第Tj轮图计算后，将需要通信状态值的图顶点的状态值更新生成消息。

[0091] 如图5所示，计算节点上的图分区收敛后，需要把其镜像代理图顶点43的状态值生成通信消息，以便发送到其他计算节点上相应的主代理图顶点来同步不同计算节点上相同图顶点的状态值。例如，在位于第3层的计算节点Nodey上的图分区收敛后，需要把其镜像代理图顶点v5，v6和v7的状态值生成通信消息，以便发送到Nodey+1上的图顶点v5，v6和v7，来同步不同计算节点上相同图顶点的状态值。

[0092] 在图数据分区时，采用社区结构感知的划分方式，将图顶点之间依赖紧密的核心子图分配到同一分组中，从而使得子图内的频繁通信发生在同一分组内部，减少全局通信开销。

[0093] 具体地，当通信消息生成以后，如图7所示，对同一图顶点相关的通信消息进行规约，即将同一图顶点的多个通信消息合并为一个通信消息，从而减少通信量。例如，对于SSSP算法来说，需要计算出这些通信消息中的状态值以更新最小值。

[0094] 如图8所示，通过规约算法步骤65，对发往同一计算节点的信息合并到同一队列以便统一发送，从而将不规则的小消息通信转化为规则的大消息通信，即生成的信息54，提高网络带宽利用率。

[0095] 小消息通信是指：通信量小于2KB的通信消息。

[0096] 大消息通信是指：通信量大于等于2KB的通信消息。

[0097] 本发明至，将若干计算节点按照树型的方式设置，将图数据按照社区结构感知的划分方式划分并形成图分区，根据所述状态值依赖关系将图顶点之间的依赖紧密的核心子图分配至同一组计算节点中，使得所述核心子图内的频繁通信发生在同一计算节点分组内部，减少全局通信开销。

[0098] 在若干计算节点进行通信时，发送至同一图顶点的通信信息基于规约合并的方式来减少通信量；和/或向同一计算节点的若干通信信息是以合并的方式统一发送至所述计算节点的，以充分利用网络带宽，减少频繁的小消息通信开销。

[0099] 优选地，本发明还对通信消息进行压缩，通过去掉图顶点ID等不必要的信息来进一步降低通信量。

[0100] 如图6所示，将每个队列中的通信消息进行压缩。具体来说，通信消息根据图顶点ID61进行排序，随后通过使用位表63来标识与第二状态值64所对应的图顶点ID61的信息，将消息中的图顶点ID61信息去掉，从而进一步减少通信量。例如，与图顶点ID61对应的第一状态值62通过消息压缩步骤51形成位表63，其中，与位表63对应的是第二状态值64。位表63通过消息发送步骤52进行发送和接收。接收的计算节点对位表63进行消息解压及规约步骤53，再次形成图顶点状态值。

[0101] 计算节点Node y所管辖的计算节点为位于第4层的计算节点Node x，Node x+1，Node x+2，和Node x+3。在计算节点Node y自身的图数据均收敛后，计算节点Node y将规约、合并和压缩后的图顶点状态数据消息发送到其他计算节点进行通信。具体来说，多机间的通信行为主要分为以下三种行为：

[0102] 第一，该计算节点Node y和其所管辖的计算节点Node x，Node x+1，Node x+2，和Node x+3之间进行相互通信。具体来说，在通信时，Node y所管辖的计算节点先将他们的通信消息发送给Node y，Node y对通信消息按照进行规约、合并和压缩后，Node y再将规整后的消息分别发送给其所管辖的计算节点，从而避免各计算节点之间频繁的小消息通信。

[0103] 第二，若按第一种方式通信后，相应计算节点的图顶点状态值均不改变，则计算节点Node y将利用归总后的通信消息与其所属的计算节点和该所属节点所管辖的其余同层次节点进行通信，从而同步图顶点状态值。

[0104] 例如，计算节点Node y和其所管辖的计算节点上的图数据整体达到局部收敛，则计算节点Node y将利用归总后的通信消息与其所属的第2层计算节点Node 5和该所属节点所管辖的同层次的第3层计算节点Node y+1，Node y+2，和Node y+3进行通信，从而同步图顶点状态值。

[0105] 第三，若该计算节点Node y和其所管辖的计算节点需要与不直接管理或不直接所属的计算节点(例如，图1中的Node n，Node n+1，Node n+2和Node n+3)进行通信时，通信消息会根据树型通信结构进行发送和传递，避免全局的频繁小消息传递。如图1所示，相关通信消息会先发送到Node y进行汇集，随后按照树型层次化通信结构，将汇聚后的消息发送到Node 5，随后再发送到Node y+3，Node y+3将相关通信消息分别发送到相应计算节点(例如，图1中的Node n，Node n+1，Node n+2和Node n+3)。通过这样的方式，使得全局通信消息被充分规约、合并和压缩，使得网络通信行为更规则。

[0106] 当所有计算节点的图数据均收敛后，即当所有计算节点与其所属的计算节点和其所属节点所管辖的其余同层次节点进行通信后，图顶点状态值均不再改变，则计算结束。

[0107] 实施例2

[0108] 本发明还提供一种面向后E级图计算系统，至少包括处理器，所述处理器至少包括：第一模块，用于分布式异步图处理；第二模块，用于建立层次化超大规模分布式通信。第一模块与第二模块以有线或无线的方式建立通信连接。

[0109] 第一模块和第二模块均可以是处理器、专用集成芯片、服务器、云服务器中的一种或几种。第一模块和第二模块还能够集成为一个处理器、专用集成芯片或服务器。

[0110] 第一模块被配置为：在构建核心子图的情况下，至少一个计算节点选取所述核心子图中包含活跃图顶点的图划分块且基于拓扑结构感知的图处理机制对所述图划分块进行异步图计算处理，

[0111] 第二模块被配置为：基于树型的方式设置计算节点，基于社区结构感知的划分方式将图数据分区并分配至各个计算节点；在各个计算节点及其管辖的下层计算节点的图数据均收敛后，所述计算节点与其自身所属的上层计算节点、同层次计算节点进行通信以实现同级之间的图顶点状态的同步；逐层次通信直至整个集群负责的图顶点状态收敛。

[0112] 如图9所示，第一模块执行的步骤示例为：

[0113] S0：开始。

[0114] S1：各计算节点对其图分区进行细粒度划分，并构建核心子图。

[0115] S2：识别核心图顶点；对核心图顶点状态进行合并。

[0116] S3：判断是否存在活跃数据块；若否，进入步骤S4，若是，进入步骤S7。

[0117] S4：判断是否达到通信条件；若否，进入步骤S5；若是；进入步骤S16。

[0118] S5：生成需要通信状态值的图顶点与其他不直接相邻图顶点之间的状态值依赖关系。

[0119] S6：图顶点状态值依赖关系存储。

[0120] S7：按照重要度选择一个包括活跃图顶点的图划分块。

[0121] S8：判断该图划分块是否存在活跃图顶点；若否，返回步骤S3；若是，进入步骤S9。

[0122] S9：选取该图划分块中的活跃图顶点并压入队列Q。

[0123] S10：从队列Q中按顺序取出一个图顶点。

[0124] S11：读取与该图顶点相关的边数据以及图顶点状态数据。

[0125] S12：将每条边的源顶点状态值传递到该边的目的顶点来更新目的顶点的状态值，读取图顶点状态值依赖关系表，将通信后所更新的图顶点状态值快速传递给其他图顶点，并对图顶点状态值更新规则化。

[0126] S13：判断在更新时目的顶点的状态值是否被更新；若否，进入步骤S15；若是，进入步骤S14。

[0127] S14：目的顶点被设置为活跃图顶点，并且压入队列Q中。

[0128] S15：判断队列Q是否还存在活跃图顶点，若否，返回步骤S8；若是，进入步骤S16。

[0129] S16：结束。

[0130] 如图10所示，第二模块执行的步骤示例为：

[0131] S0：开始，

[0132] S21：对计算节点进行分组，构建层次化的树型通信架构；

[0133] S22：对图数据进行分区，随后将图分区分配到各个计算节点；

[0134] S23：在计算节点完成第Tj轮图计算后，将图顶点状态数据的更新生成通信消息。

[0135] S24：与同一图顶点相关的通信消息进行规约计算。

[0136] S25：将发往相同计算节点的通信消息合并，并且对通信消息进行压缩。

[0137] S26：判断该计算节点所管辖的计算节点和其自身的图数据是否收敛；若否，重新进行判断；若是，进入步骤S27。

[0138] S27：该计算节点和其所管辖的计算节点之间进行相互通信。

[0139] S28：判断相应计算节点的图顶点状态值是否均不改变；若否，进入步骤S32；若是，进入步骤S29。

[0140] S29：与计算节点Node n所属的计算节点和由该所属的计算节点所管辖的其余同层次节点进行图顶点状态信息同步。

[0141] S30：判断是否需要与不直接管理或不直接所属的计算节点进行通信；若是，进入步骤S31；若否，进入步骤S32。

[0142] S31：通信消息根据树型通信结构进行发送和传递，均在父亲计算节点汇聚后统一发送。

[0143] S32：判断在所有计算节点通信后，图顶点状态值是否有更新；若否，进入步骤S34；若是，进入步骤S33。

[0144] S33：对计算节点Node n的计算进入下一轮，j＝j+1，进入步骤S23。

[0145] S34：结束。

[0146] 本发明还提供一种存储设备，其上存储有计算机程序，该程序被处理器执行时实现本发明的面向后E级图计算方法的步骤。

[0147] 本发明还提供一种电子设备，包括：存储器，其上存储有计算机程序；处理器，用于执行所述存储器中的所述计算机程序，以实现本发明的面向后E级图计算方法的步骤。

[0148] 需要注意的是，上述具体实施例是示例性的，本领域技术人员可以在本发明公开内容的启发下想出各种解决方案，而这些解决方案也都属于本发明的公开范围并落入本发明的保护范围之内。本领域技术人员应该明白，本发明说明书及其附图均为说明性而并非构成对权利要求的限制。本发明的保护范围由权利要求及其等同物限定。本发明说明书包含多项发明构思，诸如“优选地”、“根据一个优选实施方式”或“可选地”均表示相应段落公开了一个独立的构思，申请人保留根据每项发明构思提出分案申请的权利。