Think Sequential, Run Parallel

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

doi:10.1007/978-3-030-01461-2_1

Think Sequential, Run Parallel

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

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 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	https://doi.org/10.1007/978-3-030-01461-2_1
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 → …

Access to Document

10.1007/978-3-030-01461-2_1

think sequential run parallelAccepted author manuscript, 487 KB

https://link.springer.com/chapter/10.1007%2F978-3-030-01461-2_1

GRACE-Resource Bounded Graph Query Answering
Fan, W. (Principal Investigator)
EU government bodies
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)
EPSRC
1/04/15 → 30/09/20
Project: Research

Cite this

Fan, W., Liu, M., Xu, R., Hou, L., Li, D., & Meng, Z. (2018). Think Sequential, Run Parallel. In Symposium on Real-Time and Hybrid Systems - Essays Dedicated to Professor Chaochen Zhou on the Occasion of His 80th Birthday (pp. 1-25). (Lecture Notes in Computer Science; Vol. 11180), (Theoretical Computer Science and General Issues; Vol. 11180). Springer. https://doi.org/10.1007/978-3-030-01461-2_1

@inproceedings{9ec29cd28fe64286a9617476a4e1d160,

title = "Think Sequential, Run Parallel",

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.",

author = "Wenfei Fan and Muyang Liu and Ruiqi Xu and Lei Hou and Dongze Li and Zizhong Meng",

year = "2018",

month = sep,

day = "29",

doi = "10.1007/978-3-030-01461-2_1",

language = "English",

isbn = "978-3-030-01460-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "1--25",

booktitle = "Symposium on Real-Time and Hybrid Systems - Essays Dedicated to Professor Chaochen Zhou on the Occasion of His 80th Birthday",

address = "United Kingdom",

note = "Symposium on Real-Time and Hybrid Systems - Essays Dedicated to Professor Chaochen Zhou on the Occasion of His 80th Birthday ; Conference date: 01-10-2017",

}

Fan, W, Liu, M, Xu, R, Hou, L, Li, D & Meng, Z 2018, Think Sequential, Run Parallel. in Symposium on Real-Time and Hybrid Systems - Essays Dedicated to Professor Chaochen Zhou on the Occasion of His 80th Birthday. Lecture Notes in Computer Science, vol. 11180, Theoretical Computer Science and General Issues, vol. 11180, Springer, Changsha, China, pp. 1-25, Symposium on Real-Time and Hybrid Systems - Essays Dedicated to Professor Chaochen Zhou on the Occasion of His 80th Birthday, Changsha, China, 1/10/17. https://doi.org/10.1007/978-3-030-01461-2_1

Think Sequential, Run Parallel. / Fan, Wenfei; Liu, Muyang; Xu, Ruiqi et al.
Symposium on Real-Time and Hybrid Systems - Essays Dedicated to Professor Chaochen Zhou on the Occasion of His 80th Birthday. Changsha, China: Springer, 2018. p. 1-25 (Lecture Notes in Computer Science; Vol. 11180), (Theoretical Computer Science and General Issues; Vol. 11180).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Think Sequential, Run Parallel

AU - Fan, Wenfei

AU - Liu, Muyang

AU - Xu, Ruiqi

AU - Hou, Lei

AU - Li, Dongze

AU - Meng, Zizhong

PY - 2018/9/29

Y1 - 2018/9/29

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-030-01461-2_1

DO - 10.1007/978-3-030-01461-2_1

M3 - Conference contribution

SN - 978-3-030-01460-5

T3 - Lecture Notes in Computer Science

SP - 1

EP - 25

BT - Symposium on Real-Time and Hybrid Systems - Essays Dedicated to Professor Chaochen Zhou on the Occasion of His 80th Birthday

PB - Springer

CY - Changsha, China

T2 - Symposium on Real-Time and Hybrid Systems - Essays Dedicated to Professor Chaochen Zhou on the Occasion of His 80th Birthday

Y2 - 1 October 2017

ER -

Think Sequential, Run Parallel

Abstract

Publication series

Conference

Access to Document

Fingerprint

Projects

GRACE-Resource Bounded Graph Query Answering

VADA: Value Added Data Systems: Principles and Architecture

Cite this