External GPU Biconnected Components
摘要
As the scale of graph analytics continues to grow, many applications require identifying biconnected components (bccs) and cut vertices in graphs that exceed the memory capacity of a single gpu. This paper presents an out-of-core, gpu-based batch processing algorithm designed to efficiently compute bccs and cut vertices in massive graphs that do not fit entirely into device memory. We propose a novel batch technique to process the graph incrementally, and maintain a Biconnectivity Compressed Graph to compute bccs and cut vertices. Experimental results on a range of large-scale benchmark graphs demonstrate that our technique achieves competitive performance compared to state-of-the-art cpu solutions, enabling the handling of graph instances previously considered intractable on gpu platforms.