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("

");
      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("

");
   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("
");
      fflush(stdout);
   }
   wait(100);
   MPI_Finalize();
}

提前感谢Igor

Answer 1

各个过程将划分母体的子体。但是,在主修过程收集了所有这些子集之后,必须对母体进行分类。

e.g.

原阵列={1,7,2,3,10,4,8,0,11,5,9,6}

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

和单独程序分类:{ 11,2,3,7} ,{0,4,8,10} ,{5,6,9,11}

因此,在你聚集后,其原有阵列为{1,2,3,7 , 0,4,8,10 ,5,6,9,11}

因此,必须再作一次分类。

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. Submitting sorting jobs 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. receiving sorted jobs
after the parents receive the individually sorted sub sets they will sort the sorted subsets and provide their sets to their parents.

这种做法可以进一步优化。

友情链接