A Message Passing Implementation of a New Parallel Arrangement Algorithm

• DOI: 10.5281/zenodo.1080441
• Publication Date: 2008-09-29
• Authors: Herruzo, Ezequiel; Cruz, Juan José; Benavides, José I...; Plata, Oscar
• Keywords: 0301 basic medicine; 0303 health sciences; 03 medical and health sciences; Parallel algorithm; arrangement; MPI; sorting; parallel program.

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