We study the characteristics of graph datasets and their implications on the memory utilization and memory locality of graph analytics. We identify the connection between different vertex classes in real-world graph datasets and we explore how these connections affect the performance of different graph analytics and traversals. These patterns are used to propose novel structure-aware graph analytic algorithms with optimized performance.
(1) Analysing the functionality of locality optimizing graph reordering algorithms for different real-world graph datasets by introducing new metrics and tools (published in IISWC’21 and ISPASS’21).
(2) Introducing locality optimizing graph algorithms: Hub Temporal Locality (HTL) algorithm as a structure-aware and cache-friendly graph traversal (published in ICPP’21), LOTUS algorithm that optimizes locality in Triangle Counting (published in PPoPP’22), and SAPCo Sort that optimizes degree-ordering of power-law graphs (published in ISPASS’22).
(3) Introducing memory and work optimizing algorithms: Thrifty Label Propagation that optimizes the Connected Components algorithm for power-law graph datasets (published in IEEE CLUSTER’21), MASTIFF algorithm that optimizes work efficiency in finding Minimum Spanning Tree/Forest (published in ICS’22).
- MASTIFF: Structure-Aware Minimum Spanning Tree/Forest – ICS’22
- SAPCo Sort: Optimizing Degree-Ordering for Power-Law Graphs – ISPASS’22 (Poster)
- LOTUS: Locality Optimizing Triangle Counting – PPOPP’22
- Locality Analysis of Graph Reordering Algorithms – IISWC’21
- Thrifty Label Propagation: Fast Connected Components for Skewed-Degree Graphs – IEEE CLUSTER’21
- Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing – ICPP’21
- How Do Graph Relabeling Algorithms Improve Memory Locality? ISPASS’21 (Poster)
Grants and Funding
– PhD scholarship from The Department for the Economy, Northern Ireland and The Queen’s University Belfast
– Kelvin-2 supercomputer (EPSRC grant EP/T022175/1)
– DiPET (CHIST-ERA-18-SDCDN-002, EPSRC grant EP/T022345/1)
The River Lagan is the main river in the Northern Ireland and Lighters have been light-weight barges used to transport industry materials. We named our project LaganLighter after the same goal: being nimble and sharp to carry out massive works.
– We thank Vaughan Purnell (QUB), Jose Sanchez Bornot (Ulster University), Luis Fernandez Menchero (QUB), and James McGroarty (QUB) for supervising the Kelvin HPC centre, and Tony McHale and John Conway for supervising the HPDC cluster.
– We thank Jordan McComb for SkyLakeX cache simulation system from his Master project.
– Unsplash, Dean Machala, K. Mitch Hodge, and Michael Mahood