LaganLighter

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 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).

Publications


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

Naming
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.

Acknowledgement
– 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.
Plotly
Unsplash, Dean Machala, K. Mitch Hodge, and Michael Mahood