PASGAL: Parallel And Scalable Graph Algorithm Library
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929327923265536 |
|---|---|
| author | Dong, Xiaojun Gu, Yan Sun, Yihan Wang, Letong |
| author_facet | Dong, Xiaojun Gu, Yan Sun, Yihan Wang, Letong |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_17101 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | PASGAL: Parallel And Scalable Graph Algorithm Library Dong, Xiaojun Gu, Yan Sun, Yihan Wang, Letong Distributed, Parallel, and Cluster Computing Data Structures and Algorithms 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. |
| title | PASGAL: Parallel And Scalable Graph Algorithm Library |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.17101 |