Abstract ：

A partition-based hybrid hierarchical graph computation approach, called H(2)Pregel is proposed to address the redundant supersteps and inefficient computation problems due to low access locality. The H(2)Pregel preprocesses the input graph through a distributed recode algorithm to ensure the continuity and sequence of vertex ids, then employs a hybrid approach to combine the advantages of both synchronous and asynchronous models, and hierarchically computes the high proportion of interior messages generated by high quality partition algorithms. Moreover, H(2)Pregel leverages configurable parallel threads to accelerate local computation by "sub-supersteps", and employs an exterior messages stealing optimization to avoid extra communication overheads between tasks. We implemented H(2)Pregel on Giraph, a classic open source system based on Pregel. The evaluation results on large-scale graphs show that, compared with Pregel in three partition algorithms, H(2)Pregel can achieve average speedups by 1.12-4.52 times and decrease average communication messages by 23.5%-55.5%, and average supersteps by 15.8%-82.0%. (C) 2019 Elsevier B.V. All rights reserved.

Keyword ：

BSP model Graph computing Hierarchical Hybrid computation

Cite：

Copy from the list or Export to your reference management。

Abstract ：

分布式图计算是目前处理大图数据的主流技术，其利用分布式计算分布并行处理的特点，通过将一个大规模图数据划分成若干子图，把针对一个大图数据的处理任务分解为若干针对子图数据的处理任务使其同步执行，从而显著提高对大规模图数据的处理能力。分布式图计算通常涉及复杂的处理过程，其主要面临以下的挑战：首先由于图的强耦合性使得难以将图划分成完全独立的子图以进行独立的并行处理，从而在分布式环境下执行图计算时需要进行大量的数据通信，制约了分布式图计算的整体性能；其次图计算通常是迭代执行的，特别是对于随时间演变的动态图，在不同时刻构造的图数据上重复执行图算法时，需要进行大量迭代计算，很难达到实时性要求。为此，本文首先提出了一种基于消息预测的方法来优化分布式图计算中频繁的数据通信，其次提出了两种优化动态图计算性能的方法，具体如下： 1. 针对分布式图计算中存在的大量数据通信，提出一种基于消息预测的性能优化方法。该优化方法在确保消息发送端和消息接收端采用相同消息预测方法的前提下，消息发送端在发送每条消息前，通常指输入图数据中的每个顶点向其邻居顶点发送消息前，调用基于历史消息的预测方法对该消息内容进行预测，如果预测成功，则不再发送消息，此时在消息接收端，对于相应的邻居顶点，相同的预测方法被调用以更新邻居顶点的值，从而通过消息预测取代消息传递减少了不必要的消息传递；否则，如果预测失败，则发送端发送消息的真实值与预测值的差值来纠正接收端的误预测，此时在消息接收端，通过整合预测的消息内容和收到的差值来更新顶点的值。为有效的预测消息内容，本文提出了两种基于历史消息的预测方法：基于记忆的预测方法和基于曲线拟合的预测方法，分别将其应用到不同的图算法中，包括：单源最短路径算法、 连通分支算法、 PageRank算法，图直径算法和随机游走算法。本文在现有的三个图计算平台Giraph、PowerGraph和PowerLyra上比较了算法原始实现和基于消息预测优化实现的计算性能，实验结果表明，优化后的算法具有较好的性能，其可以减少39%的通信开销，减少约27%的平均执行时间，同时保持最终误差率低于5%。 2. 针对分布式动态图计算中在新构造的图数据上执行计算时，由于工作节点之间的消息传递而导致的通信开销，提出一种应用于单源最短路径算法和PageRank算法的基于局部计算逼近全局计算的优化方法。在分布式计算环境下应用增量计算模型，即应用前一时刻图数据的计算结果作为在当前更新图数据上执行计算的初始值，在动态图上执行计算时，当新增加的数据流在前一时刻图数据Gt-1（在t-1时刻为止所观察到的所有顶点和边构成的图数据）上执行计算逐渐收敛的过程中到达时，该优化方法使在新构造的图数据Gt上执行的计算仅仅发生在位于本地工作节点的局部图数据上；对于本地工作节点和其他远程工作节点有数据依赖时，依据在Gt-1上执行计算时发送的历史消息进行预测；同时，为了使局部计算具有较高的准确率，本文提出一种贪心划分方法，当新增加的数据流到达时，依据新增加的顶点与已存在图数据Gt-1中顶点的连接关系，将新增的顶点划分到其邻居顶点最多的工作节点上。本文以具有不同规模的图数据集作为输入进行实验来评估该优化方法，实验结果表明，与传统的增量计算模型相比，局部逼近方法可以使SSSP算法的响应时间减少22%，使PageRank算法的响应时间减少7%。 3. 针对分布式动态图计算中在不同时刻的图数据上重复执行图算法而导致的大量迭代计算，提出一种应用于PageRank算法和K-means算法的基于初始值优化的计算模型。与传统的增量计算模型相比，其直接使用前一时刻图数据的计算结果作为在当前更新图数据上执行计算的初始值的，该优化模型在对当前更新的图数据执行计算之前，结合前一时刻图数据的计算结果和新输入的数据流来预测在当前图数据上执行计算的最优初始值，从而来加速图计算的收敛。本文设计了两种预测方法：一种基于历史信息的预测方法，该方法通过应用图数据Gt-1和Gt的计算结果的变化率来预测在图数据Gt和Gt+1上执行图算法时计算结果的变化率，从而使得在Gt+1上执行计算的初始值逼近最终收敛值；以及一种基于统计分析的预测方法，该方法通过计算新输入数据流的统计变量（如平均值）来分析其对前一时刻图数据Gt的计算结果可能产生的影响，从而来预测在新构造的图数据Gt+1上执行计算的最优初始值。本文设计并实现了基于初始值预测的PageRank以及K-means算法，实验表明，与传统的增量计算模型相比，采用初始值优化的增量计算模型在保证最终计算结果误差处于可容忍范围内的情况下，使PageRank算法的迭代次数减少30%，K-means算法的迭代次数减少13.7%，响应时间也相应的减少12.7%和10.6%。

