Scalable Parallel Algorithm for Fast Computation of Transitive Closure on Shared Memory Architectures
Cloud and Distributed Computing
Parallel Programming Languages and Models
Parallel Programming Systems
System Software and Runtime Systems
TimeMonday, 15 November 202110:30am - 11am CST
DescriptionWe 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 details.