PASGAL: Parallel And Scalable Graph Algorithm Library
Preprint
Abstract
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.Keywords
All Related Versions
- Version 1, 2024-04-26, ArXiv
- Published version: , 439.
This publication has 8 references indexed in Scilit:
- Brief Announcement: PASGAL: Parallel And Scalable Graph Algorithm Library2024
- Theoretically Efficient Parallel Graph Algorithms Can Be Fast and ScalableACM Transactions on Parallel Computing, 2021
- Reservoir computing compensates slow response of chemosensor arrays exposed to fast varying gas concentrations in continuous monitoringSensors and Actuators B: Chemical, 2015
- The Network Data Repository with Interactive Graph Analytics and VisualizationProceedings of the AAAI Conference on Artificial Intelligence, 2015
- Defining and evaluating network communities based on ground-truthKnowledge and Information Systems, 2013
- Comparing Community Structure to Characteristics in Online Collegiate Social NetworksSIAM Review, 2011
- Algorithm 447: efficient algorithms for graph manipulationCommunications of the ACM, 1973
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972