A Message Passing Implementation of a New Parallel Arrangement Algorithm

Authors: Ezequiel Herruzo, Juan José Cruz, José Ignacio Benavides, Oscar Plata

Abstract:

This paper describes a new algorithm of arrangement in parallel, based on Odd-Even Mergesort, called division and concurrent mixes. The main idea of the algorithm is to achieve that each processor uses a sequential algorithm for ordering a part of the vector, and after that, for making the processors work in pairs in order to mix two of these sections ordered in a greater one, also ordered; after several iterations, the vector will be completely ordered. The paper describes the implementation of the new algorithm on a Message Passing environment (such as MPI). Besides, it compares the obtained experimental results with the quicksort sequential algorithm and with the parallel implementations (also on MPI) of the algorithms quicksort and bitonic sort. The comparison has been realized in an 8 processors cluster under GNU/Linux which is running on a unique PC processor.

Keywords: Parallel algorithm, arrangement, MPI, sorting, parallel program.

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

References:

[1] Batcher, K. E. "Sorting Networks an their Applications". Proc. AFIPS Spring Joint Comput. Conf., Vol. 32, 307-314, 1968.
[2] Cormen, T.H. et al. "Introduction to Algorithms". 2. Auflage, The MIT Press 2001.
[3] Culler, E., Singh, J.P. "Parallel Computer Architecture: A Hardware/Sotware approach". Morgan Kaufmann Publishers, Inc, San Francisco, 1999. ISBN 1-55860-343-3.
[4] Grama, A. Et al. "Introduction to Parallel Computing". Second Edition. Addison-Wesley 2003, SIBN 0-201-64865-2.
[5] Hoare, C. "Quicksort". Computer Journal, Vol. 5, 1, 10-15, 1962.
[6] Message Passing Interface Forum. MPI: A Message-Passing Interface standard. The International Journal of Supercomputer Applications and High Performance Computing, 8, 1994.
[7] Message Passing Interface Forum. MPI: A Message-Passing Interface standard (version 1.1). Technical report, 1995. http://www.mpiforum. org.
[8] Pratt, V. "Shellsort and Sorting Networks". Garland, New York, 1979.
[9] Sedgewick, R. "Algorithms in Java", Parts 1-4. 3. Auflage, Addison- Wesley, 2003
[10] Shell, D. L. "A High-Speed Sorting Procedure". Communications of the ACM, 2, 7, 30-32. 1959.