Accelerating Graph Analytics by Utilising the Memory Locality of Graph Partitioning

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

6 Citations (Scopus)
355 Downloads (Pure)

Abstract

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
Pages181-190
Number of pages10
ISBN (Electronic)978-1-5386-1042-8
ISBN (Print)978-1-5386-1043-5
DOIs
Publication statusPublished - 07 Sep 2017
Event2017 International Conference on Parallel Programming - Bristol, United Kingdom
Duration: 14 Aug 201717 Aug 2017
https://icppconf.wordpress.com/

Publication series

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

Conference

Conference2017 International Conference on Parallel Programming
Abbreviated titleICPP
CountryUnited Kingdom
CityBristol
Period14/08/201717/08/2017
Internet address

Keywords

  • Graph Analytics
  • Graph Partitioning
  • Memory Locality
  • NUMA

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

  • Student Theses

    The GraphGrind Framework: Fast Graph Analytics on Large Shared-Memory Systems

    Author: Sun, J., 17 Apr 2018

    Supervisor: Vandierendonck, H. (Supervisor) & Nikolopoulos, D. (Supervisor)

    Student thesis: Doctoral ThesisDoctor of Philosophy

    File

    Cite this

    Sun, J., Vandierendonck, H., & Nikolopoulos, D. S. (2017). Accelerating Graph Analytics by Utilising the Memory Locality of Graph Partitioning. In ICPP2017: The 46th International Conference on Parallel Processing: Proceedings (pp. 181-190). (International Conference on Parallel Processing (ICPP): Proceedings). IEEE . https://doi.org/10.1109/ICPP.2017.27