Projects per year
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 language | English |
---|---|
Title of host publication | Symposium on Real-Time and Hybrid Systems - Essays Dedicated to Professor Chaochen Zhou on the Occasion of His 80th Birthday |
Place of Publication | Changsha, China |
Publisher | Springer |
Pages | 1-25 |
Number of pages | 25 |
ISBN (Electronic) | 978-3-030-01461-2 |
ISBN (Print) | 978-3-030-01460-5 |
DOIs | |
Publication status | Published - 29 Sept 2018 |
Event | Symposium 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
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer, Cham |
Volume | 11180 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Name | Theoretical Computer Science and General Issues |
---|---|
Volume | 11180 |
Conference
Conference | Symposium on Real-Time and Hybrid Systems - Essays Dedicated to Professor Chaochen Zhou on the Occasion of His 80th Birthday |
---|---|
Country/Territory | China |
City | Changsha |
Period | 1/10/17 → … |
Fingerprint
Dive into the research topics of 'Think Sequential, Run Parallel'. Together they form a unique fingerprint.Projects
- 2 Finished
-
GRACE-Resource Bounded Graph Query Answering
Fan, W. (Principal Investigator)
1/11/15 → 31/10/21
Project: Research
-
VADA: Value Added Data Systems: Principles and Architecture
Libkin, L. (Principal Investigator), Buneman, P. (Co-investigator), Fan, W. (Co-investigator) & Pieris, A. (Co-investigator)
1/04/15 → 30/09/20
Project: Research