Parallelizing Sequential Graph Computations

Wenfei Fan, Wenyuan Yu, Jingbo Xu, Jingren Zhou, Xiaojian Luo, Qiang Yin, Yang Cao, Ruiqi Xu

Research output: Contribution to journalArticlepeer-review

Abstract

This paper presents GRAPE, a parallel GRAPh Engine for graph computations. GRAPE differs from prior systems in its ability to parallelize existing sequential graph algorithms as a whole, without the need for recasting the entire algorithms into a new model. Underlying GRAPE are a simple programming model, and a principled approach based on fixpoint computation that starts with partial evaluation and uses an incremental function as the intermediate consequence operator. We show that users can devise existing sequential graph algorithms with minor additions, and GRAPE parallelizes the computation. Under a monotonic condition, the GRAPE parallelization guarantees to converge at correct answers as long as the sequential algorithms are correct. Moreover, we show that algorithms in MapReduce, BSP and PRAM can be optimally simulated on GRAPE. In addition to the ease of programming, we experimentally verify that GRAPE achieves comparable performance to the state-of-the-art graph systems, using real-life and synthetic graphs.
Original languageEnglish
Article number38
Pages (from-to)38:1-38:41
Number of pages41
JournalACM Transactions on Database Systems
Publication statusAccepted/In press - 1 Oct 2018

Fingerprint Dive into the research topics of 'Parallelizing Sequential Graph Computations'. Together they form a unique fingerprint.

Cite this