Сортировка массива с помощью MPI в C ++

Question

Я хочу отсортировать массив случайных чисел, используя библиотеку MPI. Идея состоит в том, чтобы нарезать массив с помощью MPI_Scatterv и отправить его в процессы. Каждый процесс должен локально отсортировать свой объем данных и отправить его обратно в основной процесс (MPI_Gatherv). Основной процесс должен отсортировать частично отсортированную таблицу (объединить). Если есть проблемы с последним шагом. Я просто не могу объединить таблицу по центру. Есть идеи? Вот код:

    #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,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}

и сортировка отдельных процессов: {1,2, 3,7}, {0,4,8,10}, {5,6,9,11}

, таким образом, после сбора вы получите исходный массив как {1,2,3,7, 0, 4,8,10, 5,6,9,11}

Таким образом, должен быть сделан еще один проход сортировки.

Редактировать:

Одно из решений было бы (Это может быть дополнительно оптимизировано): вместо использования рассеяния и сбора данных в формате mpi используйте обычную отправку и получение MPI. Главный процесс / узел передает данные фиктивному главному процессу / узлу, который далее делит их на остальные узлы.Последняя строка узлов может сортировать подмножество данных и возвращать отсортированные подмножества своим родителям.
после того, как родители получат индивидуально отсортированные подмножества, они будут сортировать отсортированные подмножества и предоставлять свои наборы своим родителям.

Этот подход может быть дополнительно оптимизирован.