Hieroglyph: Locally-Sufficient Graph Processing via Compute-Sync-Merge

, and
Champaign-Urbana, USA,
Abstract. Despite their widespread adoption, large-scale graph processing systems do not fully decouple computation and communication, often yielding suboptimal performance. Locally-sufficient computation—computation that relies only on the graph state local to a computing host—can mitigate the effects of this coupling. In this paper, we present Compute-Sync-Merge (CSM), a new programming abstraction that achieves efficient locally-sufficient computation. CSM enforces local sufficiency at the programming abstraction level and enables the activation of vertex-centric computation on all vertex replicas, thus supporting vertex-cut partitioning. We demonstrate the simplicity of expressing several fundamental graph algorithms in CSM. Hieroglyph—our implementation of a graph processing system with CSM support—outperforms state of the art by up to 53x, with a median speedup of 3.5x and an average speedup of 6x across a wide range of datasets.
author = {Xiaoen and Ju and Hani and Jamjoom and Kang and Shin},
title = {{Hieroglyph: Locally-Sufficient Graph Processing via Compute-Sync-Merge}},
booktitle = {ACM SIGMETRICS},
address = {Champaign-Urbana, USA},
month = {June},
year = {2017}