SympleGraph: distributed graph processing with precise loop-carried dependency guarantee
| Autor: | Youwei Zhuo, Hailong Yang, Xuehai Qian, Qinyi Luo, Depei Qian, Jingji Chen, Yanzhi Wang |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Theoretical computer science
Computer science business.industry Computation Multiple buffering Big data 020207 software engineering 02 engineering and technology Disjoint sets computer.software_genre Vertex (geometry) 020204 information systems 0202 electrical engineering electronic engineering information engineering Programming paradigm Compiler business computer Circulant matrix |
| Zdroj: | PLDI |
| DOI: | 10.1145/3385412.3385961 |
| Popis: | 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%. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|