Locality Analysis of Graph Reordering Algorithms

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

Abstract

A major challenge in processing real-world graphs stems from poor locality of memory accesses and vertex reordering algorithms (RAs) have been proposed to improve locality by changing the order of memory accesses.

While state-of-the-art RAs like SlashBurn, GOrder, and Rabbit-Order effectively speed up graph algorithms, their capabilities and disadvantages are not fully understood, mainly, for three reasons: (1) the large size of datasets, (2) the lack of suitable measurement tools, and (3) disparate characteristics of graphs. The paucity of analysis has also inhibited the design of more efficient RAs.

This paper unlocks this black box by introducing a number of tools, including: (1) a cache simulation technique for processing large graphs, (2) the Neighbour to Neighbour Average ID Distance (N2N AID) as a spatial locality metric, (3) the degree distributions of simulated cache miss rate and AID to investigate how locality of different vertices is affected by RAs, and (4) Effective Cache Size to measure how much of cache capacity is used to support random accesses.

We introduce (1) asymmetricity degree distribution, (2) degree range decomposition, and (3) push and pull locality to present a structural analysis of different types of real-world graphs by explaining their contrasting behaviours in confronting RAs.

Finally, we propose a number of improvements for RAs using the analysis provided in this paper.

https://blogs.qub.ac.uk/GraphProcessing/Locality-Analysis-of-Graph-Reordering-Algorithms/
Original languageEnglish
Title of host publication2021 IEEE International Symposium on Workload Characterization (IISWC'21)
PublisherIEEE Computer Society
Number of pages12
Publication statusPublished - 08 Nov 2021

Keywords

  • High performance computing (HPC)
  • Graph Processing
  • Graph reordering
  • Memory Locality

Fingerprint

Dive into the research topics of 'Locality Analysis of Graph Reordering Algorithms'. Together they form a unique fingerprint.

Cite this