Scalable parallel algorithm for fast computation of Transitive Closure of Graphs on Shared Memory Architectures
- Resource Type
- Conference
- Authors
- Patel, Sarthak; Dave, Bhrugu; Kumbhani, Smit; Desai, Mihir; Kumar, Sidharth; Chaudhury, Bhaskar
- Source
- 2021 IEEE/ACM 6th International Workshop on Extreme Scale Programming Models and Middleware (ESPM2) ESPM2 Extreme Scale Programming Models and Middleware (ESPM2), 2021 IEEE/ACM 6th International Workshop on. :1-9 Nov, 2021
- Subject
- Computing and Processing
Processor scheduling
Instruction sets
Scalability
Memory architecture
Random access memory
Optimal scheduling
Programming
Graph Algorithms
OpenMP
Transitive Closure
Shared memory
- Language
We present a scalable algorithm that computes the transitive closure of a graph on shared memory architectures using the OpenMP API in C++. Two different parallelization strategies have been presented and the performance of the two algorithms has been compared for several data-sets of varying sizes. We demonstrate the scalability of the best parallel implementation up to 176 threads on a shared memory architecture, by producing a graph with more than 3.82 trillion edges. To the best of our knowledge, this is the first implementation that has computed the transitive closure of such a large graph on a shared memory system. Optimization strategies for better cache utilization for large data-sets have been discussed. The important issue of load balancing has been analyzed and its mitigation using the optimal OpenMP scheduling clause has been discussed in detail.