no visible efficiency boost via sectioning in quicksort-alg

General OpenMP discussion

no visible efficiency boost via sectioning in quicksort-alg

Postby Nyran » Fri Nov 02, 2012 4:43 pm

Hi everyone,
As I tried to achieve a speed-up in a quicksort algorithm which has to sort 32,000 double variables in an array I encountered some problems.

First, i could'nt see any time between sorting the array filled with random numbers sequentially and parallel. I sorted the array multiple times and tried different numbers for the iterations, but was never able to see any difference between both methods.

Tough I'm quite sure, that I'm using the "sections"-directive correct, as I tried it in another program where i filled tons of double arrays. As I set the number of iterations to a high level, I figured that parallel processing with sections took just half the time of sequential processing.

Here is the quicksort-function in which I can't see any improvement:

Code: Select all
void paraQuicksort(double *v, int start, int end)
{
    int i = start, j = end;
    double pivot;

    // sorting
    pivot = v[(start + end) / 2];   // center element
    do {
        while (v[i] < pivot)
            i++;
        while (pivot < v[j])
            j--;
         if (i <= j)
         {               // only if both indices do not touch
            swap(v, i, j);
            i++;
            j--;   
          }
        } while (i <= j);



   
    #pragma omp parallel sections
    #pragma omp section
   {
       if (start < j)
       {
           paraQuicksort(v, start, j);      // divides left segment
       }
    }
    #pragma omp section
    {
       if (i < end)
       {
           paraQuicksort(v, i, end);        // divides right segment
       }
    }
}


I'm using the gcc compiler v. 4.6.3 under Ubuntu 12.xx with an Intel i-7 processor. As I compile it with the -fopenmp and a gcc version above 4.4 I suppose I also run openMP 3.x.

I know that the quicksort algorithm performs right, but almost every cases I tried the parallel algorithm performed worse than or at least equal as the sequentiell algorithm.

My question is, if it is normal, that i don't see any improvement of the time used to perform this task (maybe because of the overhead which is created by using additional threads for a relatively simple task like this), altough quicksort seems to be a frequently used example in sectioning, or if I just missed a point in setting up the sectioning for recursive parts.

I would be glad if someone could help me with my little problem and apologize for missing information you may need.

With best regards,
Nyran
Nyran
 
Posts: 3
Joined: Fri Nov 02, 2012 3:15 pm

Re: no visible efficiency boost via sectioning in quicksort

Postby MarkB » Tue Nov 06, 2012 4:03 am

Hi Nyran,

Are you measuring the time for the whole program, or just the parallel region?
How long does the sort take sequentially?

Mark.
MarkB
 
Posts: 480
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Re: no visible efficiency boost via sectioning in quicksort

Postby Nyran » Tue Nov 06, 2012 2:42 pm

Hi Mark,

I split my program into two parts:
The first part is the sequential sort of a vector of length X and the second part is the parallel sort of another vector with the same length X.

I assume, that the time that is needed to sort a vector of length X is almost the same, considering both are filled with random numbers.

First, I measure the time of the part, where it sorts the vector sequentially, let the program write the time to the console, and then I'm doing the same with the parallel part.

There is no real difference in execution time on Windows 7, and even worse, the time the computer takes to sort parallel is even more on OpenSuse.

Only if I split the parallel sort in two parts, where it creates threads on the first level and executes the rest sequentially, I get some boost in parallel execution.

Therefore I suppose the overhead that is created with every thread for such a small task is way too high to be useful.

If you or anyone else has another suggestion I am glad to hear from you.

Nyran
Nyran
 
Posts: 3
Joined: Fri Nov 02, 2012 3:15 pm

Re: no visible efficiency boost via sectioning in quicksort

Postby Oldboy » Tue Nov 06, 2012 2:49 pm

Quicksort is very fast with compiled code on a new CPU so you need something like 10 milion numbers to see a clear effect serial->parallell.
One alternative could be to add a delay for every recursion.
Oldboy
 
Posts: 17
Joined: Wed Oct 31, 2012 2:39 am

Re: no visible efficiency boost via sectioning in quicksort

Postby MarkB » Wed Nov 07, 2012 7:40 am

Nyran wrote:Therefore I suppose the overhead that is created with every thread for such a small task is way too high to be useful.


Hi Nyran,

This is almost certainly the problem: the overhead of a parallel region is typically in the tens of microseconds range, even on small numbers of threads.

Mark.
MarkB
 
Posts: 480
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Re: no visible efficiency boost via sectioning in quicksort

Postby Nyran » Wed Nov 07, 2012 2:32 pm

Thanks for your effor Mark and Oldboy!

I guess if I section a raytracer application there will be some efficiency boost, therefore I'll try that one.

This thread can be closed. =)
Nyran
 
Posts: 3
Joined: Fri Nov 02, 2012 3:15 pm


Return to Using OpenMP

Who is online

Users browsing this forum: Exabot [Bot], Google [Bot], Yahoo [Bot] and 4 guests