SympleGraph: Distributed Graph Processing with Precise Loop-Carried Dependency Guarantee
Graph analytics is an important way to understand relationships in real-world applications. At the age of big data, graphs have grown to billions of edges. This motivates distributed graph processing. Graph processing frameworks ask programmers to specify graph computations in user-
defined functions (UDFs) of graph-oriented programming model. Due to the nature of distributed execution, current frameworks cannot precisely enforce the semantics of UDFs, leading to unnecessary computation and communication. In essence, there exists a gap between programming model and
runtime execution.
This paper proposes SympleGraph, a novel distributed graph processing framework that precisely enforces loop-carried dependency, i.e., when a condition is satisfied by
a neighbor, all following neighbors can be skipped. SympleGraph instruments the UDFs to express the loop-carried dependency, then the distributed execution framework enforces the precise semantics by performing dependency propagation dynamically. Enforcing loop-carried dependency requires the sequential processing of the neighbors of each vertex distributed in different nodes. Therefore, the major challenge is to enable sufficient parallelism to achieve high performance. We propose to use circulant scheduling in the framework to allow different machines to process disjoint
sets of edges/vertices in parallel while satisfying the sequential requirement. It achieves a good trade-off between precise semantics and parallelism. The significant speedups in most
graphs and algorithms indicate that the benefits of eliminating unnecessary computation and communication overshadow the reduced parallelism. Communication efficiency is further optimized by 1) selectively propagating dependency for large-degree vertices to increase net benefits; 2)
double buffering to hide communication latency. In a 16-node cluster, SympleGraph outperforms the state-of-the-art system Gemini and D-Galois on average by 1.42× and 3.30×, and up to 2.30× and 7.76×, respectively. The communication reduction compared to Gemini is 40.95% on average and up
to 67.48%.
Thu 18 JunDisplayed time zone: Pacific Time (US & Canada) change
06:20 - 07:40 | PerformancePLDI Research Papers at PLDI Research Papers live stream Chair(s): Fredrik Kjolstad Stanford University | ||
06:20 20mTalk | PMEvo: Portable Inference of Port Mappings for Out-of-Order Processors by Evolutionary Optimization PLDI Research Papers | ||
06:40 20mTalk | PMThreads: Persistent Memory Threads Harnessing Versioned Shadow Copies PLDI Research Papers Zhenwei Wu National University of Defense Technology, China / University of Manchester, UK, Kai Lu National University of Defense Technology, China, Andrew Nisbet University of Manchester, UK, Wenzhe Zhang National University of Defense Technology, China, Mikel Luján University of Manchester, UK | ||
07:00 20mTalk | SympleGraph: Distributed Graph Processing with Precise Loop-Carried Dependency Guarantee PLDI Research Papers Youwei Zhuo University of Southern California, USA, Jingji Chen University of Southern California, USA, Qinyi Luo University of Southern California, USA, Yanzhi Wang Northeastern University, USA, Hailong Yang Beihang University, China, Depei Qian Beihang University, China, Xuehai Qian University of Southern California, USA | ||
07:20 20mTalk | SCAF: A Speculation-Aware Collaborative Dependence Analysis Framework PLDI Research Papers Sotiris Apostolakis Princeton University, USA, Ziyang Xu Princeton University, USA, Zujun Tan Princeton University, USA, Greg Chan Princeton University, USA, Simone Campanoni Northwestern University, USA, David I. August Princeton University, USA DOI Pre-print Media Attached | ||