2

I'm trying to convert a quicksort to a parallel quicksort with openMp and I'm not sure if I'm on the right track. The regular quicksort I have works fine its the parallel version I'm not sure about. I want to have the parallel version use around 4 threads so it will execute faster than the non parallel version. Any advice on where to implement the threads?

void quickSort(int arr[], int low, int high)
{
    int pi;
    if (low < high)
    {
        //pi is partitioning index, arr[p] is now at right place 
        pi = partition(arr, low, high);
        // Separately sort elements before partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void quickSort_parallel_omp(int arr[], int low, int high)
{
    int pi;
    if (low < high)
    { 
        pi = partition(arr, low, high);
        omp_set_nested(1);
        #pragma omp parallel sections num_threads(Nthreads)
        {           //Nthreads is declared in the main as int Nthreads = 4
            #pragma omp section
            quickSort_parallel_omp(arr, low, pi - 1);
            #pragma omp section
            quickSort_parallel_omp(arr, pi + 1, high);
        }
    }
}

EDIT: My question is not a duplicate, the question mine is being compared to asks for help in fixing its incorrect output. My output is fine, I am asking what else I should implement into my parallel sort to get it to execute in a faster time than the non parallel quick sort

user6088127
  • 27
  • 9
  • 1
    There's a huge amount of questions on SO about `[openmp] quicksort` plus a vast array of resources easily accessible through your favorite search engine. Where exactly are you struggling? My only advice: use tasks. – Zulan Nov 26 '17 at 20:46
  • I know I have been looking at a lot of examples for awhile now and I just wanted someones input about how I set mine up and where I should place my threads etc.. – user6088127 Nov 26 '17 at 21:23
  • 1
    You should follow Zulan's advice. Since this is undoubtedly an exercise to teach you something, you should read the information that is already available. He's also given you a critical hint: ***USE TASKS*** – Jim Cownie Nov 27 '17 at 09:15
  • 1
    Possible duplicate of [OpenMP parallel quicksort](https://stackoverflow.com/questions/16007640/openmp-parallel-quicksort) – Jorge Bellon Nov 27 '17 at 13:37
  • 1
    You can find iterative versions of quicksort in ompSCR benchmark source code. – Jorge Bellon Nov 27 '17 at 13:45
  • This has the same problem as the bitonic sort you posted about. It spawns new threads exponentially. You don't understand what omp_set_nested and num_threads do. – Jive Dadson Nov 29 '17 at 19:45

0 Answers0