Write a Blog >>
PLDI 2020
Mon 15 - Fri 19 June 2020
Thu 18 Jun 2020 07:00 - 07:20 at PLDI Research Papers live stream - Performance Chair(s): Fredrik Kjolstad

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 Jun
Times are displayed in time zone: (GMT-07:00) Pacific Time (US & Canada) change

pldi-2020-papers
pldi-2020-papers06:20 - 06:40
Talk
Fabian RitterSaarland University, Germany, Sebastian HackSaarland University, Germany
pldi-2020-papers06:40 - 07:00
Talk
Zhenwei WuNational University of Defense Technology, China / University of Manchester, UK, Kai LuNational University of Defense Technology, China, Andrew NisbetUniversity of Manchester, UK, Wenzhe ZhangNational University of Defense Technology, China, Mikel LujánUniversity of Manchester, UK
pldi-2020-papers07:00 - 07:20
Talk
Youwei ZhuoUniversity of Southern California, USA, Jingji ChenUniversity of Southern California, USA, Qinyi LuoUniversity of Southern California, USA, Yanzhi WangNortheastern University, USA, Hailong YangBeihang University, China, Depei QianBeihang University, China, Xuehai QianUniversity of Southern California, USA
pldi-2020-papers07:20 - 07:40
Talk
Sotiris ApostolakisPrinceton University, USA, Ziyang XuPrinceton University, USA, Zujun TanPrinceton University, USA, Greg ChanPrinceton University, USA, Simone CampanoniNorthwestern University, USA, David I. AugustPrinceton University, USA
DOI Pre-print Media Attached