Keyword ：

动态图计算 分布式计算 图计算 性能优化

Cite：

Copy from the list or Export to your reference management。

Abstract ：

近年来，随着社交网络等新型媒体的高速发展，信息的组织、传播方式正在发生新的变化，呈现出明显的动态化特征。目前针对动态图计算系统的研究，主要采用增量计算模型，其对图快照设置的初始值相较于传统的批量处理模型，更加逼近于最终结果，但设置方法较为粗糙，不能体现全局特征。本文研究的目标是优化快照初始值的设置方法，提供更高时效性的动态图处理。 首先，本文提出基于值预测的增量计算模型，即通过提取更新数据的特征，来优化增量计算模型在当前快照上设置的初始值，减少了算法执行时间。其次，基于所提出的模型，实现一种图计算系统PDGiraph，实现方法是为原始静态图计算系统Giraph增加文件系统监测、动态数据加载以及值预测器的功能模块，并为值预测器提供抽象的编程接口。然后，为了对PDGiraph系统进行应用评测，设计并实现了基于值预测的PageRank算法以及K-means算法：PageRank算法采用基于状态转移矩阵的值预测方法，需要借助历史状态信息；K-means算法采用基于统计学的值预测方法，利用更新数据的特征直接对当前簇质心进行偏移即可。最后，针对不同的算法，选取合适的具有时间属性的数据集，测试PDGiraph系统的实时性、准确性以及可扩展性，并对实验结果进行分析。 实验结果表明，基于值预测的动态图增量计算模型在保证最终计算结果误差处于可容忍范围内的情况下，减少了系统执行所需的时间延迟：其中，PageRank算法减少12.7%，K-means算法减少10.6%。可以看出，本文提出模型使得实时性得到提升，适合于对动态图处理效率要求高的应用。

Keyword ：

Giraph 大规模图计算 动态图 增量计算模型 值预测

Cite：

