arXiv:1612.01178v1 [cs.DC] 4 Dec 2016

Adaptive Work-Efficient Connected Components on
the GPU
Michael Sutton, Tal Ben-Nun, Amnon Barak

Sreepathi Pai, Keshav Pingali

Department of Computer Science
Hebrew University of Jerusalem
Jerusalem 91904, Israel
Email: {msutton,talbn}@cs.huji.ac.il

Institute for Computational Engineering and Sciences
The University of Texas at Austin
Austin, Texas, USA
Email: sreepai@ices.utexas.edu, pingali@cs.utexas.edu

Abstract—This report presents an adaptive work-efficient approach for implementing the Connected Components algorithm
on GPUs. The results show a considerable increase in performance (up to 6.8×) over current state-of-the-art solutions.

I. I NTRODUCTION
Finding the Connected Components (CC) of a graph is a
fundamental algorithm, often used as a pre-processing step for
other graph algorithms. Parallel CC algorithms exhibit finegrain parallelization opportunities, as have been explored in
the literature [1], [2]. In particular, two parallel approaches
are prominently used for CC, namely Label Propagation and
“Hook-Shortcut”. Soman et. al. [3] implemented a parallel
GPU variant of Hook-Shortcut, showing that GPUs are beneficial for CC computation despite the inherent irregularity of
the algorithm.
This report presents an adaptive variant of Hook-Shortcut
CC, focusing on the two core operations of the algorithm and
implementing them in a device-centric approach. By doing so,
we improve the work-efficiency of the algorithm, increase its
performance, and reduce CPU-GPU round-trips to minimum.
We demonstrate that the algorithm is highly efficient on a wide
variety of graph types.
II. E XISTING A PPROACHES
In graph theory, a connected component of an undirected
graph G = {V, E} is defined as a subset of vertices ν ⊆ V ,
in which each two vertices are connected via an edge path.
Computing the connected components {νi }N
i=1 of a graph,
where N is the number of components, is thus defined by
assigning a unique component ID Ci to each of the vertices
v ∈ νi . In practice, the component ID is determined by an
index of some representative vertex in ν.
Straightforward sequential solutions for CC are based on
graph traversal, propagating the unique component ID, called
label, via neighboring vertices until the entire component is
labeled. Label propagation can be parallelized by initializing
each vertex with a unique ID, disseminating vertex labels in
parallel according to a global rule, such as minimal/maximal
vertex index.
Shiloach and Vishkin [2] introduced a different parallel
algorithm for CC, based on two operations called “Hooking”
and “Shortcutting”. Rather than propagating values through

the graph, this variant transforms the input graph into trees,
iteratively connecting those trees and reducing their depth. The
algorithm converges when the graph is converted into a forest
of depth-one trees, each representing a different component.
Specifically, this variant defines two core procedures: (i) Hook,
which, given an edge (u, v) ∈ E, attempts to connect the two
trees that u and v belong to (if not already connected); and (ii)
Shortcut, which replaces the parent of each tree vertex with its
grand-parent, reducing the tree depth. The process alternates
between the Hook and Shortcut operations until convergence.
Soman et al. [3] propose a variant of the Hook-Shortcut
CC, where the Shortcut operation is replaced by Compression,
which consecutively performs Shortcutting (called “Jump”
operations in this variant) until each tree is reduced into
a single-level “star” (depth-one tree). Hence, the algorithm
iteratively alternates between Hook and Compress operations,
reducing the number of iterations until convergence.
procedure ConnectedComponents(G(V, E)):
1: let π : π(vertex) ← vertex
2: repeat
3:
for all e in E do in parallel
4:
Hook(e, π)
5:
end for
6:
repeat
7:
for all v in V do in parallel
8:
Jump(v, π)
9:
end for
10:
until Jump performs no change in π
11: until Hook performs no change in π
12: return π
Fig. 1: Hook-Compress Connected Components
Fig. 1 depicts the Hook-Compress implementation for
GPUs, proposed by Soman et al. [3]. The algorithm begins by
defining a workspace π for the component trees, initializing
each vertex to point to itself (line 1). Then, the algorithm
iteratively performs Hook rounds (lines 3-5) followed by
one or more Jump calls (lines 6-10), flattening the trees by

device procedure Hook(edge(u, v), π):
1: H ← max{π(u), π(v)}
2: L ← min{π(u), π(v)}
3: π(H) ← L
device procedure Jump(v, π):
1: π(v) ← π(π(v))

Fig. 2: Hook-Compress GPU Methods

