The International Conference for High Performance Computing, Networking, Storage, and Analysis
The International Conference for High Performance Computing, Networking, Storage, and Analysis
Workshop:ESPM2 2021: Sixth International Workshop on Extreme Scale Programming Models and Middleware
Authors: Sarthak Patel, Bhrugu Dave, Smit Kumbhani, and Mihir Desai (Dhirubhai Ambani Institute of Information and Communication Technology (DA-IICT), Group in Computational Science and HPC, India); Sidharth Kumar (University of Alabama, Birmingham); and Bhaskar Chaudhury (Dhirubhai Ambani Institute of Information and Communication Technology (DA-IICT), Group in Computational Science and HPC, India)
Abstract: 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 details.