EUVIMEDEUVIMED entdecken
Crossref

PowerLyra

Rong Chen, Jiaxin Shi, Yanzhe Chen, Binyu Zang, Haibing Guan, Haibo Chen

ACM Transactions on Parallel Computing · 30.09.2018 · 5 (3) · 1-39

DOI: 10.1145/3298989 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Parallel Computing, online erschienen am 22.01.2019. Verfasst von Rong Chen und 5 weiteren Autor:innen. Die Arbeit wurde bisher 121-mal zitiert (Crossref) und nennt 101 Literaturangaben. Gefördert von: National Natural Science Foundation of China, National Key Research 8 Development Program of China.

AbstractBibliografische AngabenZitieren

Abstract (Originalsprache)

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 and MLDM (Machine Learning and Data Mining) 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.

Förderung

  • National Natural Science Foundation of China
  • National Key Research 8 Development Program of China

Zitieren

APA

Chen, R., Shi, J., Chen, Y., Zang, B., Guan, H., & Chen, H. (2018). PowerLyra. ACM Transactions on Parallel Computing, 5(3), 1-39. https://doi.org/10.1145/3298989

Vancouver

Chen R, Shi J, Chen Y, Zang B, Guan H, Chen H. PowerLyra. ACM Transactions on Parallel Computing. 2018;5(3):1-39. doi:10.1145/3298989

BibTeX
@article{Chen2018,
  author = {Chen, Rong and Shi, Jiaxin and Chen, Yanzhe and Zang, Binyu and Guan, Haibing and Chen, Haibo},
  title = {PowerLyra},
  journal = {ACM Transactions on Parallel Computing},
  year = {2018},
  volume = {5},
  number = {3},
  pages = {1--39},
  doi = {10.1145/3298989}
}
Kostenlos starten →