iteratively assigning π(v) ← π(π(v)) for each v ∈ V .
The corresponding Hook-Compress GPU kernels are
presented in Fig. 2. As seen in the figure, although parallel
Hook calls may perform concurrent writes to the same memory
locations (Hook procedure, line 3), its implementation is
atomic-free (i.e., does not use atomic operations). This is
supported by the overall algorithm logic, which assures every
Hook operation will eventually succeed before converging.
The Hook procedure also uses a global high-to-low hooking
rule for avoiding possible tree cycles.
III. W ORK -E FFICIENT C ONNECTED C OMPONENTS
This section proposes a work-efficient approach for implementing Hook-Compress CC on the GPU. This approach
redefines the two core operations of the algorithm, Hook and
Compress, moving the control-flow to the GPU. We show that
the variant is scalable, minimizes CPU-GPU communication,
adaptive with respect to graph properties (e.g., average degree),
and converges faster than existing approaches. Below, we
describe the algorithm and elaborate on its work-efficiency
and adaptability properties.
A. Work-Efficiency
The proposed CC algorithm is composed of two GPU
kernels: Multi-Jump and Atomic-Hook.
In Multi-Jump, instead of performing multiple single-level
Jump operations, we fuse an entire Compress phase into a
single kernel. This kernel, shown in the bottom portion of
Fig. 3, replaces lines 6-10 in Fig. 1 with a single parallel
invocation.
We note two important optimizations in our Multi-Jump
procedure: (i) the procedure constantly writes an updated
value to π(v) even though one final write would suffice;
and (ii), the parallel kernel is scheduled with partial order,
starting from the top-most vertices in the component trees
(lower indices) and going down to the leaves (higher indices).
The two optimizations decrease the number of iterations each
device-thread must perform, hence reducing thread-divergence
introduced by the irregular while loop.
The second kernel is an Atomic-Hook procedure. This
kernel uses atomic Compare-And-Swap (CAS) operations to
traverse the component trees until a hook operation can

device procedure AtomicHook(edge(u, v), π):
1: while π(u) 6= π(v) do
2:
H ← max{π(u), π(v)}
3:
L ← min{π(u), π(v)}
4:
lock π(H)
. (atomic CAS)
5:
if π(H) = H : then
6:
π(H) ← L
7:
return
8:
else
9:
u ← π(H)
10:
v←L
11:
end if
12:
end lock
13: end while
device procedure MultiJump(v, π):
1: while π(π(v)) 6= π(v) do
2:
π(v) ← π(π(v))
3: end while
Fig. 3: Atomic-Hook and Multi-Jump Kernels

be verified to succeed, without overriding other concurrent
hook operations. This eliminates the need for the CPU-side
convergence loop in lines 2-11 of Fig. 1.
The Atomic-Hook procedure, depicted in the top portion
of Fig. 3, begins by finding the parents of both (u, v) and
determining their high-low order for global consensus (lines
1-3). Then, with an atomic CAS operation, π(H) is locked
and checked; if H is the root of a tree, then it can be used for
hooking the entire tree without overriding any other pointer,
hence the procedure assigns L to be its parent and exits
successfully (lines 5-7). Otherwise, the procedure recursively
considers (π(H), L) to be the new (u, v) edge to connect (lines
9-10) at the next iteration. The recursive logic continues until
successfully acquiring a root (line 5), or if discovering the two
component trees are already connected (line 1).
B. Adaptability
Using the above two kernels, one could possibly solve CC
with only two kernel calls: a single Atomic-Hook (guaranteeing component tree connectivity), followed by a Multi-Jump
operation for compressing all component trees into “stars”.
Performing a single Atomic-Hook may be more efficient
than several non-atomic Hooks, but it eliminates the ability to perform constant Compress operations between each
Hook round, which may degrade the overall performance.
For enabling intermediate tree compressions we introduce
segmentation, i.e. splitting the input graph into distinct edgelist segments and performing Compress operations between
atomic segment Hooks. Below we describe a heuristic method
for selecting the optimal number of edge-list segments to split
into.

procedure AdaptiveConnectedComponents(G(V, E)):
1: let π : π(vertex) ← vertex
2: let s ← 2|E|/|V |
. (average degree)
3: let {Ei }si=1 be s distinct subsets of E
4: for i ← 1, s do
5:
for all e in Ei do in parallel
6:
AtomicHook(e, π)
7:
end for
8:
for all v in V do in parallel
9:
M ultiJump(v, π)
10:
end for
11: end for
12: return π
Fig. 4: Adaptive Hook-Compress

TABLE I: Graph Properties
Name

Nodes

Edges

Avg.
Degree

Road Maps
24M
58M
2.41
174M
348M
2.00
Social Networks
5M
69M
14.23
Synthetic Graphs
2M
182M
86.82

usa-osm [4]
euro-osm-karls [5]
soc-live-journal [6]
kron-logn21 [7]

Soman

Multi-Jump

Atomic

Max
Degree

Size
(GB)

9
15

0.62
3.90

20,293

0.56

213,904

1.40

Adaptive

Runtime [ms]

1000

100

10

1

euro-osm-karls

usa-osm

kron-logn21

soc-live-journal

Fig. 5: Adaptive Connected Components Performance (lower
is better)

