Improved Computing Performance for Floyd-Warshall Algorithm in the MapReduce architectures
Keywords:
shortest path, graph, algorithm, hadoop, mapreduceAbstract
The main result of this paper is building a new parallel algorithm based on Floyd-Warshall algorithm to find the Shortest Path for all-pair. The problem of finding All Pair Shortest Path (APSP). APSP is performed on many structures such as: MPI, OpenMP, Cuda and others. When the input data is large, we need to find ways to improve computing power to reduce calculation time for the APSP algorithm. We present a contribution for the APSP in the MapReduce architectures. The idea of this algorithm is to multi Workers to work in parallel by Floyd-Warshall algorithm. There is one Master assigning Map and Reduce. The mapper simultaneously executes their work and sends their data to the reducer until the job is finished. The MapReduce algorithm has two functions: Map and Reduce. They receive key/value pairs based on an adjacency list. The algorithm performs in MapReduce and our results prove that the proposed approach improved Computing Performance for Algorithm Finding the Shortest Path for all-pair. Some fundamental results are systematized and proved.
References
S. H. Roosta, Paralell Processing and Parallel Algorithm Theory and Computation, Springer, 2000, 347 p.
N. D. Lau, T. Q. Chien, L. M. Thanh, “Improved computing performance for algorithm finding the shortest path in extended graph,” Proceedings of the International Conference on Foundations of Computer Science (FCS’14), USA, 2014, pp. 14-20.
V. Dragomir, “All-pair shortest path modified matrix multiplication based algorithm for a one-chip MapReduce architecture,” U.P.B. Sci. Bull., Series C, 78, 4, pp. 95-108, 2016.
V. Dragomir, G. M. Ştefan, “All-pair shortest path on a hybrid Map-Reduce based architecture,” Proceedings of the Romanian Academy, Series A, the publishing House of the Romanian Academy, vol.20, no. 4, pp. 411–417, 2019.
S. Aridhi, V. Benjamin, P. Lacomme, L. Ren, “Shortest path resolutionusing hadoop,” MOSIM’14, Nancy – France, 2014.
W.Y.H. Adoni, T. Nahhal, B. Aghezzaf, A. Elbyed, “The MapReduce based approach to improve the shortest path computation in large scale road networks: the case of A* algorithm,” Journal of Big Data, vol. 5, p. 16, 2018. https://doi.org/10.1186/s40537-018-0125-8.
W.Y.H. Adoni, T. Nahhal, B. Aghezzaf, A. Elbyed, “MRA*: Parallel and distributed path in large-scale graph using MapReduce-A* based approach,” In: Sabir, E., García Armada, A., Ghogho, M., Debbah, M. (eds) Ubiquitous Networking. UNet 2017. Lecture Notes in Computer Science, vol 10542, 2027. Springer, Cham. https://doi.org/10.1007/978-3-319-68179-5_34.
S. Aridhi, P. Lacomme, L. Ren, B. Vincent, “A MapReduce-based approach for shortest path problem in large-scale networks,” Journal of Engineering Applications of Artificial Intelligence, vol. 41, pp. 151–165, 2015. https://doi.org/10.1016/j.engappai.2015.02.008.
Apache Hadoop, Welcome to Apache Hadoop. [Online]. Available at: http://hadoop.apache.org/
S. Ghemawat, H. Gobioff, S.T. Leung, “The Google file system,” ACM SIGOPS Operating Systems Review, vol. 37. New York: ACM; 2003. p. 29–43, 2003. https://doi.org/10.1145/1165389.945450.
J. Dean, S. Ghemawat, “MapReduce: simplified data processing on large clusters,” Commun ACM, vol. 51, issue 1, pp. 107–13, 2018. https://doi.org/10.1145/1327452.1327492.
V.K. Vavilapalli, Sю Seth, Bю Saha, C. Curino, O. O’Malley, S. Radia, B. Reed, E. Baldeschwieler, A.C. Murthy, C. Douglas, S. Agarwal, M. Konar, R. Evans, T. Graves, J. Lowe, H. Shah, “Apache Hadoop YARN: yet another resource negotiator,” Proceedings of the 4th ACM Annual Symposium on Cloud Computing, Santa Clara: 2013, pp. 1– 16. https://doi.org/10.1145/2523616.2523633.
M. Hena, N. Jeyanthi, A Three-Tier, “Authentication scheme for kerberized Hadoop environment,” Cybernetics and Information Technologies, vol. 21, no. 4, pp. 119-136, 2021. https://doi.org/10.2478/cait-2021-0046.
D. Petrosyan, H. Astsatryan, “Serverless high-performance computing over cloud,” Cybernetics and Information Technologies, vol. 22, no. 3, pp. 82-92, 2022. https://doi.org/10.2478/cait-2022-0029.
H. Wang, L. Tian, and C.-H. Jiang, “Practical parallel algorithm for all-pair shortest path based on pipelining,” Journal of Electronic Science and Technology of China, vol 6, no 3, 2008.
D. Kulkarni, N. Sharma, P. Shinde, V. Varma, “Parallelization of shortest path finder on GPU: Floyd-Warshall,” International Journal of Computer Applications, vol. 118, no. 20, 2015. https://doi.org/10.5120/20858-3547.
S.-C. Han, F. Franchetti, and M. Puschel, “Program generation for the all-pairs shortest path problem,” Proceedings of the 15th International Conference on Parallel Architectures and Compilation Techniques (PACT), 2006, pp. 222–232. https://doi.org/10.1145/1152154.1152189.
Z. Yan, Q. Song, “An implementation of parallel Floyd-Warshall algorithm based on hybrid MPI and OpenMP,” Proceedings of the International Conference on Electronics, Communications and Control, 2012, pp. 2461-2466.
K. Kalia, N. Gupta, “Analysis of Hadoop MapReduce scheduling in heterogeneous environment,” Ain Shams Engineering Journal, No 12, pp. 1101-1110, 2021. https://doi.org/10.1016/j.asej.2020.06.009.
J. Dean, S. Ghemawat, “Mapreduce: Simplified data processing on large clusters,” Communications of the ACM January, vol. 51, no. 11, pp. 107-113, 2008. https://doi.org/10.1145/1327452.1327492.
X. Xiaobing, B. Chao, and C. Feng, “An insight into traffic safety management system platform based on cloud computing,” Procedia - Soc. Behav. Sci., vol. 96, pp. 2643–2646, 2013. https://doi.org/10.1016/j.sbspro.2013.08.295.
S.N. Khezr, N.J. Navimipour, “MapReduce and its applications, challenges, and architecture: A comprehensive review and directions for future research,” Journal of Grid Computing, vol. 15, no. 3, pp. 295–321, 2017. https://doi.org/10.1007/s10723-017-9408-0.
N. S. Naik, A. Negi, and V. N. Sastry, ‘‘A review of adaptive approaches to MapReduce scheduling in heterogeneous environments,” Proceedings of the 2014 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Delhi, India, 2014, pp. 677-683, https://doi.org/10.1109/ICACCI.2014.6968497.
M. W. ur Rahman, N. S. Islam, X. Lu, D. Shankar, and D. K. Panda, ‘‘MRAdvisor: A comprehensive tuning, profiling, and prediction tool for MapReduce execution frameworks on HPC clusters,” Journal Parallel Distributed Computing, vol. 120, pp. 237–250, 2018. https://doi.org/10.1016/j.jpdc.2017.11.004.
H. Singh, S. Bawa, “A MapReduce-based scalable discovery and indexing of structured big data,” Future Generation Computer Systems, vol. 73, pp. 32–43, 2017. https://doi.org/10.1016/j.future.2017.03.028.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
