This blog briefly summarises my GSoC 2018 project (Parallel Graph Development) and the results achieved. For a detailed description, please refer to my GSoC blog.
The project is spread over the LightGraphs codebase. It involved:
- Producing parallel implementations of crucial graph algorithms.
- Improving sequential implementation of crucial graph algorithms in LightGraphs.
- Implementing heuristics to obtain good solutions to crucial NP-Hard graph problems.
The benchmarks were conducted on a 64-bit linux machine using 4 cores.
Benchmark Graph Datasets:
| No. | Graph | Vertices | Edges |
|---|---|---|---|
| 1 | Twitter Social Circles | 81,306 | 1,342,310 |
| 2 | Astro-Physics Collaboration | 17,903 | 197,031 |
| 3 | Facebook Social Circles | 4,039 | 88,234 |
Speed-up on parallelization with 4 cores:
| Algorithm | Astro-Physics | ||
|---|---|---|---|
| Breadth-First Search | 1.92 | 2.59 | 1.54 |
| PageRank | 1.77 | 1.54 | 1.65 |
| Bellman Ford SSSP | - | - | 1.88 |
| Floyd Warshall APSP | - | - | 1.27 |
| Johnson APSP | - | - | 2.10 |
| Randomized Heuristic | 1.88 | 1.70 | 1.66 |
| Betweenness Centrality | - | - | 1.96 |
| Closeness Centrality | - | - | 2.17 |
| Stress Centrality | - | - | 1.66 |
Speed-up on sequential optimization:
| Algorithm | Astro-Physics | ||
|---|---|---|---|
| PageRank | 3.05 | 3.37 | 3.17 |
| Dijkstra SSSP | 2.80 | 2.10 | 1.68 |
| Prim MST | 7.65 | 4.25 | 4.05 |
| Kruskal MST | 7.70 | 3.37 | 2.80 |
Absolute runtime (in ms) of Bread-First Search:
| Algorithm | Astro-Physics | ||
|---|---|---|---|
| Parallel | 7.07 | 1.2 | 0.26 |
| Sequential | 13.63 | 3.11 | 0.41 |
Get the code
This section lists the functionality implemented and a link to the corresponding branch in my cloned LightGraphs repository.
Completed and merged
The following branches have been merged into LightGraphs master:
- Parallel Breadth-First Search
- Kruskal MST
- Sequential/Parallel Johnson APSP
- Parallel Floyd Warshall APSP
- Parallel Bellman Ford SSSP
- Parallel PageRank
- PageRank
- Load-balanced Partitioning
- Prim MST
- Dijkstra SSSP I
- Dijkstra SSSP II
- Greedy Heuristics
- Minimum Vertex Cover
- Minimum Dominating Set
- Maximum Independent Set
- Vertex Connectivity
- Parallel Random Heuristics
- Karger Minimum Cut
- Multi-threaded Centrality Measures
- Betweeness Centrality
- Closeness Centrality
- Stress Centrality
Completed but not applicable
The following branches have not been merged into LightGraphs master as the functionality is not suitable to LightGraphs:
Requires Improvement
The following branches have not been merged into LightGraphs as the parallel implementations are slower than the sequential implementation:
Acknowledgements
I would like to thank my mentor, Divyansh Srivastava and LightGraphs co-owner, Seth Bromberger for reviewing my code and providing valuable advice during the summer. I would also like to thank The Julia Project and NUMFocus for sponsoring my attendance to JuliaCon 2018.