iPregel: Strategies to Deal with an Extreme Form of Irregularity in Vertex-Centric Graph Processing

Ludovic Capelli, Nicholas Brown, Jonathan Bull

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

Abstract

Over the last decade, the vertex-centric programming model has attracted significant attention in the world of graph processing, resulting in the emergence of a number of vertex-centric frameworks. Its simple programming interface, where computation is expressed from a vertex point of view, offers both ease of programming to the user and inherent parallelism for the underlying framework to leverage. However, vertex-centric programs represent an extreme form of irregularity, both inter and intra core. This is because they exhibit a variety of challenges from a workload that may greatly vary across supersteps, through fine-grain synchronisations, to memory accesses that are unpredictable both in terms of quantity and location. In this paper, we explore three optimisations which address these irregular challenges; a hybrid combiner carefully coupling lock-free and lock-based combinations, the partial externalisation of vertex structures to improve locality and the shift to an edge-centric representation of the workload. We also assess the suitability of more traditional optimisations such as dynamic load-balancing and software prefetching. The optimisations were integrated into the iPregel vertex-centric framework, enabling the evaluation of each optimisation in the context of graph processing across three general purpose benchmarks common in the vertex-centric community, each run on four publicly available graphs covering all orders of magnitude from a million to a billion edges. The result of this work is a set of techniques which we believe not only provide a significant performance improvement in vertex-centric graph processing, but are also applicable more generally to irregular applications.
Original languageEnglish
Title of host publication2019 IEEE/ACM 9th Workshop on Irregular Applications: Architectures and Algorithms (IA3)
PublisherAssociation for Computing Machinery (ACM)
Pages45-50
Number of pages6
ISBN (Electronic)978-1-7281-5987-4
ISBN (Print)978-1-7281-5988-1
DOIs
Publication statusPublished - 30 Dec 2019
Event9th Workshop on Irregular Applications: Architectures and Algorithms - Denver, United States
Duration: 18 Nov 201918 Nov 2019
https://hpc.pnl.gov/IA3/

Workshop

Workshop9th Workshop on Irregular Applications: Architectures and Algorithms
Abbreviated titleIA3 2019
Country/TerritoryUnited States
CityDenver
Period18/11/1918/11/19
Internet address

Keywords / Materials (for Non-textual outputs)

  • vertex-centric
  • hybrid combiner
  • tructure externalisation
  • edge-centric workload
  • load-balancing
  • cache efficiency

Fingerprint

Dive into the research topics of 'iPregel: Strategies to Deal with an Extreme Form of Irregularity in Vertex-Centric Graph Processing'. Together they form a unique fingerprint.

Cite this