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

6 Citations (Scopus)
582 Downloads (Pure)


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 publicationICPP2017: The 46th International Conference on Parallel Processing: Proceedings
Publisher IEEE
Number of pages10
ISBN (Electronic)978-1-5386-1042-8
ISBN (Print)978-1-5386-1043-5
Publication statusPublished - 07 Sep 2017
Event2017 International Conference on Parallel Programming - Bristol, United Kingdom
Duration: 14 Aug 201717 Aug 2017

Publication series

NameInternational Conference on Parallel Processing (ICPP): Proceedings
ISSN (Electronic)2332-5690


Conference2017 International Conference on Parallel Programming
Abbreviated titleICPP
Country/TerritoryUnited Kingdom
Internet address


  • Graph Analytics
  • Graph Partitioning
  • Memory Locality
  • NUMA


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