Think Sequential, Run Parallel

Wenfei Fan, Muyang Liu, Ruiqi Xu, Lei Hou, Dongze Li, Zizhong Meng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Parallel computation is often a must when processing large-scale graphs. However, it is nontrivial to write parallel graph algorithms with correctness guarantees. This paper presents the programming model of GRAPE , a parallel GRAPh Engine [19]. GRAPE allows users to “plug in” sequential (single-machine) graph algorithms as a whole, and it parallelizes the algorithms across a cluster of processors. In other words, it simplifies parallel programming for graph computations, from think parallel to think sequential. Under a monotonic condition, it guarantees to converge at correct answers as long as the sequential algorithms are correct. We present the foundation underlying GRAPE , based on simultaneous fixpoint computation. As examples, we demonstrate how GRAPE parallelizes our familiar sequential graph algorithms. Furthermore, we show that in addition to its programming simplicity, GRAPE achieves performance comparable to the state-of-the-art graph systems.
Original languageEnglish
Title of host publicationSymposium on Real-Time and Hybrid Systems - Essays Dedicated to Professor Chaochen Zhou on the Occasion of His 80th Birthday
Place of PublicationChangsha, China
PublisherSpringer
Pages1-25
Number of pages25
ISBN (Electronic)978-3-030-01461-2
ISBN (Print)978-3-030-01460-5
DOIs
Publication statusPublished - 29 Sept 2018
EventSymposium on Real-Time and Hybrid Systems - Essays Dedicated to Professor Chaochen Zhou on the Occasion of His 80th Birthday - Changsha, China
Duration: 1 Oct 2017 → …

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Cham
Volume11180
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameTheoretical Computer Science and General Issues
Volume11180

Conference

ConferenceSymposium on Real-Time and Hybrid Systems - Essays Dedicated to Professor Chaochen Zhou on the Occasion of His 80th Birthday
Country/TerritoryChina
CityChangsha
Period1/10/17 → …

Fingerprint

Dive into the research topics of 'Think Sequential, Run Parallel'. Together they form a unique fingerprint.

Cite this