Comparative Analysis of OpenMP and MPI Parallel Computing Implementations in Team Sort Algorithm
Abstract
Tim Sort is a sorting algorithm that combines Merge Sort and Binary Insertion Sort sorting algorithms. Parallel computing is a computational processing technique in parallel or is divided into several parts and carried out simultaneously. The application of parallel computing to algorithms is called parallelization. The purpose of parallelization is to reduce computational processing time, but not all parallelization can reduce computational processing time. Our research aims to analyse the effect of implementing parallel computing on the processing time of the Tim Sort algorithm. The Team Sort algorithm will be parallelized by dividing the flow or data into several parts, then each sorting and recombining them. The libraries we use are OpenMP and MPI, and tests are carried out using up to 16 core processors and data up to 4194304 numbers. The goal to be achieved by comparing the application of OpenMP and MPI to the Team Sort algorithm is to find out and choose which library is better for the case study, so that when there is a similar case, it can be used as a reference for using the library in solving the problem. The results of research for testing using 16 processor cores and the data used prove that the parallelization of the Sort Team algorithm using OpenMP is better with a speed increase of up to 8.48 times, compared to using MPI with a speed increase of 8.4 times. In addition, the increase in speed and efficiency increases as the amount of data increases. However, the increase in efficiency that is obtained by increasing the processor cores decreases.
Downloads
References
D. Maitra, Beginner's Guide to Code Algorithms, Boca Raton: CRC Press, 2022.
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Fourth Edition, London: MIT Press, 2022.
S. S. Skiena, The Algorithm Design Manual, New York: Springer, 2020.
D. Eddelbuettel, “Parallel Computing With R: A Brief Review,” WIREs Comput Stat, vol. 13, no. 2, p. e1515, 2021.
I. N. A. Yudiswara and A. Suganda.
F. R. Lumbanraja, A. and N. R. Muttaqina, “Analisa Komputasi Paralel Mengurutan Data Dengan Metode Radix Dan Selection,” Jurnal Komputasi, vol. 8, no. 2, pp. 77-93, 2020.
J. L. Hennessy and D. A. Patterson, Computer Architecture: A Quantitative Approach, Cambridge: Morgan Kaufmann, 2019.
V. D. Thoke, “THEORY OF DISTRIBUTED COMPUTING AND PARALLEL PROCESSING WITH ITS APPLICATIONS, ADVANTAGES AND DISADVANTAGES,” in nternational Conference on Innovative Minds, Vita, 2015.
W. Tang, W. Feng, J. Deng, M. Jia and H. Zui, “Parallel Computing for Geocomputational Modeling,” in GeoComputational Analysis and Modeling of Regional Systems, New York, Springer, Cham, 2018, pp. 37-54.
P. Czarnul, Parallel Programming for Modern High Performance Computing Systems, Boca Raton: CRC Press, 2018.
E. D. Nugroho, M. E. Wibowo and R. Pulungan, “Parallel Implementation of Genetic Algorithm for Searching Optimal Parameters of Artificial Neural Networks,” in International Conference on Science and Technology-Computer, Yogyakarta, 2017.
P. S. Pacheco and M. Malensek, An Introduction to Parallel Programming, Massachusetts: Morgan Kaufmann, 2022.
R. Trobec, B. Slivnik, P. Bulić and B. Robič, Introduction to Parallel Computing From Algorithms to Programming on State-of-the-Art Platforms, New York: Springer, Champ, 2018.
V. Kasilov, P. Drobintsev and N. Voinov, “High-performance genome sorting program,” in International Young Scientists Conference on Computational Science, St. Petersburg, 2021.
M. R. Hanafi, M. A. Faadhilah, D. Pradeka and M. T. Dwi Putra, “Comparison Analysis of Bubble Sort Algorithm with Tim Sort Algorithm Sorting Against the Amount of Data,” Journal of Computer Engineering, Electronics and Information Technology, vol. 1, no. 1, pp. 9-13, 2022.
N. Auger, V. Juge, C. Nicaud and C. Pivoteau, “On the Worst-Case Complexity of TimSort,” in Leibniz International Proceedings in Informatics, Wadern, 2018.
P. Ganapathi and R. Chowdhury, “Parallel Divide-and-Conquer Algorithms for Bubble Sort, Selection Sort and Insertion Sort,” The British Computer Society, vol. 00, no. 0, pp. 1-11, 2021.
Copyright (c) 2023 Eko Dwi Nugroho, Ilham Firman Ashari, Muhammad Nashrullah, Muhammad Habib Algifari, Miranti Verdiana
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
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 (Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) ) 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 (See The Effect of Open Access).
