Papers › PASGAL: Parallel And Scalable Graph Algorithm Library
PASGAL: Parallel And Scalable Graph Algorithm Library
Xiaojun Dong, Yan Gu, Yihan Sun, Letong Wang
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections