2022 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS 2022)May 22-24, 2022 DOI: 10.1109/ISPASS55109.2022.00015 Authors’ Copy (PDF) While counting sort has a better complexity than comparison-based sorting algorithms, its parallelization suffers from high performance overhead and/or has a memory complexity that depends on the numbers of threads […]
graph relabeling
4 posts
2021 IEEE International Symposium on Workload Characterization (IISWC’21)November 7-9, 2021Acceptance Rate: 39.5%DOI: 10.1109/IISWC53511.2021.00020 Authors’ Copy (PDF Format) Graph reordering algorithms try to improve locality of graph algorithms by assigning new IDs to vertices that ultimately changes the order of random memory accesses. While graph relabeling algorithms such as SlashBurn, GOrder, […]
50th International Conference on Parallel Processing (ICPP’21)August 9-12, 2021Acceptance Rate: 26.4% DOI:10.1145/3472456.3472462ACM Digital LibraryPDF Version (Authors’ Copy) This paper investigates the implications made by the structure of real-world graphs with power-law degree distribution on the locality of SpMV graph analytics, and by considering the efficacy of locality optimizing graph reordering […]
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, web graphs) is enhanced by relabeling algorithms. This paper also investigates why different push and pull traversal of different datasets show different behaviours by introducing push locality and pull locality.