PASGAL: Parallel And Scalable Graph Algorithm Library
<|reference_start|>PASGAL: Parallel And Scalable Graph Algorithm Library: 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.<|reference_end|>
@article{dong2024pasgal:,
    title={PASGAL: Parallel And Scalable Graph Algorithm Library},
    author={Xiaojun Dong, Yan Gu, Yihan Sun, Letong Wang},
    journal={arXiv preprint arXiv:2404.17101},
    year={2024},
    doi={10.1145/3626183.3660258},
    archivePrefix={arXiv},
    eprint={2404.17101},
    primaryClass={cs.DC cs.DS}
}