Orchestrating parallel detection of strongly connected components on GPUs

Detecting strongly connected components (SCC) is a practical graph analytics algorithm widely used in many application domains. To accelerate SCC detection, parallel algorithms have been proposed and implemented on GPUs. However, existing GPU implementations show unstable performance for various graphs, especially for real-world graphs, as these implementations do not have a clear understanding of the graph properties. In this paper, we analyze that graphs in SCC detection usually exhibit (1) skewed component sizes (the static property) and (2) dynamically changed graph structure (the dynamic property). To deal with these irregular graph properties, we propose a hybrid method that divides the algorithm into two phases and exploits different levels of parallelism for different-sized components. We also customize the graph traversal strategies for each phase to handle the dynamically changed graph structure. Our method is carefully implemented to take advantage of the GPU hardware. Evaluation with diverse synthetic and real-world graphs shows that our method substantially improves existing GPU implementations, both performance-wise and applicability-wise. It also achieves an average speedup of 5.6 ×  and 1.5 ×  over the sequential and OpenMP implementations on the CPU respectively.