Abstract:
We present an iterative breadth-first approach to maximum clique enumeration on the GPU. The memory required to store all of the intermediate clique candidates poses a si...Show MoreMetadata
Abstract:
We present an iterative breadth-first approach to maximum clique enumeration on the GPU. The memory required to store all of the intermediate clique candidates poses a significant challenge. To mitigate this issue, we employ a variety of strategies to prune away non-maximum candidates and present a thorough examination of the performance and memory benefits of each of these options. We also explore a windowing strategy as a middle-ground between breadth-first and depth-first approaches, and investigate the resulting tradeoff between parallel efficiency and memory usage. Our results demonstrate that when we are able to manage the memory requirements, our approach achieves high throughput for large graphs indicating this approach is a good choice for GPU performance. We demonstrate an average speedup of 1. 9x over previous parallel work, and obtain our best performance on graphs with low average degree.
Published in: 2023 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)
Date of Conference: 15-19 May 2023
Date Added to IEEE Xplore: 04 August 2023
ISBN Information: