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.


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


GraphTime (ms)

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