摘要

由于具有良好的表达能力，图数据结构被广泛用来对元素间具有复杂联系的数据进行建模，如社交网络、知识图谱等。随着信息化技术的迭代更新和互联网应用的蓬勃发展，可以对大规模图数据进行分析的处理技术逐渐成为当前学术界和业界的热门研究课题之一。已有为数众多的图计算系统被提出和应用，并取得了巨大的商业成功。

然而，现有的图计算系统主要基于一些简单化假设实现，如点权不可分割、单个计算操作可以孤立地执行等，因此很难达到下层硬件所能支持的最高计算效率。为解决这一问题，本书通过分析，发现大量图计算应用的主要效率瓶颈在于数据载入速度，于是将不同环境下图计算系统的数据载入途径分为四个方面分别进行了研究。本书的主要创新成果如下。

（1）提出了一种三维图计算应用任务划分方法。该方法基于数据图中点权可进一步划分这一发现，拓展了一个全新的任务划分维度。与传统的一维和二维划分方法不同，三维划分方法允许将数据图中的点进一步划分为子点，并分配给不同的计算节点。测试结果显示，三维划分方法最高可以减少90.6%的通讯量，从而达成提升整体运行效率的目的。

（2）提出了一种分层的图数据组织格式。通过在外存设备上分层存储图数据，计算系统可以一次性载入更多的点，从而降低单个点重复读取的次数，达到提高计算效率的目的。测试表明基于这一设计实现的新型外存图计算系统比已有系统有明显的性能提升，最高可达6.4倍的加速比。

（3）提出了一种矩阵图计算引擎的自动优化算法。该算法主要基于循环融合优化的原理，并同时考虑了分布式环境下数据一致性的要求。在保证计算正确性的同时，该算法可以通过自动流水线化的方法提升图计算应用的数据局部性，从而减少内存带宽压力。实验表明该方法最高可将原程序加速5.8倍。

（4）提出了一种针对新型存算融合器件的图计算模型。针对存算融合这一全新的支持直接在内存器件上进行计算的体系结构，提出了与之相适配的新型图计算模型。该模型通过限定用户的编程接口，使得自动的通讯去冗余成为可能。并进一步提出了基于广播树的更新传播算法，可以有效减少瓶颈链路上的通讯量。计算结果显示，上述两种方法最高可以减少近95%的通讯量。

关键词：图计算；分布式计算；矩阵计算；局部性；PIM