面向大规模图计算的系统优化（2）
摘要
图是描述事物及事物间关联的一种重要数据结构，它广泛应用于多个领域。由于图具有与其他数据结构不同的特性且图数据规模逐年增长，而用通用性系统处理图数据的效率低下，因此有众多工作研究了面向图的系统设计与优化，以更好地对上层应用提供支持。
本系列文章首先回顾图的概念，并对图算法进行分类讨论，并引出图计算系统的基本分类（第一部分)；接下来，详细讨论三大类系统：基于CPU的图计算系统、基于异构器件的图计算系统和基于新兴非冯·诺依曼器件的图计算系统，并对图计算系统中使用的编程模型进行分类与介绍（第二部分，本文）。随后，文章介绍了工业界研究和使用的图计算系统特点。最后，通过分析现有系统面临的挑战，文章指出图计算系统的发展趋势，以对未来研究提供借鉴作用（第三部分）。
本系列文章笔者胡静波为清华大学清华大学电子工程系硕士生；戴国浩为清华大学电子工程系助理研究员、博士后。该文工作得到清华大学和壁仞科技研究院联合研究项目的支持。
前文回顾：面向大规模图计算的系统优化（1）
03
左中括号
图计算系统研究现状
左中括号
图3.1 图计算系统的分类及时间线表示
3.1 基于CPU的大规模图计算系统
基于CPU的图计算系统以CPU作为计算单元，针对其特性进行了相对应的优化，按照图数据存储位置的不同，可分为以下三类：分布式图计算系统、单机内存图计算系统和单机核外图计算系统。在本小节中，我们选取了若干个有代表性的图系统进行介绍。
谷歌公司在2010年提出了分布式大规模图计算系统Pregel[27]。Pregel[27]采用同步计算模型，在每次迭代中，节点会接收邻居信息，并通过用户自定义的更新函数向外传播。2012年提出的GraphLab[29]能够支持异步图计算，利用锁定引擎保证顺序一致性，同时提高并行性。同年提出的PowerGraph[28]利用幂律图的结构特征，提出了一种新的数据布局方式，并支持增量缓存过程和异步实施。
2013年提出的Trinity[30]利用图形访问模式来优化内存管理和网络通信，能够同时支持大规模图的在线查询和离线分析。不同于Pregel等图系统[27, 29, 19]中采用的以顶点为中心的局限性计算模式，Trinity[30]凭借其灵活的计算建模功能，拥有支持任何图应用的能力。2014年提出的GraphX[31]是一种基于Apache Spark[56]构建的嵌入式图形处理框架，通过利用分布式数据流框架中的先进技术，GraphX[31]为图形处理带来了低成本的容错能力，且对于图形算法的处理速度比基本数据流系统快一个数量级。
2015年提出的PowerLyra[32]进一步关注了自然图中度分布不均的问题，对低度顶点使用集中式计算以避免频繁的通信，并为高度顶点分配计算以平衡工作量。另外，PowerLyra[32]提供了一种融合边切割和顶点切割的混合图分区算法。评估表明，PowerLyra[32]的性能比PowerGraph[28]高出5.53倍。
2016年提出的Gemini[33] 指出先前的图系统为了实现可扩展性，其开销已成为影响效率的性能瓶颈。鉴于此，Gemini[33]应用了针对计算性能多种优化方式，如：基于块的分区方案、压缩对顶点索引的访问方案、NUMA（non-uniform memory access，非均匀访存模型）感知子分区等。在性能方面，Gemini[33]比先前的分布式图计算系统提升39.8倍。
2018年提出的ShenTu[34]利用四项关键创新：硬件专业化、超节点路由、片上分类和可感知的消息传递，实现了前所未有的性能和可伸缩性。ShenTu[34]能够在几秒钟内遍历70万亿条边的图，并有效处理现实中的应用问题，如垃圾邮件检测等。
2019年提出的CGraph[18]指出现有的分布式系统面临的问题是数据访问成本占并行迭代图形处理(CGP)计算成本的比例很高，从而导致吞吐量较低。CGraph[18]采用以数据为中心的负载模型，使得图数据结构与并行任务的顶点状态解耦。结果表明，与现有分布式系统相比，CGraph[18]能将CGP的吞吐量提高3.47倍。
3.1.2 单机内存图计算系统
虽然分布式图计算系统能够有效处理大规模图，但性能受限于复杂的图分割算法、网络带宽、通信开销等。基于单机内存的图计算系统能够有效地缓解上述问题，因而也被广泛研究。
2013年提出的Ligra[14]是一种轻量级的图形处理框架，易于遍历算法的程序编写，且能够适应顶点级的密度。同年提出的Galois[15]设计了用于并行图分析的领域特定语言(DSL),并在通用基础框架上进行了实现，结果表明，即使对于幂律图，其性能也能超过原始DSL系统。
2015年提出的Polymer[16]指出先前的图系统因对NUMA特性影响小而性能欠佳。因此，Polymer[16]应用了以下技术点：根据访问模式以差异化分配图数据，最大程度地减少远程访问。其次，通过使用顶点的轻量级复制，将随机访问转换为顺序访问。利用边分割改善负载平衡，并根据活动顶点的比例自适应地调整数据结构以加快收敛速度。结果表明，其性能一般优于Ligra[14]、Galois[15]等单机图系统。同年提出的GraphMat[17]通过获取顶点程序并将其映射到后端中的高性能稀疏矩阵运算来发挥作用，其执行速度比GraphLab[29]，Galois[15]等高性能框架快1.1-7倍。
3.1.3 单机核外图计算系统
2012年提出的GraphChi[19]是一个基于磁盘的系统，利用新颖的并行滑动窗口策略能够将大图分解为小部分，并对数十亿条边的图形进行有效处理且支持增量图，具有与Pregel[27]、PowerGraph[28]等分布式图系统相近的处理性能。
2013年提出的X-Stream[20]采用以边为中心的编程模型，能够流式传输完全无序的边列表，以执行顺序访问，且无需对边进行排序以提升性能。同年提出的TurboGraph[21]充分利用了多核并行性和I/O并行性，并提出了有效的磁盘和内存结构，其性能比GraphChi[19]高出了1-4个数量级。
2015年提出的GridGraph[22]在预处理中将图形分区为一维的顶点块和二维的边块，依靠双滑动窗口策略流式处理边，并应用动态顶点更新，以减少I/O量。其性能优于GraphChi[19]和X-Stream[20]。同年提出的FlashGraph[23]仅从磁盘访问应用程序中请求的边列表，并对I/O请求进行合并以提高吞吐量，其系统性能已经超过了分布式系统PowerGraph[28]一个数量级以上。
2017年提出的Mosaic[24]采用了节省空间的图形表示法，即希尔伯特有序切片，并包含了以顶点为中心和以边为中心的混合计算模型。同年提出的Graspan[25]是第一个为过程间静态分析量身定制的单机磁盘并行图计算系统，其采用以边为中心的计算模型，并同时支持内存中和内存外的计算。
2018年提出的RStream[26]是第一个利用磁盘支持存储中间数据的单机核外图挖掘系统。它利用了丰富的编程模型，以支持各种图挖掘任务，另外，它利用流的方式访问边，以提高运行效率。结果表明，Rstream[26]的性能优于多个分布式图挖掘系统。
2019年提出的Automine[39] 是第一个为图挖掘应用程序提供高级抽象和高性能的单机图挖掘系统，它采用高效的嵌入表示和优化技术，能自动生成有效的图挖掘算法，且有效减少内存。结果表明，AutoMine[39]的性能通常比RStream[26]高几个数量级，并能完成更大规模的图挖掘任务。
3.2基于异构器件的大规模图计算系统
近年来随着异构器件的兴起以及图应用中任务的多样化和复杂性，基于异构器件的大规模图计算系统的性能已经超过了基于CPU的系统。在本小节中，主要介绍基于GPU和FPGA的图计算系统。
GPU底层含有多个流处理器，适合于执行大量并行的计算任务，许多先前的文献已在单一图算法上利用GPU进行加速[44,57]。但图结构的不规则性仍使在GPU上有效地处理图算法变得困难。Medusa[35]于2014年被提出，在GPU上提供了通用的图算法支持。Medusa[35]开发了一种称为EMV(Edge-Message-Vertex)的图形编程模型，能够对顶点和边进行细粒度的处理。另外，它应用成本模型指导的复制以减少跨GPU间的数据传输。同年提出的Cusha[36]利用以顶点为中心的计算模型，为了解决因GPU内存不足和随机访问所带来的问题，Cusha[36]将图数据组织成有序边的分片集合，结合级联窗口的使用，能够实现GPU对处理稀疏图更高的利用率。
2016年提出的Gunrock[37]是一个批量同步图计算系统，采用以数据为中心的编程模型，将GPU计算单元、优化策略和编程模型结合在一起，从而降低编程的复杂性，并权衡性能。结果表明，Gunrock[37]在图算法上的平均执行速度比PowerGraph[28]至少高出一个数量级。
2018年提出的Tigr[38]是一种图转换框架，使用均匀度数转换机制(UDT,uniform-degree treetransformation)将度高的顶点拆分成多个顶点，在保证算法正确性的前提下，将不规则的图数据变得更具规则性，从而更利于GPU的处理。在性能方面，Tigr[38]普遍优于Cusha[36]和Gunrock[37]。
3.2.2基于FPGA的图计算系统
由于FPGA具有灵活性和可编程性，FPGA平台提供了高效处理图形数据的机会，一系列基于FPGA的图计算系统也被相继提出。2014年提出的GraphGen[40]采用以顶点为中心的计算模型，它能够在FPGA平台上支持通用的图算法，利用流水线架构和指令集设计，GraphGen[40]具有比CPU更高的性能，但处理的图大小受限于FPGA的片上容量。
2016年提出的FPGP[41]同样采用以顶点为中心的计算模型，它基于间隔分片的结构，能够最大化图数据的片外带宽，提高并行性并扩展到更大规模的图。2017年提出的ForeGraph[42]是一个基于多FPGA架构的大规模图系统，每个FPGA板仅将一部分图数据存储在片外。顶点和边会被顺序加载到FPGA芯片上，依靠有效的调度方案，各个芯片并行处理图数据而不会发生冲突。结果表明，ForeGraph[42]的性能比先前基于FPGA的图计算系统高4.54倍。
2019年提出的FabGraph[43]为了解决ForeGraph[42]中单机节点缓存机制导致大量顶点数据传输从而浪费带宽的问题，因此采用两级顶点缓存机制，并利用片上存储资源进行实现。结果表明，对于基准图算法，FabGraph[43]比ForeGraph[42]的处理速度快2.5-3.1倍。
2020年提出的GraphABCD[79]是一种异步异构图分析框架。为提高迭代算法的收敛速度，GraphABCD[79]使用了块坐标下降视图，且能以最小的同步开销拓展到异构和分布式系统。结果表明，基于CPU-FPGA异构平台的GraphABCD[79]相比于GraphMat[17]收敛速度和执行速度平均提高了4.8倍和2.0倍。
3.3基于新兴非冯·诺依曼器件的大规模图计算系统
在大规模图应用中，访存受限是其区别于其他应用的显著特点。传统的冯·诺依曼架构需要在存储单元和计算单元间进行数据搬运，而这会带来大量的开销，从而成为系统性能的瓶颈。为了解决上述问题，研究者们开始考虑在非冯·诺依曼架构的新型硬件上进行大规模图计算。
3.3.1面向大规模图计算的存储系统
2018年提出的GAS[45]利用专用的内容可寻址存储器(CAM，Content-AddressableMemory)来存储随机数据，并通过一系列的关联搜索来确定访问模式。GAS[45]不仅可以提高随机访问的效率，也可以减少存储器访问的等待时间。结果表明，GAS[45]可以节省能耗34%，减少执行时间27%。同年提出的HyVE[46]通过在顶点和边上进行数据分配和调度，将图数据有效映射在ReRAM（金属氧化物电阻随机存取存储器）等存储结构上，与图处理中的传统内存系统相比，HyVE[46]将内存能耗降低了69％。
3.3.2基于近存储的图计算系统
随着器件工艺的不断发展，在存储芯片内部可以集成计算单元，从而无需将数据搬运到片外就可以完成计算。“大数据”和3D堆栈技术的最新发展使PIM（内存中处理，Processing-In-Memory)成为处理大规模图数据的实用和可行的解决方案。2015年提出的Tesseract[48]是是基于HMC（HybridMemoryCube，最著名的3D堆栈存储技术之一）的PIM并行图处理体系结构。Tesseract[48]设计不同内存分区间的有效通信方法，并拥有独特硬件设计的编程接口、硬件预取器等。与传统系统相比，Tesseract[48]的性能平均提高了十倍，且能耗平均降低了87％。
2017年提出的GraphPIM[50]借助较小的体系结构扩展来支持PIM指令卸载，以减少原子开销，且能有效提升图处理性能。2018年提出的GraphP[49]指出Tesseract[48]采用的以顶点为中心的编程模型会限制HMC的本地带宽。为了解决上述问题，GraphP[49]采用如下关键技术：“源剪切”分区、“两阶段顶点程序”和分层通信和重叠。结果表明，与Tesseract[48]相比，GraphP[49]平均提供1.7的加速和89％的节能。
3.3.3基于存算一体的图计算系统
由于图可以自然地表示为邻接矩阵，并且大多数图算法可以通过某种形式的矩阵矢量乘法来实现，而ReRAM是执行矩阵矢量乘法的基本硬件构件，且具有如下优点：基于ReRAM的体系结构能够享受计算并行性以及计算与数据移动之间更高比例的优势；在ReRAM中执行计算还可以减少数据移动，实现近距离数据处理，即无需像传统体系结构一样经过多个层次的存储结构传输数据。综上，基于ReRAM的架构成为高效大规模图处理的又一方案。
2018年提出的GraphR[53]是第一个基于ReRAM的图形处理加速器，它由两部分组成：内存ReRAM和图形引擎。核心图的计算在图形引擎中以稀疏矩阵格式执行。结果表明，与基于PIM的架构相比，GraphR[53]实现了1.16-4.12倍的加速和3.67-10.96倍的节能。
2019年提出的GraphSAR[54]指出自然图的稀疏特性会阻碍ReRAM处理图的性能。因此，GraphSAR[54]考虑用稀疏性来划分图，以减少存储空间的浪费。另一方面，边计算在存储器中执行，以减少输出边数据的开销。结果表明，相比于GraphR[53]，GraphSAR[54]的能耗降低了4.43倍，速度提高了1.85倍。
04
编程模型
由前文可知，图计算系统通常基于一定的编程模型，如表4.1所示，以对应执行算法中的一次迭代过程。不同编程模型适合于不同的图算法，并且对图系统的性能具有不同方面的优势。在本文中，我们主要介绍三类编程模型：以顶点为中心、以边为中心和以子图为中心。
表4.1不同图计算系统与使用的编程模型间的对应关系
编程模型 | 图计算系统 |
以顶点为中心，包含GAS （收集-应用-分散，Gather-Apply-Scatter）模型 | Pregel[27]、PowerGraph[28]、Tesseract[48]、Mosaic[24]、GraphLab[29]、PowerLyra[32]、GraphGen[40]、FPGP[41]、GraphX[31]、Trinity[30]、Pregelix[52]、Pregel+[55]、VENUS[66] |
以边为中心 | X-Stream[20]、Mosaic[24]、Graspan[25] |
以子图为中心 | Giraph++[47]、GoFFish[51]、Blogel[59]、Arabesque[60]、NScale[61] |
4.1以顶点为中心
以顶点为中心的编程模型是在2010年由Pregel[27]引入的，由于它支持的算法多样，且易于编程，此后，大部分图计算系统都沿用该模型。以顶点为中心的模型思想是在图算法的每次迭代中，图中的顶点都以自身为中心，接受来自邻居节点值或所连接的边权重信息，并利用用户自定义的执行函数进行信息整合和自身顶点值运算，最后，顶点再将更新后的值传递给邻居节点，并完成本轮迭代，如图4.1所示。
另外，在计算过程中，顶点存在两种状态，分别为活跃(active)和不活跃(inactive)。最初，所有顶点都会被定义为活跃状态，此后，随着迭代的进行，一些顶点会因用户定义的计算和收敛条件而转变为不活跃状态。在图算法执行的过程中，只有活跃的顶点会参与迭代运算从而更新自身值，且每次迭代操作均为同步。
在此基础上，为了提升现实世界中幂律图的计算性能，PowerGraph[28]提出了GAS模型，即分为收集、应用和分散三个阶段，其中，收集和分散操作是在边级别上进行的，而不是顶点级别。以顶点为中心的模型在表达算法层面是十分通用的，尤其是当计算是集中在相邻顶点和边数据上，如PageRank[8]、BFS[9]等。然而，非迭代图算法很难在以顶点为中心的模型中表达，且如三角形计数等图挖掘算法在该模型上的执行效率也较低。
图4.1以顶点为中心的编程模型示意图[81]
4.2以边为中心
以顶点为中心的编程模型虽然具有高算法通用性、易于编程的优点，但会带来边的大量随机访问问题，减少带宽利用率。而这个问题在图应用中尤其突出。为了解决上述问题，X-Stream[20]第一个提出了以边为中心的编程模型。该模型分为两个阶段：分散和收集，如图4.2所示。分散阶段通过遍历边而获得源顶点，顶点同样拥有两个状态：活跃和不活跃。如果源顶点处于活跃状态，则会连同边一起作为消息进行发送。在收集阶段，会扫描接收到的消息，并获取目标节点，通过用户自定义的计算，目标节点会更新自身值，至此完成本轮操作。与以顶点为中心的模型不同的是，由于分散阶段和收集阶段处于同一迭代过程中，因此，收集阶段可以直接访问分散阶段发送的消息，且边列表无需进行排序。
在应用层面，以边为中心的模型也同样适合执行PageRank[8]等迭代算法，且通常具有较低的内存需求，因为不需要并行访问接收和发送的消息。但此特性会限制该模型的算法表达能力，例如寻找强连通分量(StronglyConnected Components) 和近似最大权重匹配(ApproximateMaximum Weight Matching) 算法[58]就不适合用该模型执行。
图4.2以边为中心的编程模型示意图[81]
4.3以子图为中心
以子图为中心的模型相比于上述两种模型，是更加粗粒度的划分。它的优点是能够减少数据通信，并缓解负载不均衡的现象。例如，在针对幂律图时，以顶点为中心的模型需要将顶点和边划分到不同的机器上，从而导致负载不均衡。而以子图为中心的模型会将图划分为细粒度的子图，且相邻节点会存储在同一部分中以减少数据搬运和通信，提升图系统的性能，如图4.3所示。
然而，以子图为中心的模型在存储子图时会存在顶点和边的冗余信息，从而带来更高的本地处理开销。因此，仍需要通过数据和算法特性来选取模型。以子图为中心的模型适用于在子图上执行高效的顺序算法，且各个子图中的结果可以轻易地合并在一起，例如连通分量算法。另一方面，该模型依赖于子图划分的质量，如果各个子图间连接的边较少，则与其他模型相比，该模型可以有效减少图数据间的通信和收敛步数；但如果分区不佳，则性能并不会由于以顶点为中心的模型，因此，该模型可能面临着大量的预处理步骤。
图4.3以子图为中心的编程模型示意图[81]
未完待续，本系列文章的下一部分将详细介绍工业界研究和使用的图计算系统特点，并分析和总结这个方向的挑战及未来发展趋势
作者简介
胡静波，本科就读于西安电子科技大学，目前为清华大学电子工程系硕士生，专业为电子与通信工程，自2019年入学至今，一直跟随汪玉教授和戴国浩博士后进行大规模图计算方面的研究，且已经发表有关通用性图采样框架的论文一篇。
戴国浩，现清华大学电子工程系助理研究员、博士后，分别于2019年和2014年在清华大学电子工程系获得博士与学士学位。主要研究方向为大规模图计算、异构计算、存算一体、虚拟化等，曾获ASPDAC 2019最佳论文奖、DATE 2018最佳论文提名。
参考文献
[14]Shun JL, Blelloch GE, 2013. Ligra: a lightweightgraph processing framework for shared memory. ACM SIGPLAN Not, 48(8):135-146.
壁仞科技研究院作为壁仞科技的前沿研究部门，旨在研究新型智能计算系统的关键技术，重点关注新型架构，先进编译技术和设计方法学，并将逐渐拓展研究方向，探索未来智能系统的各种可能。壁仞科技研究院秉持开放的原则，将积极投入各类产学研合作并参与开源社区的建设，为相关领域的技术进步做出自己的贡献。