Edinburgh Research Explorer

Adaptive Asynchronous Parallelization of Graph Algorithms

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

  • Wenfei Fan
  • Ping Lu
  • Xiaojian Luo
  • Jingbo Xu
  • Qiang Yin
  • Wenyuan Yu
  • Ruiqi Xu

Related Edinburgh Organisations

Open Access permissions

Open

Documents

https://dl.acm.org/citation.cfm?id=3196918
Original languageEnglish
Title of host publicationProceedings of the 2018 International Conference on Management of Data (SIGMOD'18)
Place of PublicationTexas, USA
PublisherACM
Pages1141-1156
Number of pages16
ISBN (Electronic)978-1-4503-4703-7
DOIs
Publication statusPublished - 27 May 2018
Event2018 ACM SIGMOD/PODS International Conference on Management of Data - Houston, United States
Duration: 10 Jun 201815 Jun 2018
https://sigmod2018.org/

Conference

Conference2018 ACM SIGMOD/PODS International Conference on Management of Data
Abbreviated titleSIGMOD'18
CountryUnited States
CityHouston
Period10/06/1815/06/18
Internet address

Abstract

This paper proposes an Adaptive Asynchronous Parallel (AAP) model for graph computations. As opposed to Bulk Synchronous Parallel (BSP) and Asynchronous Parallel (AP) models, AAP reduces both stragglers and stale computations by dynamically adjusting relative progress of workers. We show that BSP, AP and Stale Synchronous Parallel model (SSP) are special cases of AAP. Better yet, AAP optimizes parallel processing by adaptively switching among these models at different stages of a single execution. Moreover, employing the programming model of GRAPE, AAP aims to parallelize existing sequential algorithms based on fixpoint computation with partial and incremental evaluation. Under a monotone condition, AAP guarantees to converge at correct answers if the sequential algorithms are correct. Furthermore, we show that AAP can optimally simulate MapReduce, PRAM, BSP, AP and SSP. Using real-life and synthetic graphs, we experimentally verify that AAP outperforms BSP, AP and SSP for a variety of graph computations.

    Research areas

  • parallel model, parallelisation, graph computations, Church-Rosser

Event

2018 ACM SIGMOD/PODS International Conference on Management of Data

10/06/1815/06/18

Houston, United States

Event: Conference

Download statistics

No data available

ID: 64279519