Locality analysis of graph reordering algorithms

Mohsen Koohi Esfahani, Peter Kilpatrick, Hans Vandierendonck

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

8 Citations (Scopus)
19 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationProceedings of the IEEE International Symposium on Workload Characterization, IISWC'21
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages101-112
Number of pages12
ISBN (Electronic)9781665441735
ISBN (Print)9781665441742
DOIs
Publication statusPublished - 07 Nov 2021
EventIEEE International Symposium on Workload Characterization - virtually, Storrs, United States
Duration: 07 Nov 202109 Nov 2021

Conference

ConferenceIEEE International Symposium on Workload Characterization
Abbreviated titleIISWC
Country/TerritoryUnited States
CityStorrs
Period07/11/202109/11/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