Copy from the list or Export to your reference management。

Abstract ：

随着大数据时代的兴起，挖掘大规模复杂关联数据的内在价值成为各行业的迫切需求，图作为一种能够有效表达事物间联系的数据结构，受到了广泛的关注。图数据除了具备传统大数据规模较大的特点外，还具有数据间耦合性强、数据局部性差且动态变化的特点，这些特点决定了其处理机制有别于传统的海量数据处理方法。图算法中频繁迭代的计算特点使得并行计算框架如MapReduce等难以满足图数据的分析需求，对现有图计算框架的处理能力提出了严峻挑战。因此，如何对现有图处理方法进行性能优化，减少计算时由于图数据和应用特点带来的冗余计算和频繁通信，成为当前大数据分析领域一个亟待解决的问题。本文针对图计算性能优化中存在的增量复用、中间消息I/O优化以及数据局部性与冗余迭代三个关键问题展开了深入的研究分析，并取得了如下主要创新成果?。 1）针对现有图计算方法多基于批处理方式，在增量更新场景下导致大量冗余计算和通信的问题，提出了一种增量式图计算方法IncPregel，该方法在预处理阶段使用宽度优先搜索对上传时图结构中的增量部分进行自动检测，找出原始图结构中增量对应的最大连通子图作为变化部分；在首轮作业的计算阶段将顶点的中间消息和计算结果作为可复用数据，并在后续作业计算前将未变化顶点细粒度的可复用数据通过各节点间混洗传输进行交换以方便任务进行本地复用，避免了原方法在每轮超级步中不变顶点带来的重复计算和冗余通信。基于该增量计算方法，在Pregel的开源版本Hama上进行了设计实现。测试结果表明，在边数据增量从0.1k-100k时，IncPregel相比Pregel，平均性能加速可达1.71-2.02倍，同时平均通信消息量减少75.1%-87.5%。 2）针对通信密集场景下，原静态最大消息阈值方法由于内存容量局限性导致的中间消息数据频繁低效I/O问题，给出了预计算模型，该模型利用图计算满足交换律和结合律的特点，将通信过程中收到的部分消息进行预计算以减轻磁盘I/O负载，并在正常计算时合并预计算结果，实现了通信和计算的重叠，达到提升作业响应时间的目的。在预计算模型基础上，提出了一种基于内存利用率的预计算方法MUP，根据当前的进程内存利用率判断是否进行预计算，并在预计算过程中使用细粒度锁以增大并发度；在分析MUP方法缺陷基础上，进一步提出了一种基于标志位映射机制的预计算方法MMP。MMP方法通过标志位映射机制增加了预计算时间，避免了预计算线程过多的问题，并对消息接收机制进行了优化以减少消息接收和存储等额外开销。实验结果表明，在通信密集场景下，MMP方法的性能优于MUP方法和原MMT方法。相比MMT方法，MUP方法平均性能加速为1.08-1.21倍，而MMP平均性能加速则为1.26-1.43倍，同时计算过程中任务平均磁盘I/O开销减少17.1%-20.9%。 3）针对现有图处理方法在图划分后数据局部性差，导致冗余超步和低效计算的问题，提出了一种基于分区的混合分层图计算方法H2Pregel，该方法在数据预处理阶段通过分布式重编码算法确保输入图的顶点Id连续且有序，在计算阶段将同步和异步模式相结合，对任务内部边执行基于“子超步”的局部计算以避免冗余超步和低效计算，同时针对不同划分算法下任务内部消息比例的差异性，通过可配置的子线程数将消息计算进一步分层并行，有效加速迭代，减少了任务间通信。基于该方法，在Pregel的开源版本Giraph上进行了设计实现。实验结果表明，在三种划分算法下，相比Pregel，H2Pregel的平均性能加速从1.19-4.94倍，同时任务间平均通信量减少范围为25.3%-55.4%，作业迭代次数平均减少25.0%-82.1%。

Keyword ：

大同步模型 混合计算 图计算 预计算 增量式计算

Cite：

Copy from the list or Export to your reference management。