0

I'm doing a paralellism study using OpenMP. I'm trying to divide a MergeSort in tasks to get a better result.

I already got a good result doing it with tasks, but now I'm trying to divide on more tasks per iteration, so I can use more CPU's (in my original code I'm using about 1,5 CPU per recursion).

So I divided my Mergesort in four rather then two calls per recursion, but i'm getting an error of bad array lenght:

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

My code is below, in 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);
}
0

1 Answer 1

2

Your calculation of middleLeft and middleright in mergeSort are wrong, and can give values outside the [left, right] range. For example, if left is 20, and right is 30, middle will be 25, middleLeft 12, and middleRight 18.

What you want to do instead is:

middleLeft = left + (right - left) / 4;
middleRight = left + 3 * (right - left) / 4;
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.