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, […]
Mohsen Koohi Esfahani
34 posts
IEEE CLUSTER 20217-10 SeptemberAcceptance rate: 29.4% DOI: 10.1109/Cluster48925.2021.00042IEEE XplorePDF Version (Authors’ Copy) Thrifty introduces four optimization techniques to Label Propagation Connected Components: 1) Unified Labels Array accelerates label propagation by allowing the latest label of each vertex to be read in processing other vertices. 2) Zero Convergence optimizes work-efficiency in […]
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.