在C ++中使用MPI对数组进行排序 [英] Sorting array with MPI in C++

问题描述

我想使用MPI库对随机数数组进行排序.这个想法是用MPI_Scatterv分割数组并将其发送到进程.每个进程都应在本地对其数据量进行排序，然后将其发送回主进程(MPI_Gatherv).主进程应该对部分排序的表进行排序(合并).如果最后一步有问题.我只是不能完全合并表. 有任何想法吗? 这是代码:

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

预先感谢，伊戈尔

推荐答案

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

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.

例如

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

original array = {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}之后

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

和单个进程排序:{1,2,3,7}，{0,4,8,10}，{5,6,9,11}

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

因此，收集后，您的原始数组为{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.

一种解决方案是(可以进一步优化): 而不是使用mpi分散和收集，而是使用简单的mpi发送和mpi接收. 主进程/节点会将数据提供给虚拟主进程/节点，该虚拟主进程/节点会将其进一步划分为其余节点.节点的最后一行可以对数据的子集进行排序，并将排序后的子集返回给其父级.
父母收到单独排序的子集后，他们将对排序后的子集进行排序，并将其集提供给父母.

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.

这篇关于在C ++中使用MPI对数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！