SHARE
TWEET

Untitled

a guest Nov 20th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "pch.h"
  2.  
  3. #include <iostream>
  4. #include <algorithm>
  5. #include<stdlib.h>
  6. #include <time.h>
  7. #include <mpi.h>
  8. #include <cmath>
  9.  
  10. #define MASTER 0
  11. using namespace std;
  12. void bubblesort(int *v, int n);
  13. int *merge(int* v1, int n1, int* v2, int n2);
  14.  
  15. int main(int argc, char **argv) {
  16.     //zainicjalizuj środowisko MPI,
  17.     MPI_Init(&argc, &argv);
  18.     //przypisz zmiennej n ilosc elementow sortowanej tablicy
  19.     int n = 10;
  20.     //zadeklaruj wskaźnik służący do odwoływania się do tablicy liczb całkowitych
  21.     int *a = new int[n];
  22.     int rank, size, length;
  23.     int kawalki;
  24.     int *data = NULL;
  25.     int buforN;
  26.     int *bufor = NULL;
  27.     int *kawalki_wys = NULL;
  28.     char hostname[MPI_MAX_PROCESSOR_NAME];
  29.     MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  30.     MPI_Comm_size(MPI_COMM_WORLD, &size);
  31.     MPI_Get_processor_name(hostname, &length);
  32.     //jesli nr procesu = 0 (master)
  33.     if (rank == MASTER) {
  34.         srand(time(NULL));
  35.         //dzielenie tablicy rownomiernie na czesci pomiedzy procesy
  36.         kawalki = n / size;
  37.         if (n%size != 0) {//jzaokraglenie do gory reszty z dzielenia
  38.             kawalki++;
  39.         }
  40.         cout << "Kawalki: " << kawalki << endl;
  41.  
  42.         data = new int[size * kawalki];
  43.         cout << "Tablica wyjsciowa " << endl;
  44.  
  45.         for (int i = 0; i < n; i++) {
  46.             data[i] = rand() % 1000;
  47.             cout << data[i] << endl;
  48.         }
  49.         //wypełnianie reszty ostatniego kawałka zerami
  50.         for (int i = n; i < size*kawalki; i++) {
  51.             data[i] = 0;
  52.         }
  53.     }
  54.  
  55.     MPI_Barrier(MPI_COMM_WORLD);//jak wszystkie procesy zakoncza swoje dzialanie dopiero mozna ruszyc dalej
  56.     double timestart = MPI_Wtime();
  57.  
  58.     MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
  59.  
  60.     kawalki = n / size;
  61.     if (n%size != 0) {
  62.         kawalki++;
  63.     }
  64.     bufor = new int[kawalki];
  65.  
  66.     MPI_Scatter(data, kawalki, MPI_INT, bufor, kawalki, MPI_INT, 0, MPI_COMM_WORLD);
  67.     delete[] data;
  68.     data = NULL;
  69.  
  70.     if (size - 1 != rank) {
  71.         buforN = kawalki;
  72.     }
  73.     else {
  74.         buforN = n - kawalki * rank;
  75.     }
  76.  
  77.     bubblesort(bufor, buforN);
  78.     // w tym momencie KAŻDY PROCES POSIADA POSORTOWANY SWÓJ KAWAŁEK TABLICY
  79.     int krok;
  80.     int s_wys;
  81.     for (krok = 1; krok < size; krok = krok * 2) { //tu wejdzie 1 3 5
  82.         if ((rank % (2 * krok)) != 0) {
  83.             MPI_Send(bufor, buforN, MPI_INT, rank - krok, 0, MPI_COMM_WORLD);
  84.             break;
  85.         }
  86.         if (rank + krok < size) {
  87.             if (n >= kawalki * (rank + 2 * krok)) { //czy to dziala i dlczego czy id+krok
  88.                 s_wys = kawalki * krok;
  89.             }
  90.             else {
  91.                 s_wys = n - (kawalki*(rank + krok));
  92.             }
  93.             kawalki_wys = new int[s_wys];
  94.             MPI_Status status;
  95.             MPI_Recv(kawalki_wys, s_wys, MPI_INT, rank + krok, 0, MPI_COMM_WORLD, &status);
  96.             data = merge(bufor, buforN, kawalki_wys, s_wys);
  97.             delete[] bufor;
  98.             delete[] kawalki_wys;
  99.             bufor = data;
  100.             buforN = buforN + s_wys;
  101.         }
  102.     }
  103.  
  104.     if (rank == MASTER) {
  105.         cout << "\nTablica posortowana o wielkosci " << buforN << endl;
  106.         for (int i = 0; i < buforN; i++) {
  107.             cout << bufor[i] << endl;
  108.         }
  109.         cout << "\nLiczba procesow: " << size << endl;
  110.         cout << "Czas: " << MPI_Wtime() - timestart << endl;
  111.     }
  112.  
  113.     MPI_Finalize();
  114.     return 0;
  115. }
  116.  
  117. void bubblesort(int *v, int n) {
  118.     for (int i = n - 2; i >= 0; i--)
  119.         for (int j = 0; j <= i; j++)
  120.             if (v[j] > v[j + 1]) {
  121.                 swap(v[j], v[j + 1]);
  122.             }
  123. }
  124.  
  125. int* merge(int* v1, int n1, int* v2, int n2) {
  126.     int *merged = new int[n1 + n2];
  127.  
  128.     int i = 0;
  129.     int j = 0;
  130.     int k;
  131.  
  132.     for (k = 0; k < n1 + n2; k++) {
  133.         if (i >= n1) {
  134.             merged[k] = v2[j];
  135.             j++;
  136.         }
  137.         else if (j >= n2) {
  138.             merged[k] = v2[i];
  139.             i++;
  140.         }
  141.         else if (v1[i] < v2[j]) {
  142.             merged[k] = v1[i];
  143.             i++;
  144.         }
  145.         else {
  146.             merged[k] = v2[j];
  147.             j++;
  148.         }
  149.     }
  150.  
  151.     return merged;
  152. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top