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 language | English |
---|---|
Title of host publication | Proceedings of the IEEE International Symposium on Workload Characterization, IISWC'21 |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
Pages | 101-112 |
Number of pages | 12 |
ISBN (Electronic) | 9781665441735 |
ISBN (Print) | 9781665441742 |
DOIs | |
Publication status | Published - 07 Nov 2021 |
Event | IEEE International Symposium on Workload Characterization - virtually, Storrs, United States Duration: 07 Nov 2021 → 09 Nov 2021 |
Conference
Conference | IEEE International Symposium on Workload Characterization |
---|---|
Abbreviated title | IISWC |
Country/Territory | United States |
City | Storrs |
Period | 07/11/2021 → 09/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.Student theses
-
On designing structure-aware high-performance graph algorithms
Koohi Esfahani, M. (Author), Vandierendonck, H. (Supervisor) & Kilpatrick, P. (Supervisor), Jul 2023Student thesis: Doctoral Thesis › Doctor of Philosophy
File