LaganLighter

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

Project Steps

(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) and LOTUS algorithm that optimizes locality in Triangle Counting (published in PPoPP’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), and SAPCo Sort that optimizes degree-ordering of power-law graphs (published in ISPASS’22).

Publications & Source Code


Project Members
Prof. Hans Vandierendonck
Prof. Peter Kilpatrick
Mohsen Koohi Esfahani

Grants and Funding
– PhD scholarship from The Department for the Economy, Northern Ireland and The Queen’s University Belfast (10/2019-9/2022)
– Kelvin-2 supercomputer (EPSRC grant EP/T022175/1)
– DiPET (CHIST-ERA-18-SDCDN-002, EPSRC grant EP/T022345/1)

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