I'm trying to take my existing parallel Quicksort and make it execute faster. Below is what I have but half the time the optimized version doesn't give me a faster time.
I use them to compare big arrays whose sizes are 10,000 or more. Any advice on what I should change? Nthreads
is declared in the main
function and set to 4.
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
{
#pragma omp section
quickSort_parallel_omp(arr, low, pi - 1);
#pragma omp section
quickSort_parallel_omp(arr, pi + 1, high);
}
}
}
void quickSort_Optparallel_omp(int arr[], int low, int high) //optimized version
{
int pi;
if (low < high)
{
pi = partition(arr, low, high);
omp_set_nested(1);
#pragma omp parallel sections num_threads(Nthreads)
{
#pragma omp section
quickSort_Optparallel_omp(arr, low, pi - 1);
#pragma omp section
quickSort_Optparallel_omp(arr, pi + 1, high);
}
}
}
high-lo < threshold
would probably help. I would expect the task bookeeping overhead to overtake your paralelism gains at some point. \$\endgroup\$partition()
function as that can affect the running time of quick sort. \$\endgroup\$