Edinburgh Research Explorer

From Think Parallel to Think Sequential

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Open Access permissions

Open

Documents

  • Download as Adobe PDF

    Accepted author manuscript, 604 KB, PDF-document

    Licence: Creative Commons: Attribution Non-Commercial (CC-BY-NC)

https://sigmodrecord.org/2018/08/09/from-think-parallel-to-think-sequential-2/
Original languageEnglish
Pages (from-to)15-22
Number of pages8
JournalACM SIGMOD Record
Volume47
Issue number1
DOIs
Publication statusPublished - 10 Sep 2018

Abstract

This paper presents GRAPE, a parallel GRAPh Engine for graph computations. GRAPE differs from previous graph systems in its ability to parallelize existing sequential graph algorithms as a whole, without the need for recasting the entire algorithms into a new model. Underlying GRAPE are a simple programming model, and a principled approach based on fixpoint computation with partial evaluation and incremental computation. Under a monotonic condition, GRAPE guarantees to converge at correct answers as long as the sequential algorithms are correct. We show how our familiar sequential graph algorithms can be parallelized by GRAPE. In addition to the ease of programming, we experimentally verify that GRAPE achieves comparable performance to the state-of-the-art graph systems, using real-life and synthetic graphs.

Download statistics

No data available

ID: 70342077