配列をC++でMPIで並べ替える

Question

MPIライブラリを使用して乱数の配列を並べ替える必要があります。その考え方は、MPI_Scattervで配列を切り詰めてプロセスに送ることです。すべてのプロセスは、データ量を並べ替えてメインプロセス（MPI_Gatherv）に返す必要があります。メインプロセスは、部分的にソートされたテーブルをソートする必要があります（マージ）。最後のステップに問題がある場合。私はテーブルをcorectlyマージすることはできません。 アイデアここで コードです：事前に

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

おかげで、イゴール

Answer 1

は、個々のプロセスは、親配列のサブセットをソートします。しかし、マスタープロセスがこれらのすべてのサブセットを集めた後、親アレイに対して1つのソーティングが行われなければなりません。

散布処理1後

元の配列= {1,7,2,3、10,4,8,0、11,5,9,6}

：{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}

したがって、もう1つのソート・パスが必要です。

編集：ソリューションの

一つ（これをさらに最適化することができます）、次のようになります。 代わりにプレーンなMPIの送信とMPIが受け取る使用をMPI散乱を使用して収集します。 マスタプロセス/ノードは、データをダミーマスタプロセス/ノードに渡します。ダミーマスタプロセス/ノードは、ノードを残りのノードにさらに分割します。ノードの最後の行は、データのサブセットをソートし、ソートされたサブセットをその親に返すことができます。
親が個別にソートされたサブセットを受け取った後、ソートされたサブセットをソートし、そのセットをその親に提供する。

このアプローチは、さらに最適化することができます。