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

В общем намек, пожалуйста, рассмотреть вопрос о выборе ваших имен переменных более тщательно. Гораздо проще рассуждать о коде, когда имена переменных являются описательными.

Возвращаясь к вашей реальной проблеме, снова: используйте разброс & собирайте! Довольно просто использовать 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; 
}