{"id":1615,"date":"2021-03-11T13:15:28","date_gmt":"2021-03-11T13:15:28","guid":{"rendered":"https:\/\/blogs.qub.ac.uk\/graphprocessing\/?page_id=243"},"modified":"2025-03-03T08:06:18","modified_gmt":"2025-03-03T08:06:18","slug":"laganlighter","status":"publish","type":"page","link":"https:\/\/blogs.qub.ac.uk\/dipsa\/laganlighter\/","title":{"rendered":"LaganLighter: Structure-Aware High-Performance Graph Algorithms"},"content":{"rendered":"\n

Project Statement<\/strong><\/h2>\n\n\n\n

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.<\/p>\n\n\n\n

Project Steps<\/strong><\/h2>\n\n\n\n

(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<\/a>’21<\/a> and ISPASS’21<\/a>).

(2) Introducing locality-optimizing graph algorithms: Hub Temporal Locality (HTL)<\/a> <\/strong>algorithm as a structure-aware and cache-friendly graph traversal (published in ICPP’21<\/a>) and <\/a>LOTUS<\/a><\/strong> algorithm that optimizes locality in Triangle Counting (published in PPoPP’22<\/a>).

(3) Introducing memory and work-optimizing algorithms: Thrifty Label Propagation<\/a><\/strong> that optimizes the Connected Components algorithm for power-law graph datasets (published in IEEE CLUSTER’21<\/a>), MASTIFF<\/a><\/strong> algorithm that optimizes work-efficiency in finding Minimum Spanning Tree\/Forest (published in ICS’22<\/a>), and SAPCo<\/a><\/strong> Sort<\/strong><\/a> that optimizes degree-ordering of power-law graphs (published in ISPASS’22<\/a>).<\/p>\n\n\n\n

(4) To demonstrate the dependency of performance on graph locality and computer architecture, we design performance model of graph algorithms. We apply this method to PoTra<\/strong><\/a>, our structure-aware graph transposition algorithm, illustrating how architectural characteristics can be leveraged to optimize performance.
<\/p>\n\n\n\n

Project Legacy<\/strong><\/h2>\n\n\n\n

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<\/strong><\/a> 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.<\/p>\n\n\n\n

Publications & Source Code<\/strong><\/h2>\n\n\n