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).
Project Legacy
The LaganLighter project shows that the different constituents of a network (graph) may expose different behaviours to analytic algorithms as a result of contrasting features and requirements. By exploiting these diverse behaviours and structural differences, we can accelerate the performance.
The Uniform Memory Demands Strategy concentrates on separating these constituents with contrasting needs and behaviours based on the degree of vertices. Similarly, other features of the skewed degree networks, or in other words, other perspectives on separating constituents of the network (such as connectivity that is used by Thrifty and MASTIFF algorithms) can be exploited to accelerate graph algorithms.
Publications & Source Code
- Random Vertex Relabelling in LaganLighter
- Minimum Spanning Forest of MS-BioGraphs
- Topology-Based Thread Affinity Setting (Thread Pinning) in OpenMP
- ParaGrapher Integrated to LaganLighter
- On Designing Structure-Aware High-Performance Graph Algorithms (PhD Thesis)
- LaganLighter Source Code
- MASTIFF: Structure-Aware Minimum Spanning Tree/Forest – ICS’22
- SAPCo Sort: Optimizing Degree-Ordering for Power-Law Graphs – ISPASS’22 (Poster)
- 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 (Poster)
Project Members
– Mohsen Koohi Esfahani
– Hans Vandierendonck
– Peter Kilpatrick
Grants and Funding
– PhD scholarship from The Department for the Economy, Northern Ireland and The Queen’s University Belfast (2019/10-2022/9)
– 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
Last update: Sep 13th, 2024