Fast load balance parallel graph analytics with an automatic graph data structure selection algorithm

Jiawen Sun*, Hans Vandierendonck, Dimitrios S. Nikolopoulos

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

This paper investigates the performance of graph-structured analytics on large-scale shared memory systems. Graph analytics are highly demanding for efficient graph traversal due to large data set size and irregular data access patterns. In order to achieve efficient graph analytics, we consider and discuss the performance of three common types of graph data structures. Also, we demonstrate that load balance is to a large extent determined by the number of edges and number of unique vertices processed by each thread. Finally, we propose an automatic graph data structure selection algorithm and an efficient reordering as a pre-processing step to balance the number of vertices and edges together. Reordering algorithm also optimally balances edges and vertices for graphs with a power-law degree distribution and ensures an equal degree distribution across threads. The developed techniques are implemented in GraphGrind, a new shared memory graph analytics framework. Evaluation in GraphGrind, shows that this outperforms state-of-the-art graph analytics frameworks for shared memory including Ligra (Shun and Blelloch, 2013) up to 10.4×, and Polymer (Zhang et al., 2015) up to 8.3× across 8 algorithms and 6 graphs.

Original languageEnglish
Pages (from-to)612-623
Number of pages12
JournalFuture Generation Computer Systems
Volume112
Early online date13 Jun 2020
DOIs
Publication statusEarly online date - 13 Jun 2020

Keywords

  • Graph analytics
  • Graph data structures
  • Graph partition
  • Graph reordering
  • Load imbalance
  • Shared memory systems

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Fast load balance parallel graph analytics with an automatic graph data structure selection algorithm'. Together they form a unique fingerprint.

  • Projects

    Cite this