Connected Components

Problem Description

A connected component of an undirected graph is a subgraph in which there is a path between any two nodes. A node with no edges is itself a connected component.

Algorithm

The application is developed using the pointer jumping algorithm for GPUs described in Soman et al.[1]. The CUDA code is generated using the IrGL compiler[2].

[1] "Fast GPU Algorithms for Graph Connectivity", Jyothish Soman, K. Kothapalli, and P. J. Narayanan, in Proc. of Large Scale Parallel Processing, IPDPS Workshops, 2010
[2] https://users.oden.utexas.edu/~sreepai/sree-oopsla2016.pdf

Performance

GraphTime (ms)
USA-road-d.FLA12
2d-2e2016

The above performance is observed on a 1733.500 Mhz GeForce GTX 1080 6000 with 8119 MB of main memory.