Task Level Parallelization of All Pair Shortest Path Algorithm in OpenMP 3.0
Eid Albalwi, Parimala Thulasiraman, Ruppa K. Thulasiram · 2013
OpenMP is a standard parallel programming language to develop parallel applications on shared memory machines.OpenMP is very suitable for designing parallel algorithms for regular applications where the amount of work is known apriori and therefore, distribution of work among the threads can be done at compile time.In irregular applications, the load changes dynamically at runtime and distribution of work among the threads can be done only at runtime.In the literature, it has been shown that OpenMP produces poor performance for irreg-ular applications.In 2008, the OpenMP 3.0 version introduced new features such as "tasks" to handle irregular computations.Not much work has gone into studying irregular algorithms in OpenMP 3.0.In this paper, we consider one graph problem, the all pair shortest path problem and its implementation in OpenMP 3.0.We show that for large number of vertices, the algorithm running on OpenMP 3.0 surpasses the one on OpenMP 2.5 by 1.6 times.