Как улучшить алгоритм сортировки слиянием с OpenMP? - PullRequest
Новая
       24

Как улучшить алгоритм сортировки слиянием с OpenMP?

0 голосов
/ 14 мая 2019

Я пытаюсь улучшить время выполнения моего кода с помощью OpenMP.Я провожу исследование параллелизма и тестирую различные способы его реализации.

Я попытался разделить мой массив на 4, и я хочу запустить свой код в 4 ядрах (каждая часть в одном ядре), а затем объединить все,

Итак, я нарезаю его и запускаю 4 mergeSorts, используя: #pragma omp single nowait, но я думаю, что я делаю это неправильно, потому что он использует только 1,5 ядра.Что мне нужно изменить, чтобы сделать то, что мне нужно?(Извините, я новичок в OpenMP, я студент информатики, и я делаю это как исследование класса).

Кроме того, у меня есть замедление, потому что мне нужно сделать дополнительные слияния, потому что оно разделенов четырех частях (мое время выполнения примерно вдвое медленнее, чем простым параллельным способом.

Вот мой полный код (приветствуются другие советы по улучшению): 

#include<iostream>
#include<fstream>
#include<algorithm>
#include "omp.h"
using namespace std;

int n = 60000000;
int * Vet = new int [60000000];
double startTime, stopTime;

void generate_list(int * x, int n) {
   int i,j,t;
   for (i = 0; i < n; i++)
     x[i] = i;
   for (i = 0; i < n; i++) {
     j = rand() % n;
     t = x[i];
     x[i] = x[j];
     x[j] = t;
   }
}

void merge(int aux[], int left, int middle, int right){
    int * temp = new int [middle-left+1];
    int * temp2 = new int[right-middle];
    for(int i=0; i<(middle-left+1); i++){
        temp[i]=aux[left+i];
    }
    for(int i=0; i<(right-middle); i++){
        temp2[i]=aux[middle+1+i];
    }
    int i=0, j=0, k=left;
    while(i<(middle-left+1) && j<(right-middle))
    {
        if(temp[i]<temp2[j]){
            aux[k++]=temp[i++];
        }
        else{
            aux[k++]=temp2[j++];
        }
    }
    while(i<(middle-left+1)){
        aux[k++]=temp[i++];
    }
    while(j<(right-middle)){
        aux[k++]=temp2[j++];
    }
}

void mergeSortSerial(int aux[], int left, int right){
    if (left < right){
        int middle = (left + right)/2;
        mergeSortSerial(aux,left,middle); //call 1
        mergeSortSerial(aux,middle+1,right); //call 2
        merge(aux,left,middle,right);
    }
}

void mergeSort (int aux[], int left, int right){
    if (left < right){
        if ((right-left) > 1000){
            int middle = (left + right)/2;
           #pragma omp task firstprivate (aux, left, middle)
                mergeSort(aux,left,middle); //call 1
            #pragma omp task firstprivate (aux, middle, right)
                mergeSort(aux,middle+1,right); //call 2
            #pragma omp taskwait
            merge(aux,left,middle,right);
        } else{mergeSortSerial(aux, left, right);}
    }
}

void print(int aux[], int n)
{
    for(int i=0; i<n; i++)
        cout<<aux[i]<<" ";
    cout<<endl;
}



int main(){
    generate_list(Vet, n);
    omp_set_nested(1);
    omp_set_num_threads(4);
    //startTime = clock();
    int middle = n/2;
    int middleLeft = (n) / 4;
    int middleRight = 3 * (n) / 4;
       #pragma omp parallel
   {
      #pragma omp single nowait
        mergeSort(Vet, 0, middleLeft);
      #pragma omp single nowait
        mergeSort(Vet, middleLeft+1, middle);
      #pragma omp single nowait
        mergeSort(Vet, middle+1, middleRight);
      #pragma omp single nowait
        mergeSort(Vet, middleRight+1, n);
    }
        merge(Vet, 0, middleLeft, middle);
        merge(Vet, middle+1, middleRight, n);
        merge(Vet, 0, n/2, n);



    //stopTime = clock();
    cout<<is_sorted(Vet,Vet+n)<<endl;
    //print(Vet, n);
    //printf("\nSorted in (aprox.): %f seconds \n\n", (double)(stopTime-startTime)/CLOCKS_PER_SEC);
    return(0);
}
...