Performance Comparison of Parallel Sorting Algorithms on the Cluster of Workstations

Authors: Lai Lai Win Kyi, Nay Min Tun

Abstract:

Sorting appears the most attention among all computational tasks over the past years because sorted data is at the heart of many computations. Sorting is of additional importance to parallel computing because of its close relation to the task of routing data among processes, which is an essential part of many parallel algorithms. Many parallel sorting algorithms have been investigated for a variety of parallel computer architectures. In this paper, three parallel sorting algorithms have been implemented and compared in terms of their overall execution time. The algorithms implemented are the odd-even transposition sort, parallel merge sort and parallel rank sort. Cluster of Workstations or Windows Compute Cluster has been used to compare the algorithms implemented. The C# programming language is used to develop the sorting algorithms. The MPI (Message Passing Interface) library has been selected to establish the communication and synchronization between processors. The time complexity for each parallel sorting algorithm will also be mentioned and analyzed.

Keywords: Cluster of Workstations, Parallel sorting algorithms, performance analysis, parallel computing and MPI.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1059595

References:

[1] Kalim Qureshi, "A Practical Performance Comparison of Parallel Sorting Algorithms on Homogeneous Network of Workstations"
[2] Gropp, W., Lusk, E., Skjellum, A. (1999) Using MPI: portable parallel programming with the message-passing interface, MIT, Cambridge
[3] D. Bitton, D. DeWitt, D.K. Hsiao, J. Menon, "A Taxonomy of Parallel Sorting", ACM Computing Surveys, 16,3,pp. 287-318, September 1984.
[4] E. Lusk. Programming with MPI on clusters. In 3rd IEEE International Conference on Cluster Computing (CLUSTER'01), October 2001.
[5] Mono project (2004) Open source platform basedon NET, http://www.mono-proj ect. com
[6] Willcock, J., et. al. (2002) Using MPI with C# and the Common language infrastructure, Technical report TR570, Indiana University, Bloomington
[7] F. Meyer auf der Heide, A Wigderson, The Complexity of Parallel Sorting, SIAM Journal of Computing, 16, 1, pp. 100-107, February1999.
[8] Gropp, W., Lusk, E., Skjellum, A. (1999) Using MPI: portable parallel programming with the message-passing interface, MIT, Cambridge.