C MPI管道使用插入排序

Question

我正在尝试使用此技术来实现：

因此，该程序在arraysize = numberfprocessors时可以工作并分类元素。问题在于我需要实现一种算法，该算法将数组分为冠军，主人将能够将Sublist发送到从属上进行整理。

#include <stdio.h>
#include <stdlib.h>
#include "mpi.h"
#include <time.h>    // time()
#define WORKTAG 1  /* WORKTAG for sending a number */

void Compare_And_Swap(int duomenuBlokas[], int proc_Nr, int step, int *maxValue, int *gottenValue, int sizeOfSublist);
void Collect_And_Sort (int proc_Nr, int sizeOfArray, int maxValue, int *sortedArray);

int main ( int argc, char *argv[] )
{
   int processNumber; // current process number : 0 - Master
   int * sortingArray; // Our sorting array
   int * subList; // sublist
   int tempValue;
   int maxValue;
   int numberOfProcessors; // On how many processors we run our program
   MPI_Status status;
   MPI_Init(&argc,&argv);
   int arraySize = atoi(argv[1]); // Aray size input through the console
   int sizeOfSublist;
   subList = (int*)calloc(arraySize,sizeof(int));
   MPI_Comm_size(MPI_COMM_WORLD,&numberOfProcessors);
   MPI_Comm_rank(MPI_COMM_WORLD,&processNumber);
   if(processNumber==0) /* Master generates p random numbers */
   {
      sortingArray = (int*)calloc(arraySize,sizeof(int));
      srand(time(NULL));
      for(int i = 0; i < arraySize; i++)
      {
          sortingArray[i] = rand() % 100;
      }
      printf("The %d numbers to sort : ",arraySize);
      for(int i =0; i<arraySize; i++)
      {
          printf(" %d", sortingArray[i]);
      }
      printf("\n");
      fflush(stdout);
   }
       sizeOfSublist = arraySize / numberOfProcessors; // Get the size of each subList
       subList = (int*)calloc(sizeOfSublist,sizeof(int));
       MPI_Scatter(sortingArray, sizeOfSublist, MPI_INT, subList, // Get sublists
        sizeOfSublist, MPI_INT, 0, MPI_COMM_WORLD);

   for(int i=0; i<numberOfProcessors-processNumber; i++)
   {
      if(processNumber==0) // Master gets the value
      {
         tempValue = sortingArray[i]; // Send subLists here [21,32] for example
         printf("Master gets %d.\n",sortingArray[i]);
         fflush(stdout);

         Compare_And_Swap(subList,processNumber,i,&maxValue,&tempValue, sizeOfSublist); // Masteris siunc
      }
      else // Slave receives the value
      {
         MPI_Recv(&tempValue,1,MPI_INT,processNumber-1,WORKTAG,MPI_COMM_WORLD,&status);
         printf("Slave %d receives %d.\n",processNumber,tempValue);
         fflush(stdout);
         Compare_And_Swap(subList,processNumber,i,&maxValue,&tempValue, sizeOfSublist);
      }
   }
   Collect_And_Sort(processNumber,arraySize,maxValue,subList); // Collect values


    printf("Exit. \n");
    MPI_Finalize();
    return 0;
}

void Compare_And_Swap(int duomenuBlokas[], int proc_Nr, int step, int *maxValue, int *gottenValue, int sizeOfSublist) // Parallel pipe-sort function
{

   if(step==0) // assign maxValue
   {
       *maxValue = *gottenValue;
   }

   else
      if(*gottenValue > *maxValue)  // Send maxValue
      {
         MPI_Send(maxValue,1,MPI_INT ,proc_Nr+1,WORKTAG,MPI_COMM_WORLD);
         printf("Slave %d sends %d to %d.\n",proc_Nr,*maxValue,proc_Nr+1);
         fflush(stdout);
         *maxValue = *gottenValue;

      }
      else // Send gotten value
      {
         MPI_Send(gottenValue,1,MPI_INT,proc_Nr+1,WORKTAG,MPI_COMM_WORLD);
         printf("Slave %d sends %d to %d.\n",proc_Nr,*gottenValue,proc_Nr+1);
         fflush(stdout);
      }
}

 void Collect_And_Sort(int proc_Nr, int sizeOfArray, int maxValue, int *sortedArray)
{
   MPI_Status status;

   if(proc_Nr==0)
   {
      sortedArray[0] = maxValue;
      for(int i=1; i<sizeOfArray; i++)
      {
         MPI_Recv(&sortedArray[i],1,MPI_INT,i,WORKTAG,MPI_COMM_WORLD,&status);
      }
      printf("Sorted array: ");
      for(int i=0; i<sizeOfArray; i++)
      {
        printf(" %d",sortedArray[i]);
      }
      printf("\n");
   }
   else
   {
        MPI_Send(&maxValue,1,MPI_INT,0,WORKTAG,MPI_COMM_WORLD);
   }

}

我使用mpi_ -scatter获取了订书机，我认为我应该将它们发送到这个地方：tempvalue = sortingArray [i]替换为tmparray = sublist; sublist;我遇到的问题是所有值都是相同的，因为“ Master” ProcessID -0仅包含第一个sublist。例如，数组[2,3,4,5,6,7,8]，在MPI_Scatter“ Master”之后，每次仅发送[2,3]。非常感谢。

如果需要，我还可以附加结果图片，以使其更加清晰。让我知道！

Answer 1

通常，您需要使用 MPI_Scatterv 一般。如果所有标准师的长度相同，则您的方法将起作用。

更大的问题是您的测试如果（ *GottenValue＆gt; *MaxValue）需要变得更加复杂，因为您的 GottenValue 将是一个数组，因此您需要比较每个数组成分。例如，您可以在每个通信对中：让两个进程都从另一个接收，并且仅保留最低/最高的elemts。