IEEE Xplore (DOI: 10.1109/ISPASS51385.2021.00023)
ISPASS-2021
2021 IEEE International Symposium on Performance Analysis of Systems and Software
March 28-30, 2021

Authors’ Copy (PDF Format)

For a complete version of this article, please refer to Locality Analysis of Graph Reordering Algorithms and also Chapter 3 of the On Designing Structure-Aware High-Performance Graph Algorithms thesis.

Relabeling (reordering) algorithms aim to improve the poor memory locality of graph processing by changing the order of vertices. This paper analyses the functionality of three state-of-the-art relabeling algorithms: SlashBurn, GOrder, and Rabbit-Order for real-world graphs.

We use a number of techniques to explain how locality is affected by relabeling algorithms and how locality of different datasets (like social networks and web graphs) is enhanced by relabeling algorithms.

We use last level cache simulation to study miss rate degree distribution. We also use the degree distribution of Giant Connected Component (GCC) in SlashBurn iterations to see if real-world graphs follow the assumption that “power-law graphs are created/destroyed recursively” [SlashBurn]. We represent SlashBurn++ as an enhanced version of SlashBurn with lower preprocessing time and better locality.

Using cache simulation, we count the number of misses for accessing vertices data of high-degree vertices. This helps to explain how GOrder provides better temporal locality by managing cache space. Average ID Distance (AID) is a spatial locality metric introduced in this paper to explain how clustering relabeling algorithms like Rabbit-Order provide better spatial locality.

This paper also investigates why push and pull traversals of different datasets show different performances by introducing Push Locality and Pull Locality.

Code Availability
The source-code of LaganLighter is available on LaganLighter Repository.

BibTex

@INPROCEEDINGS{10.1109/ISPASS51385.2021.00023,
  author={Koohi Esfahani, Mohsen and Kilpatrick, Peter and Vandierendonck, Hans},
  booktitle={2021 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)}, 
  title={How Do Graph Relabeling Algorithms Improve Memory Locality?}, 
  year={2021},
  volume={},
  number={},
  pages={84-86},
  publisher={IEEE Computer Society},
  doi={10.1109/ISPASS51385.2021.00023}
}

ISPASS’21
ISPASS’21 Final Program
LaganLighter

Related Posts

• 
  ParaGrapher Integrated to LaganLighter16 February 2024
• 
  On Designing Structure-Aware High-Performance Graph Algorithms (PhD Thesis)8 December 2022
• 
  LaganLighter Source Code14 November 2022
• 
  MASTIFF: Structure-Aware Minimum Spanning Tree/Forest – ICS’2228 June 2022
• 
  SAPCo Sort: Optimizing Degree-Ordering for Power-Law Graphs – ISPASS’22 (Poster)23 May 2022
• 
  LOTUS: Locality Optimizing Triangle Counting – PPOPP’225 April 2022
• 
  Locality Analysis of Graph Reordering Algorithms – IISWC’218 November 2021
• 
  Thrifty Label Propagation: Fast Connected Components for Skewed-Degree Graphs – IEEE CLUSTER’219 September 2021
• 
  Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing – ICPP’219 August 2021
• 
  How Do Graph Relabeling Algorithms Improve Memory Locality? ISPASS’21 (Poster)28 March 2021