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 ISPASS’21, and IISWC’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).
– Prof. Hans Vandierendonck
– Prof. Peter Kilpatrick
– Mohsen Koohi Esfahani
- 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
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 Jordan McComb for SkyLakeX cache simulation system as his Master project.
– We thank Tony McHale and John Conway for managing the HPDC cluster, and Vaughan Purnell and James McGroarty for supervising the Kelvin HPC centre.
– Unsplash, Dean Machala, K. Mitch Hodge, and Michael Mahood