Проблема с размером массива при параллельной сортировке слиянием в OpenMP.Как я могу разделить сортировку слиянием на несколько задач? - PullRequest
Новая
       24

Проблема с размером массива при параллельной сортировке слиянием в OpenMP.Как я могу разделить сортировку слиянием на несколько задач?

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

Я изучаю паралеллизм с использованием OpenMP.Я пытаюсь разделить MergeSort по задачам, чтобы получить лучший результат.

Я уже получил хороший результат, выполняя его с задачами, но теперь я пытаюсь разделить больше задач на одну итерацию, чтобы я могиспользовать больше процессоров (в моем исходном коде я использую около 1,5 процессоров на рекурсию).

Поэтому я разделил свой Mergesort на четыре, а не на два вызова на рекурсию, но получаю ошибкудлина массива: 

terminate called after throwing an instance of 'std::bad_array_new_length'
  what():  std::bad_array_new_length
Abortado (imagem do núcleo gravada)

Мой код ниже, на C ++ 

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

int n = 10000;
int * Vet = new int [10000];
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;
            int middleleft = (left + right)/4;
            int middleright = right-middleleft;
           #pragma omp task firstprivate (aux)
                mergeSort(aux,left,middleleft); //call 1
            #pragma omp task firstprivate (aux)
                mergeSort(aux,middleleft+1,middle); //call 2
            #pragma omp task firstprivate (aux)
                mergeSort(aux,middle+1,middleright); //call 3
            #pragma omp task firstprivate (aux)
                mergeSort(aux,middleright+1,right); //call 4            
            #pragma omp taskwait
            merge(aux,left,middleleft,middle);
            merge(aux,middle+1,middleright,right);
            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();

       #pragma omp parallel
   {
      #pragma omp single
        mergeSort(Vet, 0, n-1);
   }
    cout<<is_sorted(Vet,Vet+n)<<endl;
    return(0);
}

1 Ответ

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

Ваши вычисления middleLeft и middleright в mergeSort неверны и могут давать значения вне диапазона [left, right]. Например, если left равно 20, а right равно 30, middle будет равно 25, middleLeft 12 и middleRight 18.

Вместо этого вы хотите: 

middleLeft = left + (right - left) / 4;
middleRight = left + 3 * (right - left) / 4;
...