Accelerating Graph Analytics by Utilising the Memory Locality of Graph Partitioning

Jiawen Sun, Hans Vandierendonck, Dimitrios S. Nikolopoulos

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

Abstract / Description of output

This paper investigates how to improve the memory locality of graph-structured analytics on large-scale shared memory systems. We demonstrate that a graph partitioning where all in-edges for a vertex are placed in the same partition improves memory locality. However, realising performance improvement through such graph partitioning poses several challenges and requires rethinking the classification of graph algorithms and preferred data structures. We introduce the notion of medium dense frontiers, a type of frontier that is sufficiently dense for a bitmap representation, yet benefits from an indexed graph layout. Using three types of frontiers, and three graph layout schemes optimized to each frontier type, we design an edge traversal algorithm that autonomously decides which type to use. The distinction of forward vs. backward graph traversal folds into this decision and need no longer be specified by the programmer.We have implemented our techniques in a NUMA-aware graph analytics framework derived from Ligra and demonstrate a speedup of up to 4.34× over Ligra and up to 2.93× over Polymer.
Original languageEnglish
Title of host publicationParallel Processing (ICPP), 2017 46th International Conference on. IEEE, 2017.
Place of PublicationBristol, UK
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages181-190
Number of pages10
ISBN (Electronic)978-1-5386-1042-8
ISBN (Print)978-1-5386-1043-5
DOIs
Publication statusPublished - 7 Sept 2017
Event46th International Conference on Parallel Processing - Bristol, United Kingdom
Duration: 14 Aug 201717 Aug 2017
http://www.icpp-conf.org/2017/

Publication series

Name
PublisherIEEE
ISSN (Electronic)2332-5690

Conference

Conference46th International Conference on Parallel Processing
Abbreviated titleICPP-2017
Country/TerritoryUnited Kingdom
CityBristol
Period14/08/1717/08/17
Internet address

Fingerprint

Dive into the research topics of 'Accelerating Graph Analytics by Utilising the Memory Locality of Graph Partitioning'. Together they form a unique fingerprint.

Cite this