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

당신은 내가 두 번째로 첫 번째 부분 배열을 병합하려고하고있어, 볼 수있는 방법 : 나는 단서가 없기 때문에, 그건 내 논리는 여기

내 코드입니다 .. 제가 생각하기 좋아 보인다 그 결과를 세 번째 것과 병합합니다.

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

을 일반적인 힌트로, 더 신중 변수 이름의 검색을 고려하시기 바랍니다. 변수 이름이 설명적인 경우 코드에 대해 추론하는 것이 훨씬 쉽습니다.

다시 실제 문제로 돌아가십시오. scatter &가 모여 사용하십시오! 재귀 적 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; 
}