1.4　主要贡献

为了应对1.3节中描述的四个方向上的挑战，业界和学术界的研究人员已经提出了诸多的优化方法。它们分别可以用于缩短在图数据载入路径上的不同阶段的执行时间，从而在特定的情况下可以提升图计算系统整体的运行效率。然而，根据调研发现，在这四个方向上依然还有可以优化的余地。因此，本书分别在这四个方向上进行了进一步的研究，提出了新的优化方法。经测试，通过将本书的方法和已有的优化方法组合在一起使用，重新实现的图计算系统能够拥有远高于已有系统的效率。具体来说，本书作出了如下的四个主要贡献。

（1）三维的图计算任务划分算法

在分布式图计算系统中，通过减少通讯量缩短从网络将所需的数据载入本地内存中这一步骤的时间是决定系统整体运行速度的一个非常关键的步骤。而对于分布式图计算系统来说，其远程通讯量的大小又主要是由其所使用的图计算任务划分算法决定的。由于这一问题的重要性，其一直是一个热点的研究方向，也已经有许多的图计算任务划分算法被提出和实现。但是，经过调研发现，这些已有的方法都假定图计算系统所处理的数据图中每一个点和边都是不可划分的单元。因此，它们都将图计算问题的任务划分等价成了图的划分问题。然而，在实际的应用场景中，有许多的数据挖掘和机器学习任务也被建模成图计算问题进行运算。在这种情况下数据图中经常会出现每一个点和每一条边的数据都是一个向量的情况，因此是可以被再次划分的。基于这一发现，本书提出了一种新型的划分方法以对这一之前未被重视的维度进行划分。换句话说，本书提出的新型划分方法将尝试将一张数据图中的每个点进一步地划分成子点，并把同一个点划分出的不同子点分配给不同的计算节点。这一维度在传统的一维和二维划分方法中都没有被考虑到，因此将这种划分方法称为三维的划分方法。根据本研究的实验结果，三维的划分方法可以极大地减少集群中各个计算节点之间的通讯量，从而提升系统整体的性能。

（2）分层的外存图计算数据组织

与分布式图计算的情况类似，已有的外存图计算系统也都假定一张数据图中每个点的点权都是不可划分的单元。因此，在它们的数据组织格式中，一次载入必须完整地载入一个点所有的点权。在内存容量一定的情况下，这一限定条件就会限制一次性能够载入的点的数量的上限。而由于图计算的特殊性质，一般来说，一次能载入的点的数量越少也就意味着平均每一个点会被载入的次数越多。相对的，本书提出了在图计算应用允许的情况下将点权分层并分别存放的外存数据组织方法。通过将点权分层，提升了一次性能够载入的点的数量，从而减少了每一个点的平均载入次数。这也就意味着在点权方面减少了从外存设备到内存的载入数量，优化了数据载入路径上这一步骤的执行时间。但同时，本研究的方法也意味着会增加每一条边的边权的平均载入次数。不过，根据测试结果，通过选取一个合适的层数可以达成这一增一减之间的平衡，新型数据组织格式可以减少外存读写的数量，从而提升系统整体的性能。

（3）基于矩阵的图计算引擎的自动优化

为了提升图计算引擎的效率，目前主流的一种方法是通过利用图这一数据结构和稀疏矩阵间数学上的等价特性将图计算操作转化成矩阵操作，再利用高性能计算领域内已有的针对矩阵计算的优化方法对其进行优化。然而，根据调研发现，目前基于矩阵的计算引擎大部分系统都采用了一种非常原始的运行方式，因此还有巨大的提升余地。具体来说，这些系统经常将每一个矩阵操作孤立开来单独执行。同时，程序的执行顺序也是严格地按照程序员给定的顺序执行的，这就好像是单机程序在编译时完全关掉了编译优化，使用的是“-O0”选项进行编译的。虽然这种方法实现起来最为简单，但很明显还存在极大的优化空间。为了解决这一问题，本书提出了一个基于数组的被称为KASEN的新型编程模型。KASEN通过定义一个严格的计算和通信模型，使得分析程序并衡量它们的表现成为可能。基于这样的功能设计了一个KASEN的自动优化器，可以自动对程序员编写的原始程序进行高级优化。经评估，KASEN的优化器可以显著地减少内存的读／写、缓冲区的内存开销和网络流量，从而达到了最高5.82倍的加速比。

（4）新型存算融合的图计算编程框架

为了应对新型存算融合体系结构所带来的挑战，本书提出了一种新型的图计算编程框架。与已有的针对存算融合体系结构的图计算系统不同，这一系统同时考虑了硬件的体系结构、软件的运行环境以及数据的划分和组织方式三方面的因素，并进行了协同地设计。虽然已有的系统中也有很多注意到了数据划分的重要性，不过在这些系统之中都是先决定好了系统的体系结构和编程框架之后再决定数据划分的方法，这一决定使得很多有效的划分方法无法被使用。相对的，本书的新型系统通过使用新的图数据划分算法极大地减少了跨立方通讯量；同时在通讯时利用了广播的技巧削减瓶颈连接的通讯量，因此其对这些特殊链接的压力也要小得多；本书的编程模型还可以非常简单地实现数据通讯和计算重叠的优化方法，从而进一步地隐藏了跨立方通讯的延时。