C++ MPI：std :: merge on arrays

Question

ここでは面白い問題があります。私はすでにいくつかのサブ配列をソートしており、ソートされた大きな配列にそれらをマージする必要があります。私は以下のコードでこれをやろうとしていますが、私が期待している結果は得られません。

あなたのうちの誰かが私が間違っていることを教えてもらえましたか？

あなたが見ることができますどのように

#include <stdio.h> 
#include <stdlib.h> 
#include <mpi.h> 
#include <algorithm> 
#include <vector> 
#include <iostream> 

using namespace std; 

#define N 32 
#define ROOT 0 

int A[N]; // this should be global 

void quickSort(int*, int, int); 
int partition(int*, int, int); 

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

    int size; 
    int rank; 

    vector<int> result(N); 

    MPI_Init(&argc, &argv); 

    MPI_Comm_size(MPI_COMM_WORLD, &size); 
    MPI_Comm_rank(MPI_COMM_WORLD, &rank); 

    int count = N/size; 

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

    if (rank == ROOT) { 
     for (int i = 0; i < N; i++) { 
      A[i] = rand() % 10; 
     } 
     // master local copy 
     for (int i = 0; i < count; i++) 
      localArray[i] = A[i]; 

     for (int dest = 1; dest < size; ++dest) { 
      MPI_Send(&A[dest * count], count, MPI_INT, dest, 1, MPI_COMM_WORLD); 
      printf("P0 sent a %d elements to P%d.\n", count, dest); 
     } 

     int source = 1; 

     int sizeResult = count * 2; 
     int sizeResult2 = count; 

     int tmpVec[sizeResult2]; 
     int tm[sizeResult]; 

     MPI_Recv(tmpVec, count, MPI_INT, source, 2, MPI_COMM_WORLD, MPI_STATUS_IGNORE); 

     for (int source = 2; source < size; source++) { 
      MPI_Recv(localArray, count, MPI_INT, source, 2, MPI_COMM_WORLD, MPI_STATUS_IGNORE); 

      //-------------------------------HERE IS THE PROBLEM--------------------------- 
      merge(tmpVec, tmpVec + sizeResult2, localArray, localArray + count, tm); 

      sizeResult2 = sizeResult; 
      for (int i = 0; i < sizeResult; i++) { 
       tmpVec[i] = tm[i]; 
       cout << tm[i] << " "; 
      } 
      cout << endl; 
      sizeResult += count; 
      //------------------------------------------------------------------------------- 
     } 

     for (int i = 0; i < sizeResult2; i++) 
      cout << tmpVec[i] << " "; 
     cout << endl << sizeResult2 << endl; 

     for (int i = 0; i < N; i++) 
      cout << A[i] << " "; 

    } 
    else { 
     MPI_Recv(localArray, count, MPI_INT, ROOT, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE); 

     quickSort(localArray, 0, count); 

     MPI_Send(localArray, count, MPI_INT, ROOT, 2, MPI_COMM_WORLD); 
    } 
    MPI_Finalize(); 
    return 0; 
} 
void quickSort(int* A, int p, int q) { 
    int r; 
    if (p < q) { 
     r = partition(A, p, q); 
     quickSort(A, p, r); 
     quickSort(A, r + 1, q); 
    } 
} 

int partition(int* A, int p, int q) { 
    int x = A[p]; 
    int i = p; 
    int j; 

    for (j = p + 1; j < q; j++) { 
     if (A[j] <= x) { 
      i = i + 1; 
      swap(A[i], A[j]); 
     } 

    } 
    swap(A[i], A[p]); 
    return i; 
} 

、私がした後に、第2の1の最初の部分配列をマージしようとしている：私は見当がつかないので、私のロジックが、それはよさそうだだ、私は...ここ

が私のコードだと思います

Answer 1

中間バッファ（tmpVecおよびtm）に十分なメモリを割り当てていません。それを避けるために、代わりに単に低レベルの配列で悩まのstd::vectorを利用します。

std::vector<int> tmpVec(count); 
std::vector<int> tm; 

MPI_Recv(tmpVec.data(), count, MPI_INT, source, 2, MPI_COMM_WORLD, MPI_STATUS_IGNORE); 

for (int source = 2; source < size; source++) { 
    MPI_Recv(localArray, count, MPI_INT, source, 2, MPI_COMM_WORLD, MPI_STATUS_IGNORE); 

    merge(tmpVec.begin(), tmpVec.end(), localArray, localArray + count, std::back_inserter(tm)); 

    tmpVec = tm; 
    tm.resize(0); 
} 

を一般的なヒントとして、より慎重に変数名の選択肢を検討してください。変数名がわかりやすい場合は、コードを推論する方がずっと簡単です。

もう一度実際の問題に戻る：スキャッター&を収集してください！再帰的なmergesortを使用して、集められた連続した配列に対してstd::inplace_mergeを使用することはかなり簡単です。トリックは、すでにソートされている各ローカル部分のオフセットを使用し、その配列に「終了」オフセットを追加することです。この場合

#include <stdio.h> 
#include <stdlib.h> 
#include <mpi.h> 
#include <algorithm> 

#define N 16 
int A[N]; 

// This is basically textbook recursive merge sort using std::merge_inplace 
// but it considers the offsets of segments that are already sorted 
void merge_indexed(int data[], const int offsets[], size_t index_begin, size_t index_end) 
{ 
    if (index_end - index_begin > 1) { 
     auto index_middle = index_begin + (index_end - index_begin)/2; 
     merge_indexed(data, offsets, index_begin, index_middle); 
     merge_indexed(data, offsets, index_middle, index_end); 
     std::inplace_merge(&data[offsets[index_begin]], &data[offsets[index_middle]], &data[offsets[index_end]]); 
    } 
} 

int main(int argc, char *argv[]) { 
    int size; 
    int rank; 
    const int ROOT = 0; 

    MPI_Init(&argc, &argv); 

    MPI_Comm_size(MPI_COMM_WORLD, &size); 
    MPI_Comm_rank(MPI_COMM_WORLD, &rank); 

    auto remainder = N % size; 
    int local_counts[size], offsets[size + 1]; 
    int sum = 0; 
    for (int i = 0; i < size; i++) { 
     local_counts[i] = N/size; 
     if (remainder > 0) { 
      local_counts[i] += 1; 
      remainder--; 
     } 
     offsets[i] = sum; 
     sum += local_counts[i]; 
    } 
    offsets[size] = sum; 

    int localArray[local_counts[rank]]; 

    if (rank == ROOT) { 
     for (int i = 0; i < N; i++) { 
      A[i] = rand() % 10; 
     } 
    } 

    MPI_Scatterv(A, local_counts, offsets, MPI_INT, localArray, local_counts[rank], MPI_INT, ROOT, MPI_COMM_WORLD); 

    std::sort(&localArray[0], &localArray[local_counts[rank]]); 

    MPI_Gatherv(localArray, local_counts[rank], MPI_INT, A, local_counts, offsets, MPI_INT, ROOT, MPI_COMM_WORLD); 

    if (rank == ROOT) { 
     //---------------Merge sections in localArray------------------- 
     merge_indexed(A, offsets, 0, size); 
    } 

    MPI_Finalize(); 
    return 0; 
}