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

Displayed time zone: Pacific Time (US & Canada) change

06:20 - 07:40
PMEvo: Portable Inference of Port Mappings for Out-of-Order Processors by Evolutionary Optimization
PLDI Research Papers
Fabian Ritter Saarland University, Germany, Sebastian Hack Saarland University, Germany
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
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
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