Edinburgh Research Explorer

Think Sequential, Run Parallel

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

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

Related Edinburgh Organisations

Open Access permissions

Open

Documents

https://link.springer.com/chapter/10.1007%2F978-3-030-01461-2_1
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, Cham
Pages1-25
Number of pages25
ISBN (Electronic)978-3-030-01461-2
ISBN (Print)978-3-030-01460-5
DOIs
Publication statusPublished - 29 Sep 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 → …

Conference

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

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.

Download statistics

No data available

ID: 76854198