Proceedings of the 2nd International Conference on Advances in Computer Science and Engineering (CSE 2013)

Task Level Parallelization of All Pair Shortest Path Algorithm in OpenMP 3.0

Authors
Eid Albalwi, Parimala Thulasiraman, Ruppa Thulasiram
Corresponding Author
Eid Albalwi
Available Online July 2013.
DOI
10.2991/cse.2013.26How to use a DOI?
Keywords
OpenMP 3.0; All Pair Shortest Path; Task Paral-lelization
Abstract

OpenMP is a standard parallel programming lan-guage to develop parallel applications on shared memory ma-chines. 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.

Copyright
© 2013, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

Volume Title
Proceedings of the 2nd International Conference on Advances in Computer Science and Engineering (CSE 2013)
Series
Advances in Intelligent Systems Research
Publication Date
July 2013
ISBN
978-90786-77-70-3
ISSN
1951-6851
DOI
10.2991/cse.2013.26How to use a DOI?
Copyright
© 2013, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

TY  - CONF
AU  - Eid Albalwi
AU  - Parimala Thulasiraman
AU  - Ruppa Thulasiram
PY  - 2013/07
DA  - 2013/07
TI  - Task Level Parallelization of All Pair Shortest Path Algorithm in OpenMP 3.0
BT  - Proceedings of the 2nd International Conference on Advances in Computer Science and Engineering (CSE 2013)
PB  - Atlantis Press
SP  - 111
EP  - 114
SN  - 1951-6851
UR  - https://doi.org/10.2991/cse.2013.26
DO  - 10.2991/cse.2013.26
ID  - Albalwi2013/07
ER  -