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 language | English |
---|---|
Title of host publication | 2019 IEEE/ACM 9th Workshop on Irregular Applications: Architectures and Algorithms (IA3) |
Publisher | Association for Computing Machinery (ACM) |
Pages | 45-50 |
Number of pages | 6 |
ISBN (Electronic) | 978-1-7281-5987-4 |
ISBN (Print) | 978-1-7281-5988-1 |
DOIs | |
Publication status | Published - 30 Dec 2019 |
Event | 9th Workshop on Irregular Applications: Architectures and Algorithms - Denver, United States Duration: 18 Nov 2019 → 18 Nov 2019 https://hpc.pnl.gov/IA3/ |
Workshop
Workshop | 9th Workshop on Irregular Applications: Architectures and Algorithms |
---|---|
Abbreviated title | IA3 2019 |
Country/Territory | United States |
City | Denver |
Period | 18/11/19 → 18/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.Profiles
-
Mark Bull
- Computer Systems
- EPCC - Senior Research Fellow
Person: Academic: Research Active , Academic: Research Active (Research Assistant)