Project Statement
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.

Project Phases
(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).

Project Members
– 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 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