Analytics
CPU
Betweenness Centrality
Bipart
Breadth-first Search
Clustering
Connected Components
GMetis
Independent Set
k-Core
k-Truss
Max Cardinality Bipartite Matching
Matrix Completion
Minimum Spanning Tree
PageRank
Points-To Analysis
Preflow-Push
Single-Source Shortest Path
Triangle Counting
GPU
Breadth-First Search
Connected Components
Maximal Independent Set
Minimum Spanning Tree
Pagerank
Points-To Analysis
Single-Source Shortest Paths
Matrix Completion
Triangle Counting
Distributed
Betweenness Centrality
Breadth-first Search
Connected Components
k-Core
Matrix Completion
PageRank
Single-Source Shortest Path
Triangle Counting

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

Graph	Time (ms)
USA-road-d.FLA	12
2d-2e20	16

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