  Computing strongly connected components (SCC) is a fundamental problems in
graph processing. As today's real-world graphs are getting larger and larger,
parallel SCC is increasingly important. SCC is challenging in the parallel
setting and is particularly hard on large-diameter graphs. Many existing
parallel SCC implementations can be even slower than Tarjan's sequential
algorithm on large-diameter graphs.
  To tackle this challenge, we propose an efficient parallel SCC implementation
using a new parallel reachability algorithm. Our solution is based on a novel
idea referred to as vertical granularity control (VGC). It breaks the
synchronization barriers to increase parallelism and hide scheduling overhead.
To use VGC in our SCC algorithm, we also design an efficient data structure
called the \emph{parallel hash bag}. It uses parallel dynamic resizing to avoid
redundant work in maintaining frontiers (vertices processed in a round).
  We implement the parallel SCC algorithm by Blelloch et al.\ (J.\ ACM, 2020)
using our new parallel reachability algorithm. We compare our implementation to
the state-of-the-art systems, including GBBS, iSpan, Multi-step, and our highly
optimized Tarjan's (sequential) algorithm, on 18 graphs, including social, web,
$k$-NN, and lattice graphs. On a machine with 96 cores, our implementation is
the fastest on 16 out of 18 graphs. On average (geometric means) over all
graphs, our SCC is 6.0$\times$ faster than the best previous parallel code
(GBBS), 12.8$\times$ faster than Tarjan's sequential algorithms, and
2.7$\times$ faster than the \emph{best existing implementation on each graph}.
  We believe that our techniques are of independent interest. We also apply our
parallel hash bag and VGC scheme to other graph problems, including
connectivity and least-element lists (LE-lists).

Distributed, Parallel, and Cluster Computing;Data Structures and Algorithms