SHARE
TWEET

Untitled

a guest May 25th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <cmath>
  5. #include <mpi.h>
  6.  
  7. using namespace std;
  8.  
  9. void readArrayFromFile(string filename, int* array) {
  10.     ifstream fin(filename);
  11.     int n;
  12.     fin >> n;
  13.  
  14.     for (int i = 0; i < n; ++i) {
  15.         fin >> array[i];
  16.     }
  17. }
  18.  
  19. void createArrayFile(string filename, int n) {
  20.     ofstream fout;
  21.     fout.open(filename);
  22.     fout << n << endl;
  23.  
  24.     for (int i = 0; i < n; i++) {
  25.         fout << rand() % 100000 + 1 << " ";
  26.     }
  27. }
  28.  
  29. void writeArrayInFile(string filename, int* array, int n) {
  30.     ofstream fout;
  31.     fout.open(filename);
  32.     fout << n << endl;
  33.  
  34.     for (int i = 0; i < n; i++ ) {
  35.         fout << array[i] << " ";
  36.     }
  37. }
  38.  
  39. int compare(const void* x1, const void* x2) {
  40.     return ( *(int*)x1 - *(int*)x2 );
  41. }
  42.  
  43. int getPivot(int* array, int size) {
  44.     if (size == 0) {
  45.         return 0;
  46.     } else if (size < 3) {
  47.         return array[0];
  48.     }
  49.     return (array[0] + array[size - 1] + array[(size - 1) / 2]) / 3;
  50. }
  51.  
  52. int getPairRank(int rank, int size) {
  53.     int bitToCheck = 1 << ((int) log2(size) - 1);
  54.     return rank ^ bitToCheck;
  55. }
  56.  
  57. void swapPairs(int pivot, int*& array, int& size, int pairRank, int rank, MPI_Comm MPI_Local_Comm) {
  58.     bool overPivotFlag = rank < pairRank;
  59.     int lowerIter = 0;
  60.     int overIter = size - 1;
  61.     int temp;
  62.  
  63.     while (lowerIter <= overIter) {
  64.         if (array[lowerIter] >= pivot) {
  65.             temp = array[lowerIter];
  66.             array[lowerIter] = array[overIter];
  67.             array[overIter] = temp;
  68.             overIter--;
  69.         } else {
  70.             lowerIter++;
  71.         }
  72.     }
  73.  
  74.     int sendSize = overPivotFlag ? size - lowerIter : lowerIter;
  75.     int sendIndex = overPivotFlag ? lowerIter : 0;
  76.     int recvSize = 0;
  77.  
  78.     MPI_Sendrecv(&sendSize, 1, MPI_INT, pairRank, 100, &recvSize, 1, MPI_INT, pairRank, 100, MPI_Local_Comm, MPI_STATUS_IGNORE);
  79.  
  80.     int* recvSubArray = new int[recvSize];
  81.  
  82.     MPI_Sendrecv(&(array[sendIndex]), sendSize, MPI_INT, pairRank, 100, recvSubArray, recvSize, MPI_INT, pairRank, 100, MPI_Local_Comm, MPI_STATUS_IGNORE);
  83.     size -= sendSize;
  84.  
  85.     int* finalArray = new int[size + recvSize];
  86.     int j = 0;
  87.     for (int i = 0; i < size + recvSize; i++) {
  88.         if (i < size) {
  89.             finalArray[i] = overPivotFlag ? array[i] : array[lowerIter + i];
  90.         } else {
  91.             finalArray[i] = recvSubArray[j];
  92.             j++;
  93.         }
  94.     }
  95.  
  96.     array = finalArray;
  97.     size += recvSize;
  98. }
  99.  
  100. int main(int argc, char** argv) {
  101.     string inputFile = argv[1];
  102.     string outputFile = argv[2];
  103.     int n;
  104.  
  105.     if (argc > 3) {
  106.         n = atoi(argv[3]);
  107.         createArrayFile(inputFile, n);
  108.     }
  109.  
  110.     MPI_Init(&argc, &argv);
  111.     int* array = new int[0];
  112.     int size = 0;
  113.     double time = 0.0; // счетчик времени
  114.  
  115.     int rank, worldSize;
  116.     MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  117.     MPI_Comm_size(MPI_COMM_WORLD, &worldSize);
  118.  
  119.     if (rank == 0) {
  120.         ifstream fin(inputFile);
  121.         fin >> size;
  122.         array = new int[size];
  123.         readArrayFromFile(inputFile, array);
  124.         time = MPI_Wtime();
  125.     }
  126.     MPI_Bcast(&size, 1, MPI_INT, 0, MPI_COMM_WORLD);
  127.  
  128.     auto* sizes = new int[worldSize];
  129.     auto* displs = new int[worldSize];
  130.     int remainder = size % worldSize;
  131.     int sum = 0;
  132.  
  133.     for (int i = 0; i < worldSize; i++) {
  134.         sizes[i] = size / worldSize;
  135.         if (remainder > 0) {
  136.             sizes[i]++;
  137.             remainder--;
  138.         }
  139.         displs[i] = sum;
  140.         sum += sizes[i];
  141.     }
  142.  
  143. //    if (size == 1) {
  144. //        qsort(array, size, sizeof(int), compare);
  145. //    }
  146.  
  147.     int cyclesCount = (int) log2(worldSize);
  148.     int subArraySize = sizes[rank];
  149.     int* subArray = new int[subArraySize];
  150.     int* subArrayDispls = new int[worldSize];
  151.     int* subArraySizes = new int[worldSize];
  152.  
  153.     MPI_Scatterv(array, sizes, displs, MPI_INT, subArray, subArraySize, MPI_INT, 0, MPI_COMM_WORLD);
  154.  
  155.     MPI_Comm MPI_Local_Comm = MPI_COMM_WORLD;
  156.     int localRank = rank;
  157.     int localSize = worldSize;
  158.     int localPivot = 0;
  159.  
  160.     for(int iteration = 0; iteration < cyclesCount; iteration++) {
  161.         if (localRank == 0) {
  162.             localPivot = getPivot(subArray, subArraySize);
  163.         }
  164.         MPI_Bcast(&localPivot, 1, MPI_INT, 0, MPI_Local_Comm);
  165.  
  166.         int pairRank = getPairRank(localRank, localSize);
  167.  
  168.         swapPairs(localPivot, subArray, subArraySize, pairRank, localRank, MPI_Local_Comm);
  169.  
  170.         int color = localRank < pairRank ? 0 : 1;
  171.         MPI_Comm_split(MPI_Local_Comm, color , localRank, &MPI_Local_Comm);
  172.         MPI_Comm_size(MPI_Local_Comm, &localSize);
  173.         MPI_Comm_rank(MPI_Local_Comm, &localRank);
  174.     }
  175.  
  176.     qsort(subArray, subArraySize, sizeof(int), compare);
  177.     MPI_Allgather(&subArraySize, 1, MPI_INT, subArraySizes, 1, MPI_INT, MPI_COMM_WORLD);
  178.     subArrayDispls[0] = 0;
  179.     for (int i = 1; i < worldSize; i++) {
  180.         subArrayDispls[i] = subArrayDispls[i - 1] + subArraySizes[i - 1];
  181.     }
  182.     cout << rank << " size: " << subArraySizes[rank] << " disp: " << subArrayDispls[rank] << endl;
  183.     MPI_Gatherv(subArray, subArraySize, MPI_INT, array, subArraySizes, subArrayDispls, MPI_INT, 0, MPI_COMM_WORLD);
  184.  
  185.     cout << rank << " gath" << endl;
  186.     if (rank == 0) {
  187.         time = MPI_Wtime() - time;
  188.         cout << time << endl;
  189.         writeArrayInFile(outputFile, array, size);
  190.     }
  191.  
  192.     MPI_Finalize();
  193.     return 0;
  194. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top