PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs
PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs
复制标题
PowerLyra：倾斜图上的微分图计算和分区
DOI：
10.1145/3298989
复制
发表时间：
2018-01-01
影响因子：
1.6
通讯作者：
Chen, Haibo
中科院分区：
文献类型：
--
作者：
Chen, Rong;Shi, Jiaxin;Chen, Haibo
具有偏斜分布的自然图对分布式图计算和划分提出了独特的挑战。现有的图并行系统通常使用统一处理所有顶点的“一刀切”设计，其遭受显著的负载不平衡和对高度顶点的高度竞争（例如，Pregel和GraphLab），或者即使对于低度顶点（例如，PowerGraph和GraphX）。在这篇文章中，我们认为，自然图中的偏斜分布也需要对高度数和低度数顶点进行区分处理。然后，我们介绍PowerLyra，一个新的分布式图形处理系统，它包含了现有图形并行系统的两个世界中最好的。具体来说，PowerLyra对低度顶点使用集中式计算，以避免频繁的通信，并对高度顶点进行分布式计算，以平衡工作负载。PowerLyra还提供了一种有效的混合图划分算法（即，混合切割），其将边切割（对于低度数顶点）和顶点切割（对于高度数顶点）与图解法相结合。为了提高节点间图访问的缓存局部性，PowerLyra进一步提供了一种局部性敏感的数据布局优化。PowerLyra基于最新的GraphLab实现，可以无缝支持在同步和异步执行模式下运行的各种图形算法。使用各种图形分析和MLDM（机器学习和数据挖掘）应用程序对三个集群进行的详细评估显示，PowerLyra在真实世界和合成图中的性能分别比PowerGraph高出5.53倍（从1.24倍）和3.26倍（从1.49倍），并且比其他系统（如GraphX和GitHub）快得多，但内存消耗少得多。混合切割到GraphX的移植进一步证实了PowerLyra的效率和通用性。
Natural graphs with skewed distributions raise unique challenges to distributed graph computation and partitioning. Existing graph-parallel systems usually use a "one-size-fits-all" design that uniformly processes all vertices, which either suffer from notable load imbalance and high contention for high-degree vertices (e.g., Pregel and GraphLab) or incur high communication cost and memory consumption even for low-degree vertices (e.g., PowerGraph and GraphX). In this article, we argue that skewed distributions in natural graphs also necessitate differentiated processing on high-degree and low-degree vertices. We then introduce PowerLyra, a new distributed graph processing system that embraces the best of both worlds of existing graph-parallel systems. Specifically, PowerLyra uses centralized computation for low-degree vertices to avoid frequent communications and distributes the computation for high-degree vertices to balance workloads. PowerLyra further provides an efficient hybrid graph partitioning algorithm (i.e., hybrid-cut) that combines edge-cut (for low-degree vertices) and vertex-cut (for high-degree vertices) with heuristics. To improve cache locality of inter-node graph accesses, PowerLyra further provides a locality-conscious data layout optimization. PowerLyra is implemented based on the latest GraphLab and can seamlessly support various graph algorithms running in both synchronous and asynchronous execution modes. A detailed evaluation on three clusters using various graph-analytics andMLDM (Machine Learning and DataMining) applications shows that PowerLyra outperforms PowerGraph by up to 5.53X (from 1.24X) and 3.26X (from 1.49X) for real-world and synthetic graphs, respectively, and is much faster than other systems like GraphX and Giraph, yet with much less memory consumption. A porting of hybrid-cut to GraphX further confirms the efficiency and generality of PowerLyra.