GSoC 2018 - Parallel Implementations of Graph Analysis Algorithms

3 February 2019 | Soham Tamba

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:

  1. Producing parallel implementations of crucial graph algorithms.

  2. Improving sequential implementation of crucial graph algorithms in LightGraphs.

  3. 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.GraphVerticesEdges
1Twitter Social Circles81,3061,342,310
2Astro-Physics Collaboration17,903197,031
3Facebook Social Circles4,03988,234

The graphs were obtained from the SNAPDatasets repository.

Speed-up on parallelization with 4 cores

AlgorithmTwitterAstro-PhysicsFacebook
Breadth-First Search1.922.591.54
PageRank1.771.541.65
Bellman Ford SSSP--1.88
Floyd Warshall APSP--1.27
Johnson APSP--2.10
Randomized Heuristic1.881.701.66
Betweenness Centrality--1.96
Closeness Centrality--2.17
Stress Centrality--1.66

Speed-up on sequential optimization

AlgorithmTwitterAstro-PhysicsFacebook
PageRank3.053.373.17
Dijkstra SSSP2.802.101.68
Prim MST7.654.254.05
Kruskal MST7.703.372.80
AlgorithmTwitterAstro-PhysicsFacebook
Parallel7.071.200.26
Sequential13.633.110.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:

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.