GraphU: A Unified Vertex-Centric Parallel Graph Processing Platform

Introduction

Many synchronous and asynchronous distributed platforms have been built for large-scale vertex-centric graph processing. Built on the Bulk Synchronous Parallel (BSP) model, the synchronous platforms iteratively perform vertex computations in a strict batch mode. In contrast, the asynchronous platforms enable more flexible vertex execution order and can usually result in better efficiency. Unfortunately, asynchronism also brings about an undesirable side effect: a program designed for a synchronous platform may not work properly on an asynchronous one. As a result, end users may be required to design different parallel algorithms for different platforms. Recently, we have proposed a unified programming model, DFA-G (Deterministic Finite Automaton for Graph processing), which expresses the computation at a vertex as a series of message-driven state transitions. It has the attractive property that any BSP program modeled after it can run properly across synchronous and asynchronous platforms.

In this demo, we first propose a complexity analysis framework for DFA-G automaton, which can significantly simplify complexity analysis on asynchronous programs. Due to the existing BSP platforms’ deficiency in supporting efficient DFA-G execution, we then develop a new propotype platform, GraphU. GraphU was built on the popular open-source Giraph project. But it entirely removes synchronization barriers and decouples remote communication from vertex computation. Finally, we conduct an empirical study to evaluate the performance of various DFA-G programs on GraphU. We also compare them with their alternatives on the existing BSP platforms. Our experiments validate the efficacy of the proposed automaton complexity analysis techniques and the efficiency of GraphU.

Architecture

Document

Video link

Source code