IIIT Hyderabad Publications |
|||||||||
|
Faster Parallel Graph Connectivity Algorithms for GPUAuthor: Mihir Wadwekar Date: 2019-11-14 Report no: IIIT/TH/2019/114 Advisor:Kishore Kothapalli AbstractFinding whether a graph is k-connected, and identifying its k-connected components is a fundamental problem in graph theory. For this reason, there have been several algorithm for this problem in both sequential and parallel settings. Several recent sequential and parallel algorithms for k-connectivity rely on one or more breadth-first traversals of the input graph. It can be also noticed that the time spent by the algorithms on BFS operations is usually a significant portion of the overall runtime of the algorithm. While BFS can be made very efficient in a sequential setting, the same cannot be said in the case of parallel environments. A major factor in this difficulty is due to the inherent requirement to use a shared a queue, balance work among multiple threads in every round, synchronization, and the like. Optimizing the execution of BFS on many current parallel architectures is therefore quite challenging. In this thesis, we present the first GPU algorithms and implementations for 2- and 3-connectivity. We improve upon them through the use of certificates to reduce the size of the input graph and provide the fastest implementations yet. We also study how one can, in the context of algorithms for graph connectivity, mitigate the practical inefficiency of BFS operations in parallel. Our technique suggests that such algorithms may not require a BFS of the input graph but actually can work with a sparse spanning subgraph of the input graph. The incorrectness introduced by not using a BFS spanning tree can then be offset by further post-processing steps on suitably defined small auxiliary graphs. We apply our technique to our GPU implementations for 2- and 3- connectivity and improve upon them further by a factor of 2.2x and 2.1x respectively Full thesis: pdf Centre for Security, Theory and Algorithms |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |