We study the characteristics of graph datasets and their implications on the locality of graph analytics. In this way, we identify the connection between different vertex types and investigate how this connection affects the locality of memory accesses in different graph analytics and traversals. These patterns are used to propose new algorithms with enhanced performance for graph analytics.
(1) Analysing locality optimizing graph reordering algorithms and real-world graph datasets (published in IISWC’21 and ISPASS’21).
(2) Introducing the Hub Temporal Locality (HTL) algorithm as a structure-aware and cache-friendly graph traversal (published in ICPP’21).
(3) Introducing the Thrifty Label Propagation algorithm as the state-of-the-art connected components algorithm for power-law graph datasets (published in IEEE CLUSTER’21).
(4) Investigating the effects of real-world datasets on memory utilization of graph mining algorithms and introducing the LOTUS algorithm that optimizes locality in Triangle Counting (published in PPoPP’22).
- 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
– Prof. Hans Vandierendonck
– Prof. Peter Kilpatrick
– Mohsen Koohi Esfahani
Grants and Funding
– High Performance Computing center of the Queen’s University Belfast and the Kelvin supercomputer (EPSRC grant EP/T022175/1)
– DiPET (EPSRC grant EP/T022345/1)
– The Department for the Economy, Northern Ireland
– The Queen’s University Belfast
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), and James McGroarty (QUB) for supervising the Kelvin HPC centre, and Tony McHale and John Conway for managing the HPDC cluster.
– We thank Jordan McComb for SkyLakeX cache simulation system as his Master project.
– Unsplash, Dean Machala, K. Mitch Hodge, and Michael Mahood