在 C++ 中使用 MPI 对数组进行排序

我想使用 MPI 库对随机数数组进行排序。这个想法是使用 MPI_Scatterv 切割数组并将其发送到进程。每个进程都应该在本地对其数据量进行排序并将其发送回主进程（MPI_Gatherv）。主进程应该对部分排序的表进行排序（合并）。如果最后一步有问题。我只是无法正确合并表格。 有任何想法吗？ 这是代码：

    #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();
}

预先感谢，伊戈尔

各个进程将对父数组的子集进行排序。但是，在主进程收集所有这些子集之后，必须对父数组进行一次排序。

e.g.

原始数组 = {1,7,2,3, 10,4,8,0, 11,5,9,6}

分散后 进程 1：{1,7,2,3} 进程 2：{10,4,8,0} 进程 3：{11,5,9,6}

和单个进程排序：{1,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. 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.

该方法还可以进一步优化。