Brief Announcement: PASGAL: Parallel And Scalable Graph Algorithm Library
Open Access
- 17 June 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 439-441
Abstract
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 graphs. One special focus of PASGAL is the efficiency onlarge-diameter graphs, which is a common challenge for many existing parallel graph processing systems due to the high overhead in synchronizing threads when traversing the graph in the breadth-first order. The core idea in PASGAL is a technique calledvertical granularity control (VGC) to hide synchronization overhead by careful algorithm redesign and new data structures. We compare PASGAL with existing parallel implementations on several fundamental graph problems. PASGAL is always competitive on small-diameter graphs, and is significantly faster on large-diameter graphs.Keywords
All Related Versions
Funding Information
- Google Research Scholar Program
- UCR Regents Faculty Fellowship
- National Science Foundation (CCF-2103483,CCF-2238358,CCF-2339310,IIS-2227669)
This publication has 10 references indexed in Scilit:
- Brief Announcement: PASGAL: Parallel And Scalable Graph Algorithm Library2024
- Parallel Strong Connectivity Based on Faster Reachability (Abstract)2023
- Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths2021
- Theoretically Efficient Parallel Graph Algorithms Can Be Fast and ScalableACM Transactions on Parallel Computing, 2021
- ParlayLib - A Toolkit for Parallel Algorithms on Shared-Memory Multicore Machines2020
- BFS and Coloring-Based Parallel Algorithms for Strongly Connected Components and Related Problems2014
- Direction-optimizing Breadth-First Search2012
- An Efficient Parallel Biconnectivity AlgorithmSIAM Journal on Computing, 1985
- Algorithm 447: efficient algorithms for graph manipulationCommunications of the ACM, 1973
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972