A Message Passing Implementation of a New Parallel Arrangement Algorithm

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.

Authors:

• Ezequiel Herruzo
• Juan José Cruz
• José Ignacio Benavides
• Oscar Plata

Keywords:

• Parallel algorithm
• arrangement
• MPI
• sorting
• parallel program.

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.