Xiaoen Ju, Hani Jamjoom and Kang Shin
ACM SIGMETRICS
Champaign-Urbana, USA, June 2017
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.
Bibtex.
@inproceedings{jamjoom-hieroglyph-sigmetrics-2017,
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}
}