  In this paper, we introduce PASGAL (Parallel And Scalable Graph Algorithm
Library), a parallel graph library that scales to a variety of graph types,
many processors, and large graph sizes. One special focus of PASGAL is the
efficiency on \textit{large-diameter graphs}, which is a common challenge for
many existing parallel graph processing systems: many existing graph processing
systems can be even slower than the standard sequential algorithm on
large-diameter graphs due to the lack of parallelism. Such performance
degeneration is caused by the high overhead in scheduling and synchronizing
threads when traversing the graph in the breadth-first order.
  The core technique in PASGAL to achieve high parallelism is a technique
called \textit{vertical granularity control (VGC)} to hide synchronization
overhead, as well as careful redesign of parallel graph algorithms and data
structures. In our experiments, we compare PASGAL with state-of-the-art
parallel implementations on BFS, SCC, BCC, and SSSP. PASGAL achieves
competitive performance on small-diameter graphs compared to the parallel
baselines, and is significantly faster on large-diameter graphs.
