DAWN: Matrix Operation-Optimized Algorithm for Shortest Paths Problem on Unweighted Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916242184470528 |
|---|---|
| author | Feng, Yelai Wang, Huaixi Zhu, Yining Liu, Xiandong Lu, Hongyi Liu, Qing |
| author_facet | Feng, Yelai Wang, Huaixi Zhu, Yining Liu, Xiandong Lu, Hongyi Liu, Qing |
| contents | The shortest paths problem is a fundamental challenge in graph theory, with a broad range of potential applications. The algorithms based on matrix multiplication exhibits excellent parallelism and scalability, but is constrained by high memory consumption and algorithmic complexity. Traditional shortest paths algorithms are limited by priority queues, such as BFS and Dijkstra algorithm, making the improvement of their parallelism a focal issue. We propose a matrix operation-optimized algorithm, which offers improved parallelism, reduced time complexity, and lower memory consumption. The novel algorithm requires $O(E_{wcc}(i))$ and $O(S_{wcc} \cdot E_{wcc})$ times for single-source and all-pairs shortest paths problems, respectively, where $S_{wcc}$ and $E_{wcc}$ denote the number of nodes and edges included in the largest weakly connected component in graph. To evaluate the effectiveness of the novel algorithm, we tested it using graphs from SuiteSparse Matrix Collection and Gunrock benchmark dataset. Our algorithm outperformed the BFS implementations from Gunrock and GAP (the previous state-of-the-art solution), achieving an average speedup of 3.769$\times$ and 9.410$\times$, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_04514 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | DAWN: Matrix Operation-Optimized Algorithm for Shortest Paths Problem on Unweighted Graphs Feng, Yelai Wang, Huaixi Zhu, Yining Liu, Xiandong Lu, Hongyi Liu, Qing Distributed, Parallel, and Cluster Computing The shortest paths problem is a fundamental challenge in graph theory, with a broad range of potential applications. The algorithms based on matrix multiplication exhibits excellent parallelism and scalability, but is constrained by high memory consumption and algorithmic complexity. Traditional shortest paths algorithms are limited by priority queues, such as BFS and Dijkstra algorithm, making the improvement of their parallelism a focal issue. We propose a matrix operation-optimized algorithm, which offers improved parallelism, reduced time complexity, and lower memory consumption. The novel algorithm requires $O(E_{wcc}(i))$ and $O(S_{wcc} \cdot E_{wcc})$ times for single-source and all-pairs shortest paths problems, respectively, where $S_{wcc}$ and $E_{wcc}$ denote the number of nodes and edges included in the largest weakly connected component in graph. To evaluate the effectiveness of the novel algorithm, we tested it using graphs from SuiteSparse Matrix Collection and Gunrock benchmark dataset. Our algorithm outperformed the BFS implementations from Gunrock and GAP (the previous state-of-the-art solution), achieving an average speedup of 3.769$\times$ and 9.410$\times$, respectively. |
| title | DAWN: Matrix Operation-Optimized Algorithm for Shortest Paths Problem on Unweighted Graphs |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2208.04514 |