Adaptability. The figure shows that the adaptive version consistently outperforms the other versions. Observe that MultiJump improves performance in all graph types, whereas
Atomic-Hook exhibits improvement when adapting the number of segments based on the given input graph. For the best
segmentation, we achieve consistent speedups over the current
state-of-the-art [3] ranging from 4.15× to 6.76×.
Also note that for graphs like kron-logn21 and soc-livejournal [7], [6] which have a relatively high average degree,
the effect of the Multi-Jump optimization is minor (1.02×
and 1.14× respectively) because it only affects Compress
operations, which have a small O(|V |) complexity in these
cases.

kron-logn21

soc-live-journal

euro-osm-karls

7
6
5

Speedup

We highlight two observations, both related to the ratio
between the number of edges |E|, and the number of vertices
|V | (i.e. the average vertex degree) of the input graph.
First, atomic operations within the Atomic-Hook procedure
are performed on the component trees workspace, which has
|V | memory size. As a result, the true parallelism of atomic
operations is bounded by the number of vertices, creating a
growing atomic contention as average degree increases.
Second, unlike the Hook step, which has O(|E|) complexity,
the Compress step is performed over vertices and hence has
O(|V |) complexity. As the number of edges grows compared
to the number of vertices, the cost of Compress operations
becomes a minor percentage of the overall run-time cost, and
performing more intermediate compressions may be beneficial.
Based on these observations, we suggest a heuristic method
to determine the best segmentation, is to split the graph into
2|E|/|V | segments (the average degree), effectively performing Atomic-Hook operations over edge-list segments of size
≈ |V | each followed by a full O(|V |) Compress.
This way, Hook operations are always performed over
segments proportional to the |V | memory workspace, reducing
atomic contention. Each such segment Hook, is followed by
a Compress operation, flattening all component trees and
minimizing atomic operations for the next segment Hook. As
average degree increases, more Compress operations will be
performed, but their O(|V |) cost becomes minor compared to
the dominating O(|E|) complexity of the overall algorithm.

4
3
2
1

0

Fig. 4 shows the final host-side pseudocode for Adaptive
Connected Components.

1

6

11

16

21

26

31

36

41

46

51

56

61

66

71

76

81

86

91

96

Fig. 6: Segmentation Speedup
IV. P ERFORMANCE E VALUATION
Our experimental setup consists of an NVIDIA Tesla M60
(Maxwell architecture) GPU, containing 16 multiprocessors
with 128 cores each. We evaluated four graph instances of
different types, as listed in Table I.
Fig. 5 compares the baseline Soman [3] code with our
approach, gradually adding Multi-Jump, Atomic-Hook, and

Fig. 6 shows the segmentation speedup over the AtomicHook baseline (single segment) for various graphs on the average degree spectrum. For all tested graphs, the figure shows
that the speedup is maximal when segmenting into 2|E|/|V |
segments. These results coincide with the explanation behind
the adaptive heuristic, as described in Section III-B.

ACKNOWLEDGMENT
This research was supported by the German Research
Foundation (DFG) Priority Program 1648 “Software for exascale Computing” (SPP-EXA), research project FFMK; NSF
grants 1218568, 1337281, 1406355, and 1618425; by DARPA
BRASS contract 750-16-2-0004; and an equipment grant from
NVIDIA.
R EFERENCES
[1] B. Awerbuch and T. Singh, “New connectivity and MSF algorithms for ultracomputer and PRAM,” in International Conference on Parallel Processing, ICPP’83, 1983, pp. 175–179,
http://www.odysci.com/article/1010112986051047.
[2] Y. Shiloach and U. Vishkin, “An O(log n) parallel connectivity algorithm,” Journal of Algorithms, vol. 3, no. 1, pp. 57–67, 1982,
http://www.odysci.com/article/1010112982810234.
[3] J. Soman, K. Kothapalli, and P. J. Narayanan, “A fast GPU algorithm for graph connectivity,” in 24th IEEE International Symposium
on Parallel and Distributed Processing, IPDPS 2019, 2010, pp. 1–8,
http://www.odysci.com/article/1010112986704291.
[4] “9th DIMACS Implementation Challenge.” [Online]. Available: http:
//www.dis.uniroma1.it/challenge9/\download.shtml
[5] “Karlsruhe Institute of Technology, OSM Europe Graph,” 2014. [Online].
Available: http://i11www.iti.uni-karlsruhe.de/resou\rces/roadgraphs.php
[6] T. A. Davis and Y. Hu, “The university of florida sparse matrix collection,”
ACM Trans. Math. Softw., vol. 38, no. 1, pp. 1:1–1:25, 2011.
[7] D. A. Bader, H. Meyerhenke, P. Sanders, and D. Wagner, Eds., Graph
Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge Workshop, Georgia Institute of Technology, Atlanta, GA, USA,
February 13-14, 2012. Proceedings, ser. Contemporary Mathematics, vol.
588. American Mathematical Society, 2013.

