2
\$\begingroup\$

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);
        }
    }
}
\$\endgroup\$
  • 4
    \$\begingroup\$ Out of curiosity, have you tried benchmarking these against std::sort with a parallel execution policy? \$\endgroup\$ – Frank Nov 28 '17 at 0:15
  • 1
    \$\begingroup\$ I can't really run tests right now, but I would guess that breaking out of the parallel algorithm when high-lo < threshold would probably help. I would expect the task bookeeping overhead to overtake your paralelism gains at some point. \$\endgroup\$ – Frank Nov 28 '17 at 2:01
  • \$\begingroup\$ It would be nice to see the partition() function as that can affect the running time of quick sort. \$\endgroup\$ – user1118321 Nov 28 '17 at 3:19
  • 1
    \$\begingroup\$ It's not at all clear you're parallelizing your quicksort the right way. You should think about the danger of cache thrashing and memory bandwidth saturation. In fact, I would not be so sure that quicksort is the best choice for parallelization. \$\endgroup\$ – einpoklum Nov 28 '17 at 10:41
  • \$\begingroup\$ This code spawns two new threads on every call. Thus the number of threads spawned will approximate the size of the input. If arr[] has 4096 elements, it spawns around 4096 threads. Did you intend to spawn at most Nthreads? I pointed this out on StackOverflow in one of the several duplicate questions you have posted, but radio silence.... Hunter - Do you copy? Calling @Hunter Davis... \$\endgroup\$ – Jive Dadson Nov 30 '17 at 7:50
2
\$\begingroup\$

Nested parallelism is expensive. It was designed for around 1 nesting level when the first level is not parallel enough, and loop slicing. This kind of recursive problems are much better handled by tasks.

void quickSort_tasks(int arr[], int low, int high)
{
    int pi; 
    if (low < high)
    {
        pi = partition(arr, low, high);
        #pragma omp task
        quickSort_Optparallel_omp(arr, low, pi - 1);
        #pragma omp task
        quickSort_Optparallel_omp(arr, pi + 1, high);
    }
}

void quickSort_omp(int arr[], int low, int high) {
   #pragma omp parallel
   #pragma omp single
   quickSort_tasks(arr,low,high);
   // implicit synchronization at the end of parallel section
   // otherwise use 
   // #pragma omp taskwait
}

Other sorting algorithms may offer higher performance or more efficient parallelization, although being algorithmically more complex. I'm thinking about radix, pigeonhole and merge sorting.

Parallel radix sort explanation: http://projects.csail.mit.edu/wiki/pub/SuperTech/ParallelRadixSort/Fast_Parallel_Radix_Sort_Algorithm.pdf

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.