Sorting array with MPI in C++

Question

I want to sort array of random numbers using MPI library. The idea is to chop array with MPI_Scatterv and send it to the processes. Every process should localy sort its amount of data and send it back to the main process (MPI_Gatherv). Main process should sort partly sorted table(merge). If have problems with last step. I just cannot merge the table corectly. Any ideas? Here is the code:

    #include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "math.h"
#include "mpi.h"
#include <time.h>


#define N 20

int numOfProc, idproc;


int compare(const void * a, const void * b) {
   const int *ia = (const int *)a;
    const int *ib = (const int *)b;
    return *ia  - *ib; 
}



int main(int argc,char ** argv) {

   MPI_Init(&argc, &argv);
   MPI_Comm_size(MPI_COMM_WORLD, &numOfProc );
   MPI_Comm_rank(MPI_COMM_WORLD, &idproc);

   int * buf, * send_buf, * receive_buf, * sorted_buf, *displ, *sendcnts, *recvcnts;
   int count = N/numOfProc;
   int size, i;
   int temp, index;


   displ=(int*)malloc(numOfProc*sizeof(int));

   sendcnts=(int*)malloc(numOfProc*sizeof(int));

   recvcnts=(int*)malloc(numOfProc*sizeof(int));

   buf=(int*)malloc(count*sizeof(int));

   for(i=0; i<numOfProc; i++){
       displ[i]=i*count;
       sendcnts[i]=count;
       recvcnts[i]=count;
   }



   if(idproc == 0) {
      size=N;
      send_buf=(int*)malloc(size*sizeof(int));
      receive_buf=(int*)malloc(size*sizeof(int));


      for (i=0;i<size;i++) {
         send_buf[i] = rand();
      }
      printf("\n\n");
      fflush(stdout);
   }

   MPI_Scatterv(send_buf, sendcnts, displ, MPI_INT, buf, count, MPI_INT, 0, MPI_COMM_WORLD);

   printf("proces %d: ", idproc);
   qsort(buf, count, sizeof(int), compare);
   for (int i = 0; i < count; i++) printf("%d ", buf[i]);
   printf("\n\n");
   fflush(stdout);

   MPI_Gatherv(buf, count, MPI_INT, receive_buf, recvcnts, displ, MPI_INT, 0, MPI_COMM_WORLD);

   if (idproc == 0) {
       //merge
       temp=INT_MAX;
       for(i=0; i<size; i++){
           for(int j=0; j<numOfProc; j++){

               if(temp>receive_buf[displ[j]]){
                   temp=receive_buf[displ[j]];
                   receive_buf[displ[j]]=receive_buf[i];
                   receive_buf[i]=temp;
               }

           }

           printf("%d ", receive_buf[i]);
       }


      printf("\n");
      fflush(stdout);
   }
   wait(100);
   MPI_Finalize();
}

Thanks in advance, Igor

Answer 1

The individual processes will sort the sub set of the parent array. But after the Master process gathers all these sub sets there has to be one sorting done for the parent array.

e.g.

original array = {1,7,2,3, 10,4,8,0, 11,5,9,6}

after scatter process 1 : {1,7,2,3} process 2 : {10,4,8,0} process 3 : {11,5,9,6}

and individual process sorting : {1,2,3,7} , {0,4,8,10} , { 5,6,9,11}

thus after gathering you have the original array as {1,2,3,7 , 0,4,8,10 , 5,6,9,11}

Thus there has to be one more sorting pass done.

Edit :

One of the solutions would be (This can be further optimized): instead of using mpi scatter and gather use a plain mpi send and mpi receive. The master process/node would give the data to the dummy master process/node which will further divide it to rest of the nodes. The last line of nodes can sort the sub set of data and return the sorted subsets to their parents.
after the parents receive the individually sorted sub sets they will sort the sorted subsets and provide their sets to their parents.

This approach can be further